Continuous Physical Database Design - Automated Physical Database Design and Tuning - page 195

OnlinePT (q i :query, C:current configuration)
// Initially, H= ∅ (no candidate indexes to create)
01 AOT = getRequests(q i )
// Update values
02 foreach request ρ in AOT
03 I = getBestIndex( ρ )
04 if (I ∈ C) H=H ∪{ I } ; update for I
05 I used = index in C used to implement ρ
06 update for I used
07 if q i is UPDATE on table T
08

, N U to for each index over T
// Remove bad indexes
09 drop I ∈ C if residual(I,C) ≤ 0
// Analyze candidate indexes to create
10 ITC = { I ∈ H such that benefit(I,C) > 0 }

add O U

// candidates

11 bestI = NULL; bestB = 0; bestC'= ∅
12 foreach index I in ITC
13 B I = -b I

14 get prefix C' of C in residual(I',C)/size(I') order such

that size(C-C' ∪ { I } ) fits in the available storage

B I =B I - I ∈ C 15 residual(I',C)

16 if (B I ≥ bestB)
17 bestI = I; bestB = B I ; bestC'= C'
18 ITC= ITC ∪ { merge(I, I'): I' ∈ C ∪ ITC }
// Create indexes (optionally removing others)
19 if (bestI is not NULL)
20

drop I' ∈ C' from C

create bestI in C; H= H- { bestI }

21

FIGURE 10.9 Online physical design tuning algorithm. (Used with per-
mission from Bruno, N. & Chaudhuri, S. In Proceedings of the International
Conference on Data Engineering [ICDE] , 2007.)

is ready to be used. During this time, queries cannot use the index, but
OnlinePT must “understand” that the index is being created and not
consider it again for creation. We achieve this by removing the index
from H as soon as the creation begins, so it is not considered again in
ITC at the next iteration. However, we keep updating its

value as
new queries arrive. If the bene f it value of the index being created drops
more than b I due to updates, we abort the index creation.
Supporting statistics. The cost inference in the algorithms would cer-
tainly benefit from statistics on the relevant columns. However, we can-
not greedily create statistics due to the additional overhead that this
would impose on the DBMS. As a middle ground, we can trigger asyn-
chronous statistics creation tasks on the key columns of a candidate in-
dex in H whenever

− min is larger than a fraction of b I (e.g., 0 b I ).

. 8 ·