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

b C I

b C I Benefit (I, C)

Δ max

Δ min

Δ Δ

Residual (I, C)

FIGURE 10.8 values. (Used with permis-

sion from Bruno, N. & Chaudhuri, S. In Proceedings of the International Con-
ference on Data Engineering [ICDE] , 2007.)

Residual ( I , C ) and benefit ( I , C )

Finally, note that an additional kind of index interaction results from OR
nodes in the AND/OR request tree. In fact, only one of the multiple requests
with an OR parent node can be implemented in an execution plan. For this
reason, every time we create an index, the values of the remaining indexes
that were optimal for requests that shared an OR parent node need to be
updated. To address this issue, we maintain an additional value per index
that captures the fraction of ( i N i ) generated from “shared- OR nodes” and

update values appropriately.

Note that the techniques discussed in this section are heuristics designed to
eciently address the most common types of index interactions. Section 10.4
points to recent work that extends this approach by handling index interac-
tions in a more principled way.

10.2.2.2 Storage Constraints

After executing an input query, there might be indexes I that should be cre-
ated (i.e., indexes for which

− min >

b I ) but no available space and no

b I )

existing indexes to drop (i.e., indexes I

∈ max − >

.To
handle this common scenario, we define the residual cost of an index I un-
der configuration C as residual

C for which

= b I − ( max − )

( I , C ) .If residual ( I , C )< 0, I

should be dropped from C . Otherwise, residual( ) indicates how much slack

I has before being deemed a “dropping candidate.” Also, we define the benefit
for an index I

I , C

b I . Thus, if benefit( ∈ C as benefit( I , C ) = ( − min ) − I , C )> 0,

index I should be added. Also, positive values of benefit( ) indicate the

“excess in confidence” for adding I to C (see Figure 10.8 for an illustration).
Suppose that benefit(

I , C

I , C )> 0 for some I ∈ C , but no space is available for

creating I and, for all indexes I ∈ I , )> 0 (i.e., we cannot drop

any existing index). Now, if we find a subset of indexes C ⊆

C , residual( C

C such that I ∈ C

I ,

residual , we know that the benefit of creating I exceeds

the combined slack of indexes in C . We can then update C = C

( C )< benefit ( I , C )

C ∪{

.
There might be many choices for I and C at any time. We next explain how
we can choose among these alternatives.

− I }

Addressing the oscillation problem. Suppose that we identify a set of
indexes that are useful but do not fit in the available space. We know
that, by definition, residual is upper bounded by b I for indexes

( I , C )