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.
| 
Page 28
|