Characterizing the Search Space - Automated Physical Database Design and Tuning - page 62

shortcomings. In a way, it leverages only the final execution plan of the query,
discarding important information that is obtained during optimization. In
this section we present an instrumentation-based approach that piggybacks
on top of regular query optimization and returns a very concise description
of all access path requests of the input query. These access path (or index)
requests can then be used to identify a small superset of the optimal set of
indexes for the input query.
We assume that the optimizer has a unique entry point for single-table
access path selection (see Chapter 2 for details on these procedures). In other
words, there is one component responsible for finding physical index strategies
for single-table logical subplans. For concreteness, in this section we assume
a transformation-based optimizer, but the same ideas can be applied to other
enumeration strategies as well.

4.1.3.1 Review of Access Path Selection

During the optimization of a single query, the optimizer issues several index
requests via specific transformation rules. For an index request over a single-
table subplan (see Figure 4.2), an access path generation module first identifies
the columns in equality and range predicates, required sort columns, and the
columns that are either part of complex predicates or additionally referenced
upwards in the query tree. Then, it analyzes the available indexes and returns
one or more alternative physical plans that might be optimal for the input log-
ical subquery. In general, each generated plan is an instance of a template tree
that (1) has one or more index seeks or scans at the leaf nodes, (2) combines
the leaf nodes by binary intersections or unions, (3) applies an optional RID
lookup to retrieve missing columns, (4) applies an optional filter operator for
any remaining predicate, and (5) applies an optional sort operator to enforce
order. Consider a single-table index request for the Standard Query Language
( SQL ) fragment below (note that this query fragment can be part of a larger
query that joins multiple tables, but the optimizer calls only the access path
selection module for single-table query fragments):
d , e σ a < 10 ∧ b < 10 ∧ a + c = 8 ( ) R (with a sort requirement over column d )

In this case, the optimizer identifies columns a and b in sargable predicates
(i.e., predicates that can leverage index seeks), column d as a required order,
and columns e and c as additional columns that are referenced either by
nonsargable predicates or upward in the tree. Suppose that indexes R(a) and
R(b) are available. The optimizer can then generate the plan in Figure 4.1a.
However, depending on selectivity values, the alternative plan in Figure 4.1b
(that avoids intersecting indexes but performs more record id (RID) lookups)
can be more attractive. Also, if a covering index R(d|a,b,c,e) is available, the
alternative plan in Figure 4.1c might be preferable because it avoids sorting an
intermediate result. A cost-based optimizer considers this space of alternative
plans for the available indexes and returns the most ecient physical strategy.