Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 40

columns that are additionally referenced in nonsargable predicates or upward
in the query tree. Then, it analyzes the available indexes and returns one or
more candidate physical plans for the input subquery.
Consider the application of such a rule for a groupExpression that represents
c (σ a = 10 (

, and further suppose that column b is a required sort order. In
this case, the rule identifies column a in a sargable predicate, column b as a
required order, and column c as an additional column that is either output
or referenced upward in the tree. This information allows the optimizer to
identify the available indexes that might be helpful to implement an ecient
subplan for the subquery. Suppose that an index on column a is available.
The optimizer can then generate a physical operator tree that uses the index
to retrieve all tuples satisfying a =10, looks up the remaining columns from a
primary index, and finally sorts the resulting tuples in b order. If an index on
columns

R ))

is also available, the optimizer might additionally generate
an operator tree that scans the index in b order and filters on the fly the tuples
that satisfy a =10. Depending on the selectivity of a =10, one alternative would
be more ecient than the other, and eventually the optimizer would pick the
one that results in the smallest execution cost.
Note that the same mechanism is used in another important rule that trans-
forms logical joins in which the right child consists of a single-table expression
into index-based join execution plans (which repeatedly access an index on
the right child's table for each tuple produced by the left input). In this case,
the same procedure is conducted but with respect to the inner table only,
and the joined column in the table is considered as part of a sargable (equality)
predicate. For instance, suppose that the logical subplan is

( b , a , c )

(Q Q. x = T . y T )

,

Q

where is a complex relational expression. Conceptually, the rule produces

an index-based join plan and considers the right-hand side a single-table se-
lection σ T . y = ? (

T ) as before (where T . y is a column in a sargable predicate with

an unspecified constant value).

2.4 Summary
Query optimization in relational databases takes an input SQL query and
produces an ecient execution plan to evaluate it. The optimization process
can be seen as a complex search problem, defined by:

• The search space, which defines the set of plans that are considered by

the optimizer

• The cost model, which provides a metric to compare alternative plans

• The enumeration algorithm, which is responsible for effectively travers-

ing the search space of plans