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