Database Reference
In-Depth Information
Specifically, given the current configuration
C
, we generate the following con-
figurations:
•
Merging:
C
−{
I
1
,
I
2
}∪{
I
1
⊕
I
2
}
for each pair of compatible indexes (
I
1
,
I
2
)in
C
.
•
Splitting:
C
−{
I
1
,
I
2
}∪{
I
1
⊗
I
2
}
for each pair of compatible indexes (
I
1
,
I
2
)in
C
.
•
−{
}∪{
ρ(
,
)
}
Reduction:
C
I
I
K
for each index
I
in
C
and prefix
K
of
I
.
•
Promotion:
C
for each index
I
in
C
, where
I
cl
is
the clustered index of
I
's table (if defined).
−{
I
}−{
I
cl
}∪{
(
I
)
}
•
Deletion:
C
}
for each index
I
in
C
. If the removed index is a
clustered index, it is replaced by the corresponding table heap.
−{
I
))
,
where
n
is the number of indexes in
C
, and
m
is the maximum number of
columns in an index in
C
. In real situations this number is likely to be much
smaller, because indexes are spread throughout several tables (and therefore
merging and splitting are valid for only a subset of cases) and also because
not all reductions need to be considered. To clarify the latter point, consider
index
I
The number of transformations for a given configuration
C
is
O(
n
·
(
n
+
m
=
R
(
a
,
b
,
c
,
d
,
e
)
and the single-query workload:
SELECT a, b, c, d, e
FROM R
WHEREa=10
In this situation, the only useful reduction for the index is
I
=
(
)
, since
any other prefix of
I
is going to be both larger than
I
and less ecient for
processing the query.
R
a
6.2.1.4
Ranking Candidate Configurations
After generating all candidate configurations from the current one via trans-
formations, we need to rank them in decreasing order of “promise,” so that
better configurations are chosen and explored first. For that purpose, we es-
timate both the expected cost of the workload and the expected size (i.e.,
the storage constraint) of each resulting configuration. While estimating sizes
can be done eciently, estimating costs is more challenging. The reason is
that often there are several candidate configurations to rank, and the cost
of performing what-if optimization calls (even when using the optimizations
described in Sections 5.3 and 5.4) is too costly. To reduce overheads, we can
use the upper-bound approach of Section 5.2.2 and obtain upper bounds on
the cost of queries for each candidate transformation.
Once we obtain estimates for both the optimizing function and the devia-
tion from the storage constraint for each of the alternative configurations, we
need to put together these values to rank the different candidate transforma-
tions. Consider some transformation that goes from the current configuration
Search WWH ::
Custom Search