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

approach results in the following additional benefits (note that some of the
following features are also applicable in a bottom-up strategy, but they are
more di cult to design and implement in such a context):

• The merging/reduction and enumeration steps in Figure 6.1 are inter-

leaved. It is not required to obtain all merged indexes before starting
enumeration, but instead these can be generated lazily, on demand, while
traversing the enumeration space.

• Configurations are always transformed by replacing some indexes by

others that are smaller but less ecient, so estimating the cost of the
workload under a transformed configuration can be done more eciently
(we need only to reoptimize queries that originally used some of the
transformed indexes). In a bottom-up strategy, adding a new index to
an existing configuration requires reoptimizing all queries that reference
the index table (or resort to heuristics, which introduces additional in-
accuracies).

• A top-down approach provides additional information to the database

administrator. Since we progressively transform ecient configurations
so that they use less space while performing slightly worse, at the end
of the tuning process we have many alternative configurations that are
more ecient than the final recommendation but that use more re-
sources. This might provide hints about the distribution of more e-
cient configurations to the database administrator and help in making
decisions (e.g., increasing the disk storage in the current database in-
stallation). Figure 6.5 shows a sample output of a top-down strategy
described in this section for a TPC-H workload. Using the initial con-
figuration (requiring 1.25 GB), the workload is estimated to execute
in 2,469 time-units. The optimal configuration can bring the execution
cost down to 540 time-units but requires over 6 GB of space. The best
configuration under 1.75 GB (the input constraint) is estimated to re-
sult in 1,388 time-units (56% of the original estimated cost). The figure
shows that adding up to 250 MB of additional disk space can result in
an additional 10% improvement (a reasonable trade-off). It also shows
that having more than 4 GB improves the situation only by a marginal
3% and therefore is not advisable (see the steep slope in Figure 6.5 for
configurations larger than 4 GB).

6.2.1 General Architecture
Figure 6.6 shows a high-level overview of a top-down enumeration architecture.
We begin the search from an initial configuration (step 1 in the figure). This
initial configuration does not need to fit in the available space but is the most
ecient one that the search strategy would explore during enumeration (in
terms of SELECT queries). We then progressively traverse the search space