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

4.1.2 Execution Plan-Based Approach
We now discuss a variant of the parsing-based approach that works off the
execution plan produced by the optimizer rather than off the query parse tree.
To motivate this approach, consider again the example in the previous section:

SELECT R.a, R.b
FROM R, S
WHERE R.x = S.y
ORDER BY R.a

but suppose that there is a primary-key constraint on column S.y (all tuples
in S have distinct S.y values), and a foreign-key constraint on R.x referencing
the primary key of S (which guarantees that every tuple in R joins with exactly
one tuple in S ). In this case, since no column from S is present in the SELECT
clause, an optimizer might choose to simplify the previous query by removing
the superfluous join with S , obtaining the equivalent query:

SELECT R.a, R.b
FROM R
ORDER BY R.a

Performing such sophisticated analysis over the parse tree not only is very
complex but also duplicates much of the work of the optimizer. An alternative
approach to obtain candidate indexes for a query is to leverage the optimizer
itself and process the resulting execution plan rather than the input query
string. For the previous query, the execution plan would scan table R and
then sort the result by R.a . We can then obtain indexable columns (e.g.,
those that are associated with Join , Aggregate , and Sort operators) and
proceed as before. We would then obtain the candidate set for the

original query and avoid considering indexes on columns R.x and S.y , which
would not be exploited anyway by the database management system (DBMS).
In addition to the foreign-key constraint example above, optimizers rely on
several rules to transform query fragments, such as detecting contradictions
or tautologies in predicates, eliminating empty subexpressions, or inferring
implied predicates through joins. The approach that leverages execution plans
produced by the optimizer is therefore a more robust alternative to obtain
candidate indexes for a query. Another benefit of this approach is that it is
kept in sync with the optimizer. If a new simplification strategy is incorporated
into the optimizer, it can be directly leveraged by the candidate selection
module. Finally, this approach can be extended to mimic some of the features
of the more accurate instrumentation-based approach discussed in the next
section without requiring modifying the query optimizer.

{ }

R(a|b)

4.1.3 Instrumentation-Based Approach
While the execution-plan-based approach discussed in the previous section
is more robust than the parsing-based approach, it still suffers from certain