ElevateDB uses available indexes and I/O cost estimates when optimizing SQL queries so that they execute in the least amount of time possible. In addition, joins are re-arranged whenever possible so that the smallest number of actual join operations occur during the execution of a query.

Index Selection

---

ElevateDB will use an available index to optimize any expression in the JOIN or WHERE clause of an SELECT, UPDATE, or DELETE statement. It will also use an available index to optimize any join expressions between multiple tables. This index selection is based on the following rules:

1) ElevateDB can only optimize expressions that resolve to the following formats:

<ColumnReference> [<CollationReference>] <Operator> <Expression>

<RowValueConstructor> <Operator> <Expression>

<RowValueConstructor> =

(<ColumnReference> [<CollationReference>],
 <ColumnReference> [<CollationReference>]
 [,<ColumnReference> [<CollationReference>]])

The <ColumnReference> or <RowValueConstructor> and <Expression> items are not order-dependent, and ElevateDB will reverse them as necessary so that the <ColumnReference> or <RowValueConstructor> is on the left-hand side of the <Operator>. The only requirement is that the <Expression> be appropriate for what is being compared against, so if a comparison is being made against a row value constructor, then the expression must also use a row value constructor.

For more information on row value constructors, please see the Row Value Constructors topic.

2) ElevateDB only uses the first column of any given index for the optimization of single column references. This means that if you have an index containing the columns LastName and FirstName, ElevateDB can only use the this index for optimizing any expressions that contain a reference to the LastName column. When optimizing a row value constructor that is comprised of column references, ElevateDB will try to find a matching index by comparing the column references in the row value from left-to-right.

3) ElevateDB can use an index for optimization irrespective of the ascending or descending status of a given column in the index.

4) ElevateDB can only use an index for optimization if columns in the index match both the column references and their collation references, if specified, in the expression that ElevateDB is attempting to optimize. If the collation references are not specified, then columns in the index must match the defined collations for the column references.

5) ElevateDB can mix and match the optimization of expressions so that it is possible to have one expression be optimized and the other not. This is known as a partially-optimized query.

For example, suppose that you have a Customer table with a State column that was defined with the ANSI_CI (ANSI collation, case-insensitive). An index was created on the State column using the following CREATE INDEX statement:

CREATE INDEX State ON Customer (State)

To execute an optimized search for any rows where the State column contains 'FL', one would use the following SELECT statement:

SELECT *
FROM Customer
WHERE State = 'FL'

Since the collation defined for the State column is case-insensitive, you could also use the following SELECT statement and get the same result:

SELECT *
FROM Customer
WHERE State = 'fl'

However, suppose that the State column was defined with simply the ANSI collation (case-sensitive), but the index was created using the following CREATE INDEX statement:

CREATE INDEX State ON Customer
(State COLLATE ANSI_CI)

In order to allow ElevateDB to use this index to optimize any searches on the State column, you must now specifically reference the ANSI_CI collation in the actual search expression:

SELECT *
FROM Customer
WHERE State COLLATE ANSI_CI = 'FL'

Please see the Internationalization topic for more information on collations.

How ElevateDB Selects the Rows

---

Once an index is selected for the optimization of an expression in a JOIN or WHERE clause, a range is set on the index in order to limit the index keys to those that match the current expression being optimized. The index keys that satisfy the expression are then scanned, and during the scan a bitmap is built in row order. A bit is turned on if the index key satisfies the expression, and a bit is turned off if it doesn't. This method of using bitmaps works well because it can represent sets of data with minimal memory consumption. Also, ElevateDB is able to quickly determine how many rows are in a given set by how many bits are turned on, and it can easily AND, OR, and NOT bitmaps together to fulfill boolean logic between multiple expressions joined by the AND, OR, and NOT boolean operators. Finally, because the bitmap is in row order, accessing the rows using a bitmap is very direct since ElevateDB uses fixed-length rows with directly-addressable offsets in the table.

Optimizing Before-Join Expressions

---

When optimizing queries that contain both JOIN and WHERE expressions, ElevateDB always processes the WHERE expressions first if the expressions do not reference the target table(s) in any of the join(s). The target table in a join is the table on the right side of a LEFT OUTER JOIN or the table on the left side of a RIGHT OUTER JOIN. WHERE expressions that reference the target table in a join are called after-join expressions (see below).


Evaluating WHERE expressions as before-join expressions can speed up the joins tremendously since the joins will only need to take into account the rows in the source tables based upon the before-join WHERE expressions. For example, consider the following query:

SELECT
OrderHdr.Cust_ID,
OrderHdr.Order_Num,
OrderDet.Model_Num,
OrderDet.Cust_Item
FROM OrderHdr INNER JOIN OrderDet ON
OrderHdr.Order_Num=OrderDet.Order_Num
WHERE OrderHdr.Cust_ID = 'C901'
ORDER BY OrderHdr.Cust_ID,
OrderHdr.Order_Num

In this example, the WHERE expression:

OrderHdr.Cust_ID = 'C901'

will be evaluated first before the INNER JOIN expression:

OrderHdr.Order_Num = OrderDet.Order_Num

so that the INNER JOIN only needs to evaluate a small number of rows in the OrderHdr table.

Optimizing During-Join Expressions

---

When optimizing SELECT queries that contain INNER JOINs that contain non-join expressions in addition to join expressions, the non-join expressions are always processed at the same time as the join expression, even if they affect the target table of the INNER JOIN. This can speed up join operations tremendously since the join expressions will only take into account the rows existing in the target table based upon the non-join expression(s). For example, consider the following query:

SELECT
OrderHdr.Cust_ID,
OrderHdr.Order_Num,
OrderDet.Model_Num,
OrderDet.Cust_Item
FROM OrderHdr INNER JOIN OrderDet ON
OrderHdr.Order_Num = OrderDet.Order_Num AND OrderHdr.Cust_ID = 'C901'
ORDER BY OrderHdr.Cust_ID,
OrderHdr.Order_Num

In this example, the non-join expression:

OrderHdr.Cust_ID = 'C901'

will be evaluated first before the join expression:

OrderHdr.Order_Num = OrderDet.Order_Num

so that the joins only need to process a small number of rows in the OrderHdr table.

After-Join Expressions

---

After-join expressions are expressions that must be processed after any joins have executed because they contain a column reference to a column in a table that is the target table of a right or left outer join. After-join expressions are always evaluated in an un-optimized manner, meaning that they are processed after all joins have been executed. Therefore, they are not useful in limiting the amount of work or costs involved in a particular query, but rather only useful in filtering the resultant rows of the query based upon a specific expression. For example, consider the following query:

SELECT
OrderHdr.Cust_ID,
OrderHdr.Order_Num,
FROM OrderHdr LEFT OUTER JOIN OrderDet ON
OrderHdr.Order_Num = OrderDet.Order_Num
WHERE OrderDet.Order_Num IS NULL
ORDER BY OrderHdr.Cust_ID,
OrderHdr.Order_Num

In this example, the non-join expression:

OrderHdr.Order_Num IS NULL

will be evaluated after all joins have been executed so that ElevateDB can accurately assess whether the LEFT OUTER JOIN has caused any NULL Order_Num columns to be generated from the join.

How Joins are Executed

---

Joins in a SELECT statement are executed in ElevateDB using a technique known as nested-loop evaluation. This means that ElevateDB recursively processes the source tables in a master-detail, master-detail, etc. arrangement with a driver table and a target table (which then becomes the driver table for any subsequent joins). When using this technique, it is very important that the table with the smallest row count, after any non-join expressions have been evaluated, is specified as the first driver table in the join execution. ElevateDB's optimizer will automatically optimize the join ordering so that the table with the smallest row count is placed as the first driver table, as long as the joins are INNER JOINS. LEFT OUTER JOINs and RIGHT OUTER JOINs cannot be re-ordered in such a fashion and must be left as-is.

The following is an example that illustrates nested-loop joins in ElevateDB:

SELECT c.Company,
o.OrderNo,
e.LastName,
p.Description,
v.VendorName
FROM Customer c
INNER JOIN Orders o ON c.CustNo=o.CustNo
INNER JOIN Employee e ON o.EmpNo=e.EmpNo
INNER JOIN Items i ON o.OrderNo=i.OrderNo
INNER JOIN Parts p ON i.PartNo=p.PartNo
INNER JOIN Vendors v ON p.VendorNo=v.VendorNo
ORDER BY e.LastName

In this example, ElevateDB would process the joins in this order:

1) The Customer table is joined to Orders table on the CustNo column.

2) The Orders table is joined to the Items table on the OrderNo column and the Orders table is joined to Employee table on the EmpNo column (this is also known as a multi-way, or star, join).

3) The Items table is joined to the Parts table on the PartNo column.

4) The Parts table is joined to the Vendors table on the VendorNo column.

In this case the Customer table is the smallest table in terms of its row count, so making it the driver table in this case is a good choice.


Execution Plans

---

ElevateDB can generate an execution plan for any DML statement. Please see your product-specific manual for more information on retrieving an execution plan for a SELECT, INSERT, UPDATE, or DELETE statement.

Limitations to the Optimizer

---

ElevateDB does not currently optimize multiple JOIN or WHERE expressions joined by an AND operator by mapping them to multiple columns in an available index. To illustrate this point, consider a table with the following structure:

Employee

Column      Data Type      Index
----------------------------------------------------------------------
LastName    VARCHAR(30)    Primary Key  (both columns are part of the
FirstName   VARCHAR(20)    Primary Key   primary key constraint)

And consider the following SELECT statement:

SELECT *
FROM Employee
WHERE (LastName = 'Smith') and (FirstName = 'John')

Logically you would assume that ElevateDB can use the one index available for the enforcement of the primary key constraint in order to optimize the entire WHERE clause. Unfortunately, this is not the case, and instead ElevateDB will only use the index created for the primary key constraint for optimizing the LastName expression and resort to reading the resultant rows in order to evaluate the FirstName expression.

However, you can overcome this limitation by using a row value constructor instead of two expressions combined with the AND operator:

SELECT *
FROM Employee
WHERE (LastName,FirstName) = ('Smith','John')

With the WHERE clause specified using a row value constructor, ElevateDB will be able to use the entire primary key to optimize the expression.