Database Reference
In-Depth Information
Opt-SI
(W=(q
1
,
...
,q
n
):workload, C
0
:configuration)
01 i=0
02
while
(i<n)
03
if
(C
i
=0)
// see Cases A1, A2, A3 in Figure 10.6
04
if
(Case A1) C
k
=0 for i+1
≤
k
≤
j; i=j
else if
(Case A2) C
k
=1 for i+1
≤
k
≤
j; i=j
05
else
(Case A3) C
k
=0 for i+1
≤
k
≤
n; i=n
06
else
// C
i
=1, see Cases B1, B2, B3 in Figure 10.6
07
if
(Case B1) C
k
=1 for i+1
≤
k
≤
j; i=j
08
else if
(Case B2) C
k
=0 for i+1
≤
k
≤
j; i=j
09
else
(Case B3) C
k
=0 for i+1
≤
k
≤
n; i=n
10
FIGURE 10.5
Optimal algorithm for single-index case. (Used with per-
mission from Bruno, N. & Chaudhuri, S. In
Proceedings of the International
Conference on Data Engineering [ICDE]
, 2007.)
C
∗
for a given
workload
W
when we have information about the whole workload in ad-
vance. For that purpose, given a workload
W
and integers
i
0
,
i
1
, we define
(
We now explain how to obtain the optimal schedule
=
i
1
i
W
,
i
0
,
i
1
)
i
0
(
cost
(
q
i
,
0
)
−
cost
(
q
i
,
1
))
.If
W
is clear from the context, we
=
simply write
i
0
,
i
1
measures, for a subsequence of the work-
load, the cumulative difference in cost between the configuration that does
not contain index
I
(
C
=0) and the one that does contain it (
C
=1). That is,
executing queries
i
0
,
i
1
. Intuitively,
i
0
,
i
1
units more
expensive than doing it with the index (
C
=1). Therefore, we can see
(
q
i
0
,... ,
q
i
1
)
without the index (
C
=0) is
values
as the aggregated benefit (or penalty, for negative
values) of having the
index in the configuration for a given workload subsequence.
Figure 10.5 shows how to obtain the optimal schedule using
values. The
idea is to progressively calculate the optimal schedule
C
∗
for longer work-
load prefixes by using a case-by-case analysis on the subsequent behavior of
. Each new partial schedule is appended to the optimal prefix after deter-
mining whether a physical change would be beneficial. Consider case
A
2in
Figure 10.6. If the benefit of the index
I
at a point in the future is larger than
its creation cost (and is never negative), it makes sense to create
I
for such a
period of time.
We next show that algorithm
Opt-SI
determines the optimal configura-
tion schedule for an input workload
W
. From Figure 10.6 it follows that any
instance of
. Al-
gorithm
Opt-SI
therefore always advances
i
at each iteration and in doing so
determines longer prefixes of the optimal schedule. Eventually, it reaches
i
=
n
and terminates. We need to show that each determination in lines 4-6 and
8-10 leads to an optimal schedule. For instance, consider case
A
2 and suppose
that
C
i
=0. Algorithm
Opt-SI
appends the subschedule
satisfies one and only one among
{
A
1
,
A
2
,
A
3
,
B
1
,
B
2
,
B
3
}
C
O
=
(
1
,
1
,... ,
1
)
from
positions
i
+1 to
j
. Suppose there is an alternative schedule
C
A
that contains at
least one index deletion.
C
A
starts with a block of zero or more configurations
Search WWH ::
Custom Search