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