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
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
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