Extensible/rule based query rewrite optimization in Starburst

ABSTRACT

This paper describes the Query Rewrite facility of the Starburst extensible database system, a novel phase of query optimization. We present a suite of rewrite rules used in Starburst to transform queries into equivalent queries for faster execution, and also describe the production rule engine which is used by Starburst to choose and execute these rules. Examples are provided demonstrating that these Query Rewrite transformations lead to query execution time improvements of orders of magnitude, suggesting that Query Rewrite in general—and these rewrite rules in particular—are an essential step in query optimization for modern database systems.

REFERENCES

• ABC+76: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• Anf89: Ole Jirgen Anfindsen.A Study of Access Path Selection in DB2. Technical report, Norwegian Telecommunications Administration and University of Oslo, Norway, October 1989.
• BFKM85: Lee Brownston , Robert Farrell , Elaine Kant , Nancy Martin, Programming expert systems in OPS5: an introduction to rule-based programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• BTA90: Jose Blakeley, Craig Thompson, and Abdallah Alashqur. Strawman reference model for object query language. In First OODB Standardization Workshop, X3/SPARC/DBSSG/OODBTG, Atlantic City, New Jersey, May 1990.
• Day87: Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
• GW87: Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States
• HCL+90: L. M. Haas , W. Chang , G. M. Lohman , J. McPherson , P. F. Wilms , G. Lapis , B. Lindsay , H. Pirahesh , M. J. Carey , E. Shekita, Starburst Mid-Flight: As the Dust Clears, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.143-160, March 1990 [doi>10.1109/69.50910]
• HH91: Joseph M. Hellerstein and Meichun Hsu. Determinism in Partially Ordered Production Systems. Research Report RJ 8089, IBM Almaden Research Center, March 1991.
• HP88: Waqar Hasan and Hamid Pirahesh. Query Rewrite Optimization in Starburst. Research Report RJ 6367, IBM Almaden Research Center, August 1988.
• HSS88: T. Harder , H. Schoning , A. Sikeler, Parallelism in processing queries on complex objects, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.131-143, December 05-07, 1988, Austin, Texas, United States
• ISO91: ISO_ANSI. Database Language SQL ISOBEC 9075:1992, 1991.
• Kim82: 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]
• LLOW91: Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991 [doi>10.1145/125223.125244]
• LLPS91: Guy M. Lohman , Bruce Lindsay , Hamid Pirahesh , K. Bernhard Schiefer, Extensions to Starburst: objects, types, functions, and rules, Communications of the ACM, v.34 n.10, p.94-109, Oct. 1991 [doi>10.1145/125223.125266]
• Loo86: Chris Loosley. Measuring IBM Database 2 Release 2 - The Benchmark Game. InfoDB, 1(2), 1986.
• MF78: J. McDermott and C. Forgy. Production System Conflict Resolution Strategies. In D.A. Waterman and Fredrick Hayes-Roth, editors, Pattern Directed Inference Systems, pages 177-199. Academic Press, 1978.
• MFPR90a: 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
• MFPR90b: Inderpal Singh Mumick , Sheldon J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic conditions, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.314-330, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298584]
• MPR90: Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
• O'N89: P. O'Neil. Revisiting DBMS Benchmarks. Datamation, pages 47-54, September 15, 1989.
• Pir89: Hamid Pirahesh. Early Experience with Rule-Based Query Rewrite Optimization. In G. Graefe, editor, Workshop on Database Query Optimization, CSE Technical Report 89-005. Oregon Graduate Center, May 1989.
• Pro90: Proc. ACM-SIGMOD International Conference on Management of Data, Atlantic City, May 1990.
• Ras90: Louiqa Raschid. Maintaining Consistency in a Stratified Production System Program. In Proc. AAAI National Conference on Artificial Intelligence, 1990.
• RGL90: Arnon Rosenthal , Cesar Galindo-Legaria, Query graphs, implementing trees, and freely-reorderable outerjoins, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.291-299, May 23-26, 1990, Atlantic City, New Jersey, United States
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• SJGP90: Michael Stonebraker , Anant Jhingran , Jeffrey Goh , Spyros Potamianos, On rules, procedure, caching and views in data base systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.281-290, May 23-26, 1990, Atlantic City, New Jersey, United States
• SWK76: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• TOB89: C. Turbyfill, C. Orji, and Dina Bitton. AS3AP - A Comparative Relational Database Benchmark. In Proc. IEEE Compcon Spring '89, February 1989.
• ZH90: Yuli Zhou , Meichun Hsu, A theory for rule triggering systems, Proceedings of the international conference on extending database technology on Advances in database technology, p.407-421, March 1990, Venice, Italy

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Languages, Theory