Database Reference
In-Depth Information
Online-SI
(q
i
:
query, C:current configuration)
// Initially,
=
min
=
max
=0
1
δ
=
cost
(
q
i
,
0
)
−
cost
(
q
i
,
1
)
2
=
+
δ
3
min
= MIN(
min
,
)
max
= MAX(
max
,
)
4
if
(C=0 and
−
min
≥
b
I
)
max
=
; C=1
5
// create index
if
(C=1 and
max
−
≥
b
I
)
min
=
; C=0
// drop index
6
FIGURE 10.7
Online algorithm for single-index case. (Used with permis-
sion from Bruno, N. & Chaudhuri, S. In
Proceedings of the International Con-
ference on Data Engineering [ICDE]
, 2007.)
Opt-SI
would have gathered “from the future” has already passed.
We now bound the suboptimality of
Online-SI
by presenting a
worst-case scenario for which
Online-SI
keeps creating and drop-
ping index
I
as often as possible without ever exploiting it. Consider
workload
W
=
(
q
1
,
q
2
,
q
1
,
q
2
,...)
, where
cost
(
q
1
,
0
)
=
+
b
I
,
cost
(
q
1
,
1
)
=
,
C
∗
for
W
cost
(
q
2
,
0
)
=
, and
cost
(
q
2
,
1
)
=
+
b
I
. The optimal schedule
is
. In other words, index
I
is built before each in-
stance of
q
1
and dropped before each instance of
q
2
. The cost of such
a schedule is
(
C
0
=0
,
1
,
0
,
1
,
0
,...)
(
+
)
(
q
1
,
q
2
)
b
I
2
for every pair
in
W
. The schedule pro-
C
onli ne
=
(
,
,
,
,
,
,...)
duced by
Online-SI
is
C
0
=0
0
1
0
1
0
. The cost of such
a schedule is
(
+
b
I
)
+
b
I
+
(
+
b
I
)
,or(3
b
I
+
2
) for every pair
(
q
1
,
q
2
)
, C
∗
)
3
b
I
+
2
in
W
. Then, the ratio
cost
(
W
, C
onli ne
)/
cost
(
W
is
b
I
+
2
<
3 since
>
0. Therefore, algorithm
Online-SI
is three competitive (i.e., no
worse than three times the optimal algorithm
Opt-SI
).
10.2.2 Multiple-Index Scenario
We now extend the ideas of the previous section to multiple indexes. For that
purpose, we first revise the definition of
values to reflect this scenario. For
a workload
W
, a configuration
C
, an index
I
, and integers
i
0
,
i
1
, we define
i
1
(
W
,
C
,
I
,
i
0
,
i
1
)
=
cost
(
q
i
,
C
−{
I
}
)
−
cost
(
q
i
,
C
∪{
I
}
)
i
=
i
0
If
W
,
C
, and
I
are clear from the context, we simply write
values, we can generalize
Online-SI
. For each query
q
i
we execute
Online-SI
in parallel for each index
I
i
0
,
i
1
. Using
. This
is a reasonable generalization for the case of multiple indexes but suffers from
some deficiencies.
∈{
ρ
)
:
ρ
∈
getRequests(
q
i
)
}
getBestIndex(
Search WWH ::
Custom Search