Enumerating the Search Space - Automated Physical Database Design and Tuning - page 114

B storage, we simply use T tr as the penalty associated with each

transformation tr .

6.2.3 Variations and Optimizations
We next briefly describe some minor optimizations and variations to the top-
down approach introduced in this section.

Shortcut evaluation: When evaluating the cost of a configuration C ,we
might reach a point in which the SELECT cost of a subset of queries in
C is larger than the total cost of the current best configuration C best .In
this case, we know that neither C nor any configuration that is further
relaxed from C would be more ecient than C best . Therefore, we can stop
evaluating C (thus saving optimization calls) and can backtrack to a dif-
ferent configuration (thus pruning the search space). For this heuristic
to be effective, it is useful to evaluate the workload so that more expen-
sive queries are first (this ranking of queries can be static depending on
the cost of the query under the initial configuration or adaptive based
on the configuration that was transformed to obtain the current one).
Multiple transformations per iteration: The current strategy applies
a single transformation to relax the current configuration. In general, we
might apply more than one transformation. We need to be careful that
we do not select conflicting transformations (such as merging I 1 and I 2
after removing I 1 ). This alternative might reduce the overall time to
arrive to a valid transformation but introduces additional inaccuracies
because often transformations strongly interact with each other.
Shrinking configurations: Another variation consists of removing, at
each iteration, all indexes from the current configuration that are not
used to evaluate any query in the workload. While this approach would
reduce the search space because fewer transformations are available, it
might also decrease the quality of the final recommendation, since some
structures that are not used in the current configuration might become
useful after applying some transformation.

6.3 Summary

• The search space for the physical design problem is too large to expect

exact solutions in reasonable amounts of time, even for moderately sized
input instances.