Designing a Cost Model - Automated Physical Database Design and Tuning - page 86

upperBound (q:Query, newC:Configuration, CS:set of)
Configurations
return upper bound on cost ( q , ne w C )
01 result = null
02 foreach CinCS
03 P = plan for q under C
04 foreach index-based subplan p of P such that
(i) uses indexes in (C-newC), or
(ii) is defined over a table compatible with an
index in (newC-C)
05 replace p in P with the best alternative using
indexes in newC
06 if expected cost of P is better than expected cost of
result, result = P
07 return expected cost of result

FIGURE 5.5 Obtaining upper bounds on query costs.

Note that the best we can do by following this approach is to obtain a locally
optimal execution plan. That is, we replace only some physical subplans asso-
ciated with index strategies with alternatives that are as ecient as possible
under the new configuration. We would not be able, however, to obtain a plan
with different join orders or in general with a different internal subplan. In
that sense, we are giving up some opportunities to obtain the globally optimal
execution plan but avoid an expensive what-if optimization call.

5.2.2.2 Gathering Information to Transform Subplans

The first step to transform an index-based subplan is to understand which task
the subplan is performing so that the transformed subplan returns the same
result. To that end, an available source of information is the query execution
plan itself. In general, DBMSs return rich supporting information along with
query execution plans. Specifically, it is common to be able to extract or infer
information about each index-based subplan by inspecting the corresponding
execution plan. Such information includes the estimated input/output (I/O)
and central processing unit (CPU) cost of the subplan, the estimated number
of rows returned, the type of index usage (i.e., whether the indexes are used
to seek a fraction of the rows or to scan all rows), the resulting order of the re-
turned rows, and the set of additional columns that are required upward in the
tree. An alternative and more accurate way to obtain this information is by
means of the access path requests intercepted during query optimization (see
Section 4.1.3). Access path requests encode the requirements of any possible
index strategy that might implement the corresponding subtree. Also, since
access path requests are intercepted during optimization, we can avoid the
extraction and inference of the logical requirements of an index-based subtree
based solely on execution plans.