Changing the rules: transformations for rule-based optimizers

ABSTRACT

Rule-based optimizers are extensible because they consist of modifiable sets of rules. For modification to be straightforward, rules must be easily reasoned about (i.e., understood and verified). At the same time, rules must be expressive and efficient (to fire) for rule-based optimizers to be practical. Production-style rules (as in [15]) are expressed with code and are hard to reason about. Pure rewrite rules (as in [1]) lack code, but cannot atomically express complex transformations (e.g., normalizations). Some systems allow rules to be grouped, but sacrifice efficiency by providing limited control over their firing. Therefore, none of these approaches succeeds in making rules expressive, efficient and understandable. We propose a language (COKO) for expressing an alternative form of input to a rule-based optimizer. A COKO transformation consists of a set of declarative (KOLA) rewrite rules and a (firing) algorithm that specifies their firing. It is straightforward to reason about COKO transformations because all query modification is expressed with declarative rewrite rules. Firing is specified algorithmically with an expressive language that provides direct control over how query representations are traversed, and under what conditions rules are fired. Therefore, COKO achieves a delicate balance of understandability, efficiency and expressivity.

REFERENCES

• 1: Ludger Becker , Ralf Hartmut Güting, Rule-based optimization and query processing in an extensible geometric database system, ACM Transactions on Database Systems (TODS), v.17 n.2, p.247-303, June 1992 [doi>10.1145/128903.128905]
• 2: M. J. Carey , David J. DeWitt , G. Graefe , D. M. Haight , J. E. Richardson , D. T. Schuh , E. J. Shekita , S. L. Vandenberg, The EXODUS extensible DBMS project: an overview, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 3: M. Chemiack Translating queries into combinators. September 1996.
• 4: Mitchell Frederic Cherniack , Stan Zdonik, Building query optimizers with combinators, 1999
• 5: Mitch Cherniack , Stanley B. Zdonik, Rule languages and internal algebras for rule-based optimizers, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.401-412, June 04-06, 1996, Montreal, Quebec, Canada
• 6: Béatrice Finance , Georges Gardarin, A Rule-Based Query Rewriter in an Extensible DBMS, Proceedings of the Seventh International Conference on Data Engineering, p.248-256, April 08-12, 1991
• 7: Béatrice Finance , Georges Gardarin, A rule-based query optimizer with multiple search strategies, Data & Knowledge Engineering, v.13 n.1, p.1-29, Aug. 1994 [doi>10.1016/0169-023X(94)90045-0]
• 8: G. Graefe. The Cascades framework for query optimization. Data Engineering Bulletin, 18(3): 19-29, September 1995.
• 9: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 10: John V. Guttag , James J. Horning, Larch: languages and tools for formal specification, Springer-Verlag New York, Inc., New York, NY, 1993
• 11: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 12: J.-S. Lee, K.-E. Kim, and M. Cherniack. A COKO compiler. Available at htrp ://www. cs.brown.edu/softwareJcokokola/coko.tar.Z, 1996.
• 13: Gail Mitchell , Umeshwar Dayal , Stanley B. Zdonik, Control of an Extensible Query Optimizer: A Planning-Based Approach, Proceedings of the 19th International Conference on Very Large Data Bases, p.517-528, August 24-27, 1993
• 14: I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.247-258, May 23-26, 1990, Atlantic City, New Jersey, United States
• 15: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 16: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• 17: Edward Sciore , John Sieg, Jr., A Modular Query Optimizer Generator, Proceedings of the Sixth International Conference on Data Engineering, p.146-153, February 05-09, 1990
• 18: Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Cost-based optimization for magic: algebra and implementation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.435-446, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages, Verification