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

Original Memo
Structure

C-PQO Memo
Structure

C-PQO Memo
Structure

EP 4

APR 4

APR 1 EP 1

P 4

EP 2

EP 3

APR 2 APR 3

P 1

P 3

P 2

Configuration

(a) Original MEMO. (b) CMEMO with APR s. (c) Inferring execution plans.

FIGURE 5.8 High-level overview of CPQO . (Used with permission from
Bruno, N. & Nehme, R. In Proceedings of the ACM International Conference
on Management of Data [SIGMOD], 2008.)

P i is independent of the configuration and corresponds to all combinations of
internal subplans considered by the optimizer.
Leveraging the instrumentation approach described in Section 4.1.3, we cre-
ate a new physical operator, which we call APR , that contains an access path
request N

. Then, we modify the generation of substitutes
for all the rules that are related to access path selection so that they return
an APR operator rather than an actual physical execution subplan. In this
way, we make access path selection rules configuration independent, and we
do not miss any potential execution subplan (see the resulting MEMO , denoted
CMEMO , in Figure 5.8b). Intuitively, the information in APR nodes encodes
the properties satisfied by any physical execution subplan implementing the
logical operator tree that triggered the implementation rule. Note that this
mechanism results in the following two crucial properties. First, the leaf nodes
in the resulting CMEMO are always APR physical operators. Second, there are
no rules in the optimizer that depend on the specific configuration, so query
optimization is truly configuration independent.
Whenever we want to reoptimize the query under a different configuration
we can just focus on the APR nodes and infer small execution subplans that
satisfy their requirements under the new configuration (obtained as described
in Section 5.2.2 and denoted EP 1 in Figure 5.8c). We can then extract the
best execution plan from the resulting CMEMO (whose bulk was precomputed)
in a much more ecient manner.

× ( T , E , R , P , O , A )

5.4.1 Obtaining the CMEMO Structure
Transformation-based, top-down optimizers such as Cascades use a variant of
branch-and-bound pruning to avoid exploring alternatives that are guaranteed
to be suboptimal. Specifically, line 7 in Figure 2.9 (see Chapter 2) completely
discards a groupExpression —without even optimizing all its children—if it
costs more than the upper bound UB . While this pruning makes sense in
a traditional optimizer, it would be wrong to apply it for CPQO since the