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

Candidate
Selection

Workload

Merging/Reduction
(extending the
enumeration space)

Enumeration

Configuration

FIGURE 6.1 Generic bottom-up search framework.

in Section 4.1. Since the number of candidate indexes for a given query is
typically small, an enumeration space defined in this way has a reasonable size
that can be handled by the enumeration strategies. At the same time, however,
it will miss some interesting candidates that result from operations such as
merge and reduction (see Section 4.2), especially in the presence of storage
constraints. For that reason, some approaches consider additional indexes in
the enumeration space.
A common addition to the enumeration space is all the single-column in-
dexes that result from taking the original set of candidate indexes and remov-
ing all but the leading key column. This extended set is designed to heuris-
tically cover the reduction and splitting operations discussed in Section 4.2.
Similarly, the clustered index associated to each index in the original enu-
meration space is also included, which covers the promotion operation. It is
generally a good idea to additionally consider some merged indexes. There
are different approaches to add merged indexes to the enumeration space. A
simple syntactic strategy consists of including all indexes obtained by merging
a pair of indexes from the original candidate set. This approach can be refined
to consider only indexes that are candidates for many queries or those that
are candidates for the most expensive queries under the current configuration.
A more adaptive approach is shown in Figure 6.2 and works as follows. We
start with the initial enumeration space ES and consider merging every pair
of indexes I 1 and I 2 in ES into I 12 . We then obtain the cost of the workload
under ES and also under ES —

(that is, the configuration that
contains the merged index but none of its “parents”). If the new configuration
is no worse than the original by a factor

{ I 1 , I 2 }∪{ I 12 }

1), we keep the merged
index. We repeat this procedure until no new merged index is added in an
iteration.
Once the enumeration space is defined by any of the approaches previously
described, we can conduct the enumeration phase proper. In the rest of this
section we discuss some common alternatives.

δ (e.g., δ = 1 .