Constrained Physical Database Design - Automated Physical Database Design and Tuning - page 206

11.2 Search Framework
Figure 11.2 shows a high-level architectural overview of the search framework,
which is very slightly adapted from the top-down enumeration strategy of
Figure 6.6. An important component of the framework is the global cache of
explored configurations, shown at the bottom of Figure 11.2. This global cache
contains both the set of nondominated configurations (which can be multiple
in case of more than a single soft constraint) and the remaining suboptimal
configurations that were explored.
Similar to the original top-down approach of Section 6.2, the search begins
from the initial configuration (step 1 in the figure), which becomes the cur-
rent configuration. Unless a specific initial configuration is given, the default
starting point is CSelectBest , which contains the most specific indexes that
can be used anywhere by the query optimizer for the input workload and
thus should be appropriate to handle all but nonstandard constraints. ∗ After
choosing the initial configuration, we progressively explore the search space
until a stopping condition is satisfied (typically a time bound). Each explo-
ration iteration consists of the following steps. First, we evaluate the current
configuration and store it in the global cache (step 2 in the figure). Evaluating
a configuration involves obtaining the values of each c-objective defined in the
constraint specification. Then, we perform a pruning check on the current con-
figuration. If we decide to prune the current configuration, we retrieve from
the global cache a previously explored configuration that is not pruned. At
this point, we consider transforming the current configuration to generate new
candidates (step 3 in the figure). The transformations that we consider are
the same as for the traditional physical design problem (e.g., merging and re-
duction). We rank candidate configurations based on their expected promise
and pick the best candidate configuration that is not already in the global
cache, which becomes the current configuration. This cycle repeats until the
stopping condition is met, when the database application (DBA) picks the
best configuration among those that are nondominated (step 4 in the figure).
The search framework eventually considers any configuration that is a subset
of the closure of the initial configuration under the set of transformations.
Thus, if no subset of the closure of the initial configuration satisfies all the
constraints, the problem is unfeasible. As we can see, the search strategy is
very similar to that of the traditional physical design problem. The main dif-
ference is the manner in which we rank and prune configurations, which we
discuss in the rest of this section.
∗ An example of a nonstandard constraint requires that some index not useful for any query in
the workload be present in the final configuration.