Database Reference
In-Depth Information
4.2.2.2
Splitting
Index splitting aims to introduce suboptimal index intersection plans by re-
arranging overlapping columns of existing (wider) indexes. Consider
I
1
=
I
2
) produces
a common index
I
C
and at most two additional residual indexes
I
R
1
and
I
R
2
.
The idea is that we could replace usages of index
I
1
(respectively,
I
2
)bya
less ecient index intersection between
I
C
and
I
R
1
(respectively,
I
R
2
), or RID
lookups over
I
C
's result if
I
R
1
(respectively,
I
R
2
) does not exist. Specifically,
we define
I
C
R
(
K
1
|
S
1
)
and
I
2
=
R
(
K
2
|
S
2
)
. Splitting
I
1
and
I
2
(denoted
I
1
⊗
S
2
, provided
that
K
C
is nonempty (index splits are undefined if
K
1
and
K
2
have no com-
mon columns). If
K
1
and
K
C
are different,
I
R
1
=
=
R
(
K
C
,
S
C
)
, where
K
C
=
K
1
∩
K
2
and
S
C
=
S
1
∩
R
(
K
1
−
K
C
|
I
1
−
I
C
)
and if
K
2
and
K
C
are different,
I
R
2
=
R
(
K
2
−
K
C
|
I
2
−
I
C
)
. Consider, as an exam-
ple,
I
1
=
R
(
a
,
b
,
c
|
d
,
e
,
f
)
,
I
2
=
R
(
c
,
a
|
e
)
, and
I
3
=
R
(
a
,
b
|
d
,
g
)
. In this case,
I
1
⊗
I
2
={
I
C
=
R
(
a
,
c
|
e
),
I
R
1
=
R
(
b
|
d
,
f
),
I
R
2
=
R
(
d
)
}
. In turn, we have that
I
1
⊗
I
3
={
I
C
=
R
(
a
,
b
|
d
),
I
R
1
=
R
(
c
|
e
,
f
)
}
.
4.2.2.3
Reduction
Index reductions transform an index into another one with fewer columns.
Specifically, consider
I
=
R
(
K
|
S
)
. We can reduce
I
with respect to any subset
), to obtain a new index with
K
as key columns
and no included columns. That is,
K
K
)
⊆
K
(denoted
ρ(
I
,
K
)
=
K
)
. The reduced index can
be used to answer requests for which
I
was useful (generally requiring RID
lookups to get the remaining columns in
K
ρ(
I
,
R
(
K
) Alternatively, rather
∪
S
−
than allowing all possible subsets
K
⊆
K
, a simpler family of reductions
considers only prefixes of
K
. Then, a reduction is specified by an integer
k
,
and
ρ(
I
,
k
)
=
R
(
K
)
, where
K
is a prefix of
K
of length
k
.
4.2.2.4
Promotion
Any index
I
=
R
(
K
|
S
)
can be promoted to a clustered index with key columns
)
provides the same query capabil-
ities as the original index
I
. However, since we can get one clustered index
“for free” for each table, promoting one index to a clustered index results in
new opportunities for other indexes to be part of the final configuration.
K
, denoted
(
I
)
. The clustered index
(
I
4.3 Defining the Search Space Using Closures
The transformations in the previous section provide a framework to charac-
terize the search space for the physical design problem with input workload
W
and use it to further refine our problem statement. Let
cand
(
Q
)
be the
Search WWH ::
Custom Search