Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 39

OptimizeGroup (G: group, RP: properties, UB: double)
return best groupExpression for G under UB cost satisfying RP
01 p = winnerCircle[G,RP]
02 if ( p is not NULL )
if (p.cost < UB) return p
else return NULL
03 bestP = NULL // No precomputed solution, enumerate plans
04 foreach enumerated physical groupExpression candP
05

candP.cost = localCost( candP )

foreach input p i of candP

06

if (candP.cost ≥ UB) continue to 4 // out of bound

07

08 G i = group of p i

RP i = required properties for p i

bestP i = OptimizeGroup (G i ,RP i , UB-candP.cost)

09

if (bestP i = NULL) continue to 4 // no solution

10

11 candP.bestChild[i] = bestP i
12 candP.cost += bestP i .cost
// Have valid solution, update state
13 if (candP.cost < UB and candP satisfies RP)
bestP = candP
UB = candP.cost
14 winnerCircle[G,RP] = bestP
15 return bestP

FIGURE 2.9 Simplified algorithm for the OptimizeGroup task.

far. Finally, after all candidates are processed, line 14 adds the best plan to
the winner circle for G and RP , and line 15 returns such plan.

2.3.3.3 The Rule Set

A crucial component in a Cascades-based optimizer is the rule set. In fact, the
set of rules available to the optimizer is one of the determining factors in the
quality of the resulting plans. In the rest of this section we discuss details on
a small subset of implementation rules that deal with access path selection,
since these will be relevant in subsequent chapters.
One of such rules transforms a logical expression consisting of a selection
over a single table ∗ into a physical plan that leverages available indexes (can-
didate plans include index scans, record id (RID) intersections, and lookups,
among others). After binding the logical operator tree, this rule identifies the
columns that occur in sargable predicates (i.e., predicates that can leverage
index seeks), the columns that are part of a required sort property, and the

∗ The antecedent groupExpression is typically obtained by applying other rules (e.g., pushing
selections under joins).