Restriction Optimization

This section provides a detailed description of the primary techniques employed by the database engine to make use of expressions in a restriction for optimization purposes. The types of optimizations performed by the database engine are described below in order from the simplest to the most complex.

A clear understanding of optimization techniques used by the database engine may aid you in structuring queries to achieve optimal performance from the database engine. In addition, by understanding how the database engine uses indexes to optimize queries, you can determine how to construct indexes that provide the best performance for a given set of typical uses.

For the sake of simplicity, the descriptions below initially address expressions that reference columns from only a single table. Optimizations making use of join conditions, in which predicates compare columns from two different tables, are described following the single table optimizations.

For definitions of the technical terms used in this chapter, see Terminology.

Single Predicate Optimization

The simplest form of Restriction optimization involves the use of a single Predicate. A predicate can be used for optimization if it meets all of the following conditions:

•

the predicate is joined to the rest of the restriction by the AND operator

•

one operand of the predicate consists of a column reference which is a leading segment of an index and the other operand consists of an expression that does not contain a column reference (that is, the other operand contains only a literal value or dynamic parameter)

•

the comparison operator is one of: <, <=, =, >=, >, LIKE, or IN.

For example, suppose an index exists with the first segment on column c1. The following predicates can be used for optimization:

c1 = 1

c1 IN (1,2)

c1 > 1

The LIKE operator is optimized only if the second operand starts with a character other than a wildcard. For example, C2 LIKE ‘ABC%’ can be optimized, but C2 LIKE ‘%ABC’ will not be.

Closed Range Optimization

A Closed Range can be used for optimization if it satisfies all the requirements for Single Predicate Optimization.

For example, suppose an index exists with the first segment on column c1. The following closed range can be used for optimization:

c1 >= 1 AND c1 < 10

Modified Disjunct Optimization

A Modified Disjunct can be used for optimization if it satisfies all of the following conditions:

•

it is joined to the rest of the Restriction by the AND operator

•

each Predicate and Closed Range in the disjunct satisfies the requirements for Single Predicate Optimization and Closed Range Optimization

•

each predicate or closed range references the same column as the others.

For example, suppose an index exists with the first segment on column c1. The following modified disjunct can be used for optimization:

c1 = 1 OR (c1 > 5 AND c1 < 10) OR c1 > 20

The following modified disjunct cannot be used for this type of optimization because the same column is not referenced in all predicates and closed ranges:

c1 = 1 OR (c1 > 5 AND c1 < 10) OR c2 = 1

Conjunct Optimization

A Conjunct can be used for optimization if it satisfies all of the following conditions:

•

it is joined to the rest of the restriction by the AND operator

•

each Predicate in the conjunct satisfies the requirements for Single Predicate Optimization

•

each predicate optimizes on the leading segments of an index with only one predicate for each leading segment (that is, there are not two different predicates that use the same set of leading segments)

•

all predicates, except for the predicate referencing the last segment used for optimization, use the equal (=) comparison operator.

For example, suppose an index exists with the first three segments on columns c1, c2 and c3, in that order. The following conjunct assignments can be used for optimization:

c1 = 1 AND c2 = 1 AND c3 = 1

c1 = 1 AND c2 = 1 AND c3 >= 1

c1 = 1 AND c2 > 1

The order of the predicates does not matter. For example, the following conjunct can be used for optimization:

c2 = 1 AND c3 = 1 AND c1 = 1

The following conjunct cannot be used for optimization because the second segment of the index is skipped (there is no reference to column c2):

c1 = 1 AND c3 = 1

In this case, the single predicate, c1 = 1, can still be used for optimization.

Disjunctive Normal Form Optimization

An expression in Disjunctive Normal Form (DNF) can be used for optimization if it satisfies all of the following conditions:

•

it is joined to the rest of the restriction by the AND operator

•

each conjunct in the expression satisfies the requirements for Conjunct Optimization with the additional limitation that all the predicates must contain the equal (=) comparison operator

•

all the conjuncts must use the same index and the same number of segments for optimization.

The database engine does not convert restrictions that are originally in DNF into modified CNF, because it can optimize on DNF.

For example, suppose an index exists with the first three segments on columns c1, c2 and c3, in that order. The following expression in DNF can be used for optimization:

(c1 = 1 AND c2 = 1 AND c3 = 1) OR (c1 = 1 AND c2 = 1 AND c3 = 2) OR (c1 = 2 AND c2 = 2 AND c3 = 2)

The following expression in DNF cannot be used for optimization because both conjuncts do not reference the same number of segments:

(c1 = 1 AND c2 = 1 AND c3 = 1) OR (c1 = 1 AND c2 = 2)

Modified Conjunctive Normal Form Optimization

An expression in Modified Conjunctive Normal Form (Modified CNF) can be used for optimization if it satisfies all of the following conditions:

•

it is joined to the rest of the restriction by the AND operator

•

each Modified Disjunct satisfies the requirements for Modified Disjunct Optimization except that each modified disjunct must reference a different index segment which together make up the Leading Segments (that is, taking all the disjuncts together, no segments can be skipped)

•

all the modified disjuncts except for the one that references the last segment must contain at least one predicate that contains the equals (=) comparison operator.

Modified CNF optimization is similar to DNF optimization but allows combinations of predicates involving different comparison operations not supported by DNF optimization.

For example, suppose an index exists with the first three segments on columns c1, c2 and c3, in that order. The following expression in modified CNF can be used for optimization:

(c1 = 1 OR c1 = 2) AND (c2 = 1 OR (c2 > 2 AND c2 < 5)) AND (c3 > 1)

It may be easier to understand how the database engine uses this expression for optimization by looking at the equivalent expression in modified DNF:

(c1 = 1 AND c2 = 1 AND c3 > 1) OR (c1 = 1 AND (c2 > 2 AND c2 < 5) AND c3 > 1) OR (c1 = 2 AND c2 = 1 AND c3 > 1) OR (c1 = 2 AND (c2 > 2 AND c2 < 5) AND c3 > 1)

Closing Open Ended Ranges through Modified CNF Optimization

Two Modified Disjuncts can be combined to form one or more Closed Ranges if the following conditions are satisfied:

•

both modified disjuncts satisfy the requirements for Modified Disjunct Optimization

•

both modified disjuncts use the same segment in the same index

•

both modified disjuncts contain open ended ranges that can be combined to form one or more closed ranges.

For example, suppose an index exists with the first segment on column c1. The following expression in modified CNF can be used for optimization:

(c1 = 1 OR c1 > 2) AND (c1 < 5 OR c1 = 10)

It may be easier to understand how the database engine uses this expression for optimization by looking at an equivalent expression which is simply a modified disjunct:

c1 = 1 OR (c1 > 2 AND c1 < 5) OR c1 = 10

Single Join Condition Optimization

The simplest form of optimization involving two tables makes use of a single Join Condition. Single join condition optimization is similar to Single Predicate Optimization. A join condition can be used for optimization if it satisfies the requirements for single predicate optimization. The table that will be optimized through the use of the join condition will be processed after the other table referenced in the join condition. The table optimized through the use of the join condition uses an optimization value retrieved from a row in the other table referenced in the join condition.

For example, suppose an index exists on table t1 with the first segment on column c1. The following join conditions can be used for optimization:

t1.c1 = t2.c2

t1.c1 > t2.c2

During optimization, a row is retrieved from table t2. From this row, the value of column c2 is used to optimize on table t1 according to the join condition.

If, instead of an index on t1.c1, there is an index on t2.c2, then t1.c1=t2.c2 could be used to optimize on table t2. In this case, table t1 would be processed first and the value for t1.c1 would be used to optimize on table t2 according to the join condition.

In the case that there is an index on t1.c1 as well as an index on t2.c2, the database engine query optimizer examines the size of both tables as well as the characteristics of the two indexes and chooses the table to optimize that will provide the best overall query performance.

Conjunct with Join Conditions Optimization

A Conjunct that consists of a mixture of join conditions and other Predicates can be used for optimization if it satisfies all of the following conditions:

•

all the join conditions compare columns from the same two tables

•

the conjunct satisfies the requirements for regular Conjunct Optimization for one of the two tables.

The table that will be optimized through the use of the conjunct will be processed after the other table referenced.

For example, suppose an index exists on table t1 with the first three segments on columns c1, c2 and c3, in that order. The following conjuncts can be used for optimization:

t1.c1 = t2.c1 AND t1.c2 = t2.c2 AND t1.c3 = t2.c3

t1.c1 = t2.c1 AND t1.c2 > t2.c2

t1.c1 = t2.c1 AND t1.c2 = 1

t1.c1 = 1 AND t1.c2 = t2.c2

Modified Conjunctive Normal Form with Join Conditions Optimization

An Expression in Modified Conjunctive Normal Form (Modified CNF) that contains join conditions can be used for optimization if it satisfies all the following conditions:

•

it satisfies the conditions for Modified Conjunctive Normal Form Optimization

•

in addition, all disjuncts but the disjunct optimizing on the last portion of the leading segment being used must contain only a single join condition or a single predicate and at least one of these is a single join condition.

For example, suppose an index exists on table t1 with the first three segments on columns c1, c2 and c3, in that order. The following expressions in modified CNF can be used for optimization:

(t1.c1 = t2.c1) AND (t1.c2 = t2.c2 OR

(t1.c2 > 2 AND t1.c2 < 5))

(t1.c1 = 1) AND (t1.c2 = t2.c2) AND

(t1.c3 > 2 AND t1.c3 < 5)

Closing Join Condition Open Ended Ranges through Modified CNF Optimization

This type of optimization is exactly like Closing Open Ended Ranges through Modified CNF Optimization except that the range being closed may be a Join Condition.

For example, suppose an index exists on table t1 with the first two segments on columns c1 and c2, in that order. The following expressions in modified CNF can be used for optimization: