Database Reference
In-Depth Information
ultimate cost of an expression in fact depends on the actual configuration,
and thus any aggressive pruning might result in the loss of optimal plans for
some valid configurations.
5.4.1.1
Pruning the Search Space
A simple solution for this problem would be to simply remove the pruning
altogether. While this approach is correct, it might result in much longer
optimization calls. We can, however, improve this approach by eliminating
candidates that cannot be part of a solution
under any configuration
. One
of the diculties of handling
APR
operators is that they are really a spec-
ification of the required properties that any execution subplan must satisfy.
Therefore, there is no precise notion of the
cost
of an
APR
, since it depends
on the actual configuration. However, there are precise bounds on the cost of
such
APR
. On one hand, there exists a configuration with the right indexes
that makes a given
APR
execute as fast as possible. We can obtain such con-
figuration by analyzing the access path request as explained in Section 4.1.3.3.
Also, the configuration that contains no indexes results in the worst possible
implementation of an
APR
. Therefore, instead of having a single cost for each
physical operator in the tree, we maintain two costs, denoted
bestCost
(which
is the smallest possible cost of any plan implementing the operator tree un-
der any configuration) and
worstCost
(which is the largest possible cost of
any execution plan over all configurations). Once we calculate
bestCost
and
worstCost
values for leaf
APR
nodes, we can propagate such values easily
in the
CMEMO
. The
bestCost
of an operator is the local cost of the operator
plus the sum of the minimum
bestCost
of each child (
worstCost
values are
calculated analogously).
With the ability to calculate
bestCost
and
worstCost
values for arbitrary
physical operators in the
CMEMO
structure, we can rely on a relaxed pruning
rule. Specifically, every time that the partial
bestCost
of a
groupExpressions
g
is larger than the
worstCost
of a previous solution for the group under the
same optimization context, we can eliminate
g
from consideration.
5.4.1.2
Modifying the Enumeration Strategy
Figure 5.9 shows
OptimizeGroup
CPQO
, a modified version of the original
Op-
timizeGroup
procedure described in Figure 2.9, which produces the
CMEMO
structure. One difference in
OptimizeGroup
CPQO
is the input/output signa-
ture. The new version does not accept an upper bound
UB
as input, since
this is used in the original branch-and-bound pruning strategy, which we do
not rely on anymore. Also, the output of the new procedure consists not of a
single
groupExpression
but of the full set of
groupExpressions
for group
G
and
required properties
RP
. We also replace the original
winnerCircle
structure
with the more general
alternativePool
associative array, which returns the set
of all valid
groupExpressions
for a given group and required properties.
Search WWH ::
Custom Search