Characterizing the Search Space - Automated Physical Database Design and Tuning - page 66

25

20

15

10

5

0

Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19 Q20 Q21 Q22

FIGURE 4.4 Index requests for a typical TPC-H workload.

4.1.3.3 Finding the Best Indexes for a Request

The instrumentation approach described in the previous section returns a
concise encoding of all access path requests performed by the optimizer for
an input query. If we obtain the indexes that best implement each of these
requests and unite them, the result would be a superset of the optimal con-
figuration for the input query.
In general, if we can choose the physical design, the optimal execution
plan for a given request cannot use index intersections. Consider an execution
plan that intersects a number R A and R B of rows from table R that are
produced, respectively, by indexes I A (stored in P A pages) and I B (stored
in P B pages). The number of inputs/outputs (I/Os) required by this plan is
C AB = P A

R A R B

is the number of I/Os used to intersect RIDs
(we assume fixed-size records, but this does not change the main result). Now,
assume without loss of generality that R A <

| R | +

P B

| R | +

, where

R B , and consider index I D , which
consists of all columns of I A followed by the columns in I B that are not in
I A . Index I D can be stored in P D ≤

P B pages because some columns (at
least RIDs) are duplicated in I A and I B . Seeking I D with the predicates used
in I A results in R D = R A rows. Therefore, the total number of I/Os by using
I D is C D

P A +

R D R A R A R A

= P D

| R | ≤ (

P A + P B )

| R | =

P A

| R | +

P B

| R | ≤

C AB , since R A < R B

and 0. The optimal execution plan therefore uses at most one index (and

optional RID lookups).
We next show how to obtain the indexes that would lead to the best exe-
cution plan implementing a given access path request, for progressively more
complex scenarios. Specifically, we assume that N

≥

1 since the best index for
a request is independent of the number of times the corresponding subplan
would be executed.

=