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

more than UB , and satisfies the required properties RP . This task im-
plements memoization by caching the best execution plan for a given
set of required properties in the winner circle of the group . The winner
circle of a group is an associative array that returns the best plan found
so far for a given set of required properties. Subsequent calls to Op-
timizeGroup with the same required physical properties would return
immediately with the best plan or a failure (depending on the value
of UB ). Optimizing a group involves exploring the group (see Explore-
Group task), and then applying all implementation rules (see ApplyRule
task) to produce all the candidate physical operators that implement
the logical counterparts in the group .
ExploreGroup: A group is explored by iteratively exploring each logical
groupExpression in the group (see ExploreExpr task).
ExploreExpr: Exploring a logical groupExpression generates all logically
equivalent alternatives of the input groupExpression by applying ex-
ploration rules (see ApplyRule task). This task also uses memoization
to avoid repeated work. Consider a join reordering rule that transforms
groupExpression G 1 into G 2 . When eventually exploring G 2 , it would
not make sense to apply join reordering again, since we would obtain
G 1 back. ExploreExpr uses a bitmap, called pattern memory , that keeps
track of which transformation rules are valid and which ones should not
be applied.
ApplyRule: In general, each rule is a pair of an antecedent expression (to
match in the MEMO ) and a consequent expression (to generate and intro-
duce back in the MEMO ). On one side, exploration rules transform logical
operator trees into equivalent logical operator trees and can range from
simple rules like join reordering to more complex ones like pushing ag-
gregates below joins. An example of an exploration rule is the join as-
sociativity rule “ JOIN (

g 3 ) .” ∗ On
the other side, implementation rules transform logical operator trees into
hybrid logical/physical trees by introducing physical operators into the
MEMO . Implementation rules range from simple ones like transforming a
logical join into a physical hash join to very complex ones that generate
index strategies, discussed later. The ApplyRule task can be broken down
into four components. First, all the bindings for the rule antecedent are
identified and iterated over one by one (for complex rules, there can
be different ways of matching the antecedent of the rule with operator
trees in the current group ). Second, the rule is applied to each binding
generating one or more new expressions (for the previous rule, there
is a single substitute per rule application, but in general there might

g 1 , JOIN ( g 2 , g 3 )) → JOIN ( JOIN ( g 1 , g 2 ),

∗ This is a very simple exploration rule. More complex rules, especially implementation
rules, have right sides that cannot be expressed as succinctly.