[Lee 88] builds on the ideas of [Lohman 88] and represents some of the main ideas underlying the Starburst optimizer. The goal was to use on the ideas of the System R optimizer with the flexibility and other advantages of the rule-based approach. The rule-based approach "cleanly separates the plan generation cost estimation and search strategy components to facilitate extensibility" [Lee 88]. Lee, in comparing the rules used in STARBURST optimizer to the productions used in Yacc [UNIX 84], states:
"(our rules) have conditions of applicability and parameters, which productions do not permit. Furthermore, grammars are typically used by parsers to find one sequence of terminals that match an input stream of tokens, whereas we wish to generate all such sequences."

           The advantage of the grammar-based approach over the top-down approach, is that you can more easily limit, and more efficiently search, the search space.

Exodus and Volcano

           Exodus [Graefe 87] and Volcano [McKenna 93] used a top-down, rule-based search strategy, a large search space and a model based on logical and physical properties. Exodus, was developed as part of the Exodus Extensible Database System at Wisconsin. The Exodus optimizer read a model description file which described logical and physical operators and rules. The primary data structure for Exodus was called a "mesh" (as distinguished from a tree). Each node in the mesh, represented a logical expression and contained a list of logically equivalent logical and physical expressions. The mesh is essentially the same as the memo data structure in Cascades.

           Exodus had logical and physical properties called operator and method properties, respectively. Exodus had a task structure, listing rules that needed to be applied and allowed some search strategies in order to prune or order the application of rules.


4. Related Work:    <System R> <Bottom Up> <Join Order Heuristics> <Query Blocks> <Rules> <Top Down> <Volcano> <Phases> <Specialized Techniques> <Unique Rules>
  4.1: Left-Deep  

 Page 13