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

adaptiveMerge (ES: enumeration space)
1 NS=ES
2 while (NS =∅ )

3 ES=ES ∪ NS; NS = ∅

4 foreach (I1, I2 in ES)

5 I12 = merge(I1, I2)

if (I12 is not valid or I12 ∈ ES) continue

6

if (cost(W, ES- { I1,I2 } ∪ { I12 } )< δ · cost(W, ES))

7

NS = NS ∪ { I12 }

8

return ES

9

FIGURE 6.2 Adaptive merging of indexes to obtain the enumeration

space.

6.1.1 Hill-Climbing Approach
We now describe a hill-climbing approach, which we call greedy(m,B) . The
greedy(m,B) approach results in a spectrum of alternatives that includes the
exhaustive enumeration strategy at one extreme and a pure greedy strategy
at the other. Rather than exhaustively traversing all subsets of the enumer-
ation space, greedy(m,B) starts by evaluating all configurations with at most
m indexes and then continues considering the remaining indexes greedily.
Figure 6.3 illustrates this approach. Lines 1-4 consider all subsets of the enu-
meration space ES and obtain the configuration C that fits B and results in the
smallest execution cost for the workload W . Then, lines 5-11 greedily attempt
to add a single index to C that improves the cost the most (if possible). Lines
7-9 consider each index in the enumeration space that is not already part of C
and keep track, in newC , of the configuration that fits in B and improves over

greedy-mB (ES: set of indexes, m:integer, B:size constraint)
01 C = null
02 foreach (valid CS ⊆ ES such that |CS| ≤ m and size(CS) ≤ B)
03

if (cost(W, CS) < cost(W, C)) // cost(W,null)= ∞

04 C = CS
// C contains the best configuration with at most m indexes.
05 while (true)
06 newC = C
07 foreach (I in ES-C such that size(C ∪ { I } ) ≤ B)
08 if (cost(W, C ∪ { I } ) < min(cost(W, newC))
09 newC = C ∪ { I }
10 if (newC = C) break
11 C = newC
12 return C

FIGURE 6.3 Greedy(m,B) approach to traverse the enumeration space.