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.
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 220.127.116.11.
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
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.
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.