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