The model's rule set can be thought of as defining the logical and physical search space of the optimizer. The memo is expanded to encompass the full logical and physical search space through the application of rules. The application of rules is a multistep process of finding a binding in the memo, evaluating a rule condition (if the rule has one) and (if the condition is satisfied) firing the rule -- putting new expressions in the memo. When the optimizer is done applying rules, the memo structure will have been expanded to the point that it conceptually represents the entire search space.15
Cascades rules come in three types: transformation rules, implementation rules and enforcement rules. In simple terms, transformation rules expand the logical search space, implementation rules expand the physical search space and enforcement rules, which are similar to implementation rules, insert physical operators to supply inputs that satisfy certain physical properties.
Rules always represent logical equivalence relationships [McKenna 93]. Recall that figure 3.2a and 3.2b are logically equivalent. This is because the relational join operator is associative. Hence a rule, in this case the left-associative transformation rule, could be used to transform a memo that included the query tree in figure 3.2a to a memo structure that now included the query tree in figure 3.2b.
Rules are specified with an antecedent (before pattern), a consequent (resulting partial query tree) and a condition. The antecedent specifies the pattern of operators required for there to be a binding of the rule. The consequent describes the new expressions that will be inserted into the memo structure if the condition is satisfied.
15. Due to algorithmic pruning, certain parts of the search space might not end up actually being represented in the memo structure. (Heuristic pruning, in contrast, will effectively reduce the search space considered by the optimizer.)
| 
Page 25
|