Designing a Cost Model - Automated Physical Database Design and Tuning - page 94

Note that if at any moment the current bestCost of candP becomes larger than
the worstCost of a previously calculated solution, the candidate is discarded
and the next one is considered (line 7). Otherwise, after candP is completely
optimized, line 13 adds it to the candidate pool for the G and RP , and line
14 updates the upper bound with the worstCost value of candP if applicable.
After all candidates are explored, line 15 updates the alternativePool array,
and line 16 returns the candidate groupExpressions .

5.4.1.3 Generating the CMEMO Structure
After executing OptimizeGroup CPQO on the root node of the initial MEMO
with the global set of required properties, we need to prepare the output of
a CPQO optimization. We do so by extracting an AND/OR subgraph of phys-
ical operators from the final MEMO . Each node in the output graph can be
of one of two classes. On one hand, AND nodes contain the actual physical
groupExpressions along with their bestCost and localCost values (the local-
Cost value is the one defined in line 5 of Figure 5.9 and can be obtained back
by subtracting the bestCost values of the best children of a groupExpression
from its own bestCost value). Each outgoing edge of an AND node represents
a child of the corresponding groupExpression and goes into an OR node. OR
nodes, in turn, correspond to candidate choices, represented by outgoing edges
into other AND nodes. Additionally, each OR node distinguishes, among its
choices, the one that resulted in the minimum bestCost value (i.e., the child
that contributed to candP.bestCost in line 12 of Figure 5.9). Finally, we
add a root OR node that has outgoing edges toward every AND node that
corresponds to a groupExpression in the root node of the final MEMO satis-
fying the original required properties (since there might be many alterna-
tives to implement the query, this root OR node represents the highest-level
choice). Figure 5.10 shows a sample AND/OR graph induced by a partial MEMO

Hash Join

OR OR

... ...

APR 2

Filter

Group 3: 1. Join(2,7) 2. Hash Join(2.{2.3}, 7.{1,2.3}) ...

OR

Group 2: 1. Select ?? (1) 2. Filter(1.{2,3,4}) 2. APRs ...

3. APR 2

Group 1: 1. Get R 2. APR 1 4. Sort(1.{2,3}) ...

APR 1 APR 2 Sort

(a) Partial CMEMO.

OR

(b) AND/OR graph.

FIGURE 5.10 AND/OR graph induced from a MEMO .