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

set of candidate indexes for query Q , obtained by any of the techniques of
Section 4.1. Let C i

( i ≥ 0 ) be a family of candidate indexes defined as follows:

C 0 = cand ( Q )

Q ∈ W

C i + 1 =

∪

C i

{ I 1 ⊕ I 2 for each I 1 , I 2 ∈ C i }∪

{ I 1 ⊗ I 2 for each I 1 , I 2 ∈ C i }∪

K ) for each I K ⊆

{ ρ( I , = R ( K , S ) ∈ C i , K }∪

{ ( I ) for each I ∈ C i }

That is, C i + 1 is obtained by considering all possible merges, splits, reductions,
and promotions of indexes in C i . We define closure

= C k , where k is the
smallest integer that satisfies C k = C k + 1 . In words, the closure of a workload W
is the set of all indexes that either are in the candidate set of a query in W or
can be derived from these candidates through a series of merging, splitting,
reduction, and promotion operations. Our goal is then to obtain a subset of
this closure that fits in the available storage and is as ecient as possible for
a given representative workload. Thus, the physical design problem can be
stated as follows:

( W )

Physical design problem: Given a workload W ={ Q 1 ,... , Q n } , where each
Q i is a SQL query or update, and a storage bound B , obtain the index configu-
ration C ={ I 1 ,... , I k } such that:
1. C ⊆ closure( W )

2. I ∈ C size( B

3. q i ∈ W cost( q i , C ) is minimized, where cost( q , C ) is the optimizer estimated cost
of query q under configuration C

I ) ≤

) just specifies all possible indexes
that can be considered as part of the final configuration, but in general it is
not feasible to evaluate each subset of closure(

Note that the definition of closure( W

) except for extremely simple
cases. In Chapter 6 we introduce different approaches to effectively traverse
the search space of a physical design problem instance and to obtain good
configurations in reasonable amounts of time.

W

4.4 Summary

• The search space for the physical design problem can be defined as

the closure of an initial set of query-specific candidates under suitable
transformations.