Database Reference
In-Depth Information
Update statements also require that all relevant indexes be maintained.
Specifically for
Q3
, any index on
R
that contains column
D
needs to be updated.
Consider now a workload
{
}
. The optimal index for
Q2
,
I
2
, contains
column
D
and thus needs to be maintained. Consider now index
I
5
=R(A)
.
Query
Q2
can use index
I
5
in conjunction with RID lookups to obtain the result
(assuming that few tuples satisfy the predicate on
A
). Using
I
5
to evaluate
Q2
is certainly worse than using
I
2
. However,
I
5
does not contain column
D
and
therefore does not need to be maintained for
Q3
. It certainly can be the case
that a configuration
{
Q2, Q3
I
4
}
due to the update statement.
In this case,
I
5
, which was not optimal for any query in the workload, would
be part of the optimal configuration.
I
5
,
I
4
}
is better than
{
I
2
,
4.2.2 Index Transformations
As described already, some situations require considering candidate indexes
that are not part of the optimal candidate set of any query in the workload.
In this section we formally describe a set of transformations that can gener-
ate these derived indexes from an initial candidate set. The transformations
exploit knowledge about how indexes are used in the DBMS. To simplify the
notation, we assume that if
S
1
and
S
2
are sequences, the expression
S
1
∩
S
2
(similarly,
S
1
−
S
2
) returns the sequence that has elements in the intersection
(similarly, difference) of
S
1
and
S
2
in the same order
as they appear in
S
1
.
4.2.2.1 Merging
Index merging is an operation that takes two input indexes and produces a
new index that eliminates redundancy resulting from shared columns. The
resulting index is smaller than the two input indexes combined while preserv-
ing, as much as possible, their querying capabilities. We define the (ordered)
merging of two indexes
I
1
and
I
2
as the best index that can answer all requests
that either
I
1
and
I
2
do and can be eciently used to seek tuples in all cases
that
I
1
can (some requests that can be answered by seeking
I
2
might need
to scan the merged index, though). Specifically, we define the merging of
I
1
and
I
2
(denoted
I
1
⊕
I
2
) as an index that has all key columns in
I
1
as key
columns and the remaining columns in
I
2
as well as the included columns in
I
1
as included columns. That is, given
I
1
=
R
(
K
1
|
S
1
)
and
I
2
=
R
(
K
2
|
S
2
)
,we
define
I
1
⊕
I
2
=
R
(
K
1
|
(
S
1
∪
K
2
∪
S
2
)
−
K
1
)
. As an optimization, if
K
1
is a prefix
of
K
2
, we define
I
1
⊕
I
2
=
R
(
K
2
|
(
S
1
∪
S
2
)
−
K
2
)
. For instance, consider indexes
I
1
=
R
(
a
,
b
|
c
,
d
)
and
I
2
=
R
(
b
,
d
,
e
|
f
)
. Then,
I
1
⊕
I
2
=
R
(
a
,
b
|
c
,
d
,
e
,
f
)
and
I
2
⊕
I
1
=
R
(
b
,
d
,
e
|
a
,
c
,
f
)
.
Search WWH ::
Custom Search