The logical search space of an initial query is all possible logical query trees that could be generated by the application of transformation rules to the initial query. The physical search space of a query is all possible plans that could be generated by the application of implementation and enforcement rules to the fully expanded logical search space.

Based on this understanding of rule application, the stages of Cascades optimization can be looked at in a little more detail.

Stages of Optimization

Cascades optimizes a query in three major steps: copy-in (to the memo), expanding the memo and copy-out (of the memo).

As shown in figure 2.1, after the original SQL query is parsed into a logical algebra query tree this initial query tree is copied in16 to the memo data structure. At this point the memo has a set of groups, each one corresponding to a node of the initial query tree. Each group will contain a single logical (or item) expression which contains the operator from the corresponding node in the initial query tree. This is figure 3.3a (the initial memo for the query in figure 3.2b).

Then the optimization process proceeds by performing various optimization tasks such as applying rules, optimizing expressions and optimizing groups. The order in which these tasks are performed is controlled by the search engine. The optimization tasks are performed primarily by applying rules (which we described above) and finding the best plan for each group,17 a procedure called find best, which we describe below. When rules are applied, new expressions are created and inserted into the memo structure and new groups are formed -- the memo structure is expanded.

16. Note that this procedure involves converting the nodes of the query tree into expressions in the memo structure.
17. In fact, under either algorithmic or heuristic pruning, the optimizer may not need to optimize every group in the memo.

 3. Fundamental Concepts:   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 28