Database Reference

In-Depth Information

10.2.2.1

Index Interactions

(

,

,

)

(

,

,

,

)

Consider indexes
I
1
=

. If we do not consider the

inherent
index interaction
between
I
1
and
I
2
, we risk (1) underestimating

a

b

c

and
I
2
=

a

b

c

d

values for
I
2
by ignoring suboptimal—but better than existing—plans that

use
I
2
for requests served optimally by
I
1
, (2) overestimating

values for
I
1

after creating
I
2
because
I
2
can be a better alternative than the original one

if
I
1
is not present, and similarly, (3) underestimating
values for
I
2
if
I
1
is

removed from the current configuration. Since
Online-SI
relies on
values

to create and drop indexes, this problem can unexpectedly affect the resulting

physical design.

Recall that, for each index
I
that we consider in configuration
C
, we need

to accumulate the value
i
0
,
i
no
w
=
i
no
w

i
=
i
0
cost

(

q
i
,

C

−{

I

}
)
−

cost

(

q
i
,

C

∪{

I

}
)
.To

simplify the notation, we use
O
i
instead of
cost

(

q
i
,

C

−{

I

}
)
and
N
i
instead of

cost

. For each incoming query
q
i
, we obtain
O
i
(original cost for

q
i
when
I
is not present) and
N
i
(new cost of
q
i
when
I
is present) by using

getCost
as described earlier in this section. Instead of maintaining

(

q
i
,

C

∪{

I

}
)

=
(

O
i
−

, we exploit the equality
i
(

(
i

O
i
)
−
(
i

and maintain

these two aggregates separately. Additionally, we decompose each aggregate

N
i
)

O
i

−

N
i
)

=

N
i
)

into four terms,
i
O
i
=
O
0
+
O
1
+
O
2
+
O
U
and
i
N
i
=
N
0
+
N
1
+
N
2
+
N
U
, and

modify these values depending on
how
index
I
is used for each request coming

from the workload:

If
I
's columns are required in no particular order, we add
O
i
to
O
0
and

N
i
to
N
0
.

•

•

If
I
's key column is required (e.g., for an index seek), we add
O
i
to
O
1

and
N
i
to
N
1
.

•

If more than one key column in
I
is required (e.g., for a multicolumn

index seek or sort request), we add
O
i
to
O
2
and
N
i
to
N
2
.

•

If
I
is updated by the query, we add
O
i
and
N
i
from the update shell

to
O
U

and
N
U
.

Since we now have more granular information about each index usage, we can

handle index interactions more accurately (although still in an approximate

sense). For that purpose, we define the
usefulness level
of
I
1
with respect to

I
2
by the following table:

Level

Condition

−
1

I
1
columns do not include
I
2
columns.

0

I
1
columns include
I
2
columns.

1

Additionally,
I
2
's leading column agrees with
I
1
's.

2

Additionally,
I
2
is a prefix of
I
1
.

0, then
I
1

can (suboptimally) implement requests whose costs were stored in
O
m
and
N
m

components of

Informally, if the usefulness level of
I
1
with respect to
I
2
is
l

≥

for
I
2
(for
m

≤

l
). Note that this is an approximation and that

Search WWH ::

Custom Search