Notice also the leaf designations in the before pattern. These are like wildcard indicators -- they indicate that any group will match at this particular location in the pattern. The consequent will also usually contain leaves. The group matching a particular leaf in the antecedent will generally become a group at one of the leaf positions in the consequent.

           When part of the memo structure matches this pattern a binding is made -- to the particular expressions in the memo structure that match the pattern. The binding is used to evaluate the condition and to form the consequent. After the binding is made the condition (if any) is evaluated. If the condition is satisfied, or there is no condition, the rule is fired. Based on the binding and the consequent query tree, new expressions are created and inserted into the memo structure.

           In the memo of figure 3.3, consider the left associativity rule. This rule would have six bindings -- two each for the first, fourth and sixth expression in group 4. Let's look at the binding that consists of the first expression in group 4 (EQJOIN 7 1) and the first expression in group 7 (EQJOIN 0 3). Any binding of the left associativity rule will result in the firing of the rule, since the rule has no condition that must be satisfied. The firing of the rule would result in the generation of the third expression in group 4 (EQJOIN 0 6) and the first expression in group 6 (EQJOIN 3 1). The expression corresponding to the the top node of the consequent will always be inserted in the group which contains the expression corresponding to the top node of the antecedent.

           Note that firing the associative rule on the six bindings results in expressions which are already in the memo shown in figure 3.3 (because it is already fully logically expanded). In general, it is possible for rules to generate expressions which are already in the memo. Efforts to design rule sets to avoid this are discussed in section 5, Related Work.

           Now consider an implementation rule that says that a physical operator called INDEXED_FILTER implements the logical operator SELECT. This rule would likely include the condition that an index which matches the select predicate must exist in the stored database. This implementation rule will fire only if this condition is met. This condition would help to assure that the optimizer only produces legal, well-formed plans. After the consequent is formed, the corresponding expressions are inserted into the memo and, in effect, the represented search space (of all possible plans) is increased.

3. Fundamental Concepts:	<Models> <Log> <Query Trees> <Groups> <Memo> <Phys> <Item> <Rules> <Opt Stages> <Find Best> <Complexity>   3.1: EQJOIN     3.2a: Query Tree     3.2b: Equiv.     3.3a: Init Memo     3.3b: Memo     3.3c: Key     3.4: Complexity     3.5: Phys Memo     3.6: Plan     3.7: Pred.     3.8: Op Types     3.9: Rule

		Page 27