Database Reference
In-Depth Information
C as new
queries arrive. Therefore, eventually indexes that are not in C would
replace indexes in C . But now, the indexes we just dropped would start
increasing their bene f it values, while the ones we just created would
have a bounded residual value. We are caught in an endless oscilla-
tion, although the relative benefit of all indexes is similar. To address
this oscillation problem, we proceed as follows. Suppose that we are
updating the
I
C . At the same time, benefit
(
I
,
C
)
keeps growing for I
value of some index I
C with an additional
δ
but
b I . After updating to + δ , max would also be up-
dated appropriately, and residual (
residual (
I
,
C
) =
) would stay unchanged at b I .To
make I 's benefit explicit, in these situations we proportionally decrease
I
,
C
values of all indexes I
I ,
C so that the new value of benefit (
C
)
I ,
becomes max ( 0 , benefit (
C
) δ) . In other words, as current indexes
C keep being helpful, we adjust down the benefit of the remaining
indexes I
I
C , thus avoiding the previously described oscillations.
10.2.3 Putting It All Together
Figure 10.9 shows an online algorithm for physical design tuning. Each time
a query is optimized, we generate its AND/OR request tree T and obtain the
best index to implement each request. When a query is executed, we retrieve
its AND/OR request tree T and update
values for the indexes that are not in
C but optimally implement some request in T (lines 3 and 4). (We maintain
in H the set of candidate indexes that were optimal for some request in the
workload.) We also update
values for the indexes in C that were used
to implement some request in T (lines 5 and 6). If the input query was an
update, we refine
values in lines 7 and 8. Lines 1-8 are very ecient because
they manipulate only in-memory values. In line 9 we drop all indexes I
C
b I . In lines 10-18 we analyze the current candidate
indexes and determine if we can create (and optionally drop) indexes in C .
For that purpose, we initialize ITC = H and process each index in ITC .We
first obtain accurate values (line 13) and optionally find a subset of elements
from C that, if dropped, would make enough space for I to be created. For
eciency, we periodically sort the existing indexes by residual (
for which
max >
) so
that indexes that are either large or are almost dropping candidates are chosen
first. In lines 15-17 we adjust the benefit of I by subtracting the combined
residual values from C . If the resulting benefit is the largest seen so far, we
keep I as the best candidate. Finally, we lazily generate merged indexes and
include them in ITC for later analysis (line 18). After all indexes in ITC are
processed, we implement the best design change (if any) in lines 19-21.
We conclude this section by discussing some refinements and technical de-
tails of OnlinePT .
I
,
C
)/
size
(
I
Impact of online index creation. There is a period of time between
the asynchronous online index creation (line 21) and the time the index
Search WWH ::




Custom Search