Database Reference
In-Depth Information
and also to retrieve an additional column
c
, which is eventually needed at
higher levels in the execution plan. In general, the optimal execution plan
under
C
=
−{
}
might be arbitrarily different from that under
C
.How-
ever, we can always
locally transform
P
into
P
by adjusting the execution
subplan that uses
I
so that it depends only on indexes in
C
. To simplify the
presentation, we define the
internal subplan
of an execution plan
p
as the por-
tion of
p
that remains after removing all index-based execution subplans (i.e.,
scans, seeks, index intersections, and RID lookups). An important property of
the local transformations previously described is that the cost of the internal
subplan does not vary across transformations, because the transformed sub-
plan returns the same sequence of tuples as the original subplan. Therefore,
estimating the cost of the transformed plan can be done by just comparing
the original and transformed index-based subplans. Since
P
was optimal, the
local transformation would result in a less ecient plan
P
. However, we know
that the locally transformed plan
P
is valid under
C
, and therefore its cost
is an upper bound on the cost of the optimal plan for
C
, as desired. As an
example, the alternative plan at the right of Figure 5.4 locally transforms the
original plan so that it uses
I
=
C
I
. To do that,
it additionally looks up the primary index to obtain the required
c
column
and returns the same sequence of tuples as the original subplan in
P
.
So far we discussed examples for which
C
has strictly fewer indexes than
C
. In general, the configuration
C
that we try to approximate might have
additional indexes not found in a previously evaluated configuration
C
.Of
course, we can ignore indexes in
C
−
R
(
a
|
b
)
instead of
I
=
R
(
a
|
b
,
c
)
C
, proceed as before, and still obtain
an upper bound on the cost of
q
under
C
. The upper bound would be looser
in this case, because we are not leveraging indexes in
C
−
C
. In general, we
have to consider each subplan that is defined over a table associated with at
least one index in
C
−
C
and locally transform such execution subplans by
leveraging all indexes in
C
.
To summarize this discussion, the algorithm in Figure 5.5 obtains an up-
per bound on the cost of a query
q
under a configuration
newC
, leveraging
information on past optimizations over configurations
CS
but without issuing
a new optimization call. We first obtain the optimal execution plan
P
for
q
under each configuration
C
∈
CS
. We then transform some index-based sub-
plans of
P
depending on the indexes in both
C
and
newC
. Specifically, for each
subplan
p
of
P
that uses an index present in
C
but not available in
newC
,we
construct an alternative, equivalent plan that uses only available indexes in
newC
. Similarly, for each subplan
p
of
P
over a table that has indexes in
newC
but not in
C
, we try to improve the current plan by additionally using indexes
in
newC-C
. We keep the best transformed execution plan for every previous
configuration and return its expected cost. This returned plan is valid and
should be considered by the optimizer. However, the optimizer might return
some even better execution plan for
newC
, and that is the reason that the
execution cost of the returned plan is an upper bound of
cost
(
,
)
.
q
newC
Search WWH ::
Custom Search