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

I1 , I2, I3, I4 (20)

I1, I2, I3 (45) I2 , I3 , I4 (50)

I2, I3 (50) I3, I4 (65)

I1, I3 (80)

I3 (80) I4 (80)

FIGURE 5.2 Index benefit graph for a query.

of the IBG we can obtain a recursive top-down algorithm to compute graph
instances (see Figure 5.3). Specifically, we start with all candidate indexes in C
and perform a what-if optimization call. Suppose that the resulting plan uses
indexes U

⊆ C . We then create node N=(C, U, cost(q,C)) . Then, for each

U we recursively obtain the root N' of the IBG graph calculated from q
and C-

∈

I

and connect N and N' . The size of the resulting IBG might be,
in the worst case, exponential in the number of indexes. In general, however,
IBG sizes are much smaller (the example in Figure 5.2 has 8 of 16 possible
index subsets).
An interesting property of an IBG graph is that we can infer the cost of
the input query under arbitrary configurations without making additional
optimization calls. In fact, the used indexes U in each node N=(C,U,cost)
correspond to atomic configurations for the input query, since a well-behaved
optimizer would return the same plan under C or U . For instance, the atomic
configurations in Figure 5.2 are {

{ }

I

I 3 } . Additionally,
it can be shown that all atomic configurations are represented in IBG nodes.
Therefore, after an IBG has been computed, it can be used to infer all atomic
configurations and thus query costs under arbitrary configurations.

I 1 , I 4 } , { I 1 , I 2 } , { I 2 } , and {

buildIBG (q:Query, C:Configuration)
return root note of the IBG for q and C
01 P = plan for q under C (using indexes U ⊆ C)
02 N = new node (C, U, cost(q,C))
03 foreach I ∈ U
04 N = buildIBG (q, C-I)
05 add edge between N and N'
06 return N

FIGURE 5.3 Obtaining the IBG for a given query and initial set of indexes.