ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Grammar-like Functional Rules for Representing Query Optimization Alternatives.

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
@inproceedings{DBLP:conf/sigmod/Lohman88,
  author    = {Guy M. Lohman},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Grammar-like Functional Rules for Representing Query Optimization
               Alternatives},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {18-27},
  ee        = {http://doi.acm.org/10.1145/50202.50204, db/conf/sigmod/Lohman88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Extensible query optimization requires that the "repertoire" of alternative strategies for executing queries be represented as data, not embedded in the optimizer code. Recognizing that query optimizers are essentially expert systems, several researchers have suggested using strategy rules to transform query execution plans into alternative or better plans. Though extremely flexible, these systems can be very inefficient at any step in the processing, many rules may be eligible for application and complicated conditions must be tested to determine that eligibility during unification. We present a constructive, "building blocks" approach to defining alternative plans, in which the rules defining alternatives are an extension of the productions of a grammar to resemble the definition of a function in mathematics. The extensions permit each token of the grammar to be parametrized and each of its alternative definitions to have a complex condition. The terminals of the grammar are base-level database operations on tables that are interpreted at run-time. The non-terminals are defined declaratively by production rules that combine those operations into meaningful plans for execution. Each production produces a set of alternative plans, each having a vector of properties, including the estimated cost of producing that plan. Productions can require certain properties of their inputs, such as tuple order and location, and we describe a "glue" mechanism for augmenting plans to achieve the required properties. We give detailed examples to illustrate the power and robustness of our rules and to contrast them with related ideas.

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 BibTeX , SIGMOD Record 17(2), June 1988
Contents

Online Edition: ACM Digital Library


References

[BABB 79]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX
[BATO 86]
Don S. Batory, J. R. Barnett, J. F. Garza, K. P. Smith, K. Tsukuda, B. C. Twichell, T. E. Wise: GENESIS: An Extensible Database Management System. IEEE Trans. Software Eng. 14(11): 1711-1730(1988) BibTeX
[BATO 87a]
...
[BATO 87b]
Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986) BibTeX
[BACK 78]
John W. Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. Commun. ACM 21(8): 613-641(1978) BibTeX
[BERN 81]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
[BRAT 84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX
[CARE 86]
Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, M. Muralikrishna, Joel E. Richardson, Eugene J. Shekita: The Architecture of the EXODUS Extensible DBMS. OODBS 1986: 52-65 BibTeX
[CHU 82]
...
[CLEA 77]
...
[DANI 82]
...
[DEWI 85]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 BibTeX
[EPST 78]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX
[FREY 87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX
[GRAE 87a]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
[GRAE 87b]
Goetz Graefe: Software Modularization with the EXODUS Optimizer Generator. IEEE Database Eng. Bull. 9(4): 37-45(1986) BibTeX
[HAER 78]
Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) BibTeX
[KOST 71]
...
[LEE 88]
...
[LIND 87]
Bruce G. Lindsay, John McPherson, Hamid Pirahesh: A Data Management Extension Architecture. SIGMOD Conference 1987: 220-226 BibTeX
[LOHM 83]
Guy M. Lohman, Joseph C. Stoltzfus, Anita N. Benson, Michael D. Martin, Alfonso F. Cardenas: Remotely-Sensed Geophysical Databases: Experience and Implications for Generalized DBMS. SIGMOD Conference 1983: 146-160 BibTeX
[LOHM 84]
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 BibTeX
[LOHM 85]
...
[MACK 86]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 BibTeX
[MORR 86]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 BibTeX
[ROSE 87]
Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) BibTeX
[SCHW 86]
Peter M. Schwarz, Walter Chang, Johann Christoph Freytag, Guy M. Lohman, John McPherson, C. Mohan, Hamid Pirahesh: Extensibility in the Starburst Database System. OODBS 1986: 85-92 BibTeX
[SELI 79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[STON 86]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
[ULLM 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[VALD 87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
[WONG 76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[WONG 83]
Eugene Wong, Randy H. Katz: Distributing A Database for Parallelism. SIGMOD Conference 1983: 23-29 BibTeX

Referenced by

  1. Michael Jaedicke, Bernhard Mitschang: User-Defined Table Operators: Enhancing Extensibility for ORDBMS. VLDB 1999: 494-505
  2. Laura M. Haas, Donald Kossmann, Ioana Ursu: Loading a Cache with Query Results. VLDB 1999: 351-362
  3. Clara Nippl, Bernhard Mitschang: TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer. VLDB 1998: 251-262
  4. Michael Jaedicke, Bernhard Mitschang: On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS. SIGMOD Conference 1998: 379-389
  5. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
  6. Ramana Yerneni, Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Fusion Queries over Internet Databases. EDBT 1998: 57-71
  7. Michael J. Carey, Donald Kossmann: Processing Top N and Bottom N Queries. IEEE Data Eng. Bull. 20(3): 12-19(1997)
  8. Mary Tork Roth, Peter M. Schwarz: Don't Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources. VLDB 1997: 266-275
  9. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
  10. Michael J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference 1997: 219-230
  11. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: An Optimizer for Heterogeneous Systems with NonStandard Data and Search Capabilities. IEEE Data Eng. Bull. 19(4): 37-44(1996)
  12. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. SIGMOD Conference 1996: 57-67
  13. Vassilis Christophides, Sophie Cluet, Guido Moerkotte: Evaluating Queries with Generalized Path Expressions. SIGMOD Conference 1996: 413-422
  14. Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
  15. David E. Simmen, Eugene J. Shekita, Timothy Malkemus: Fundamental Techniques for Order Optimization. EDBT 1996: 625-628
  16. Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao, James A. Thom, Justin Zobel: Atlas: A Nested Relational Database System for Text Applications. IEEE Trans. Knowl. Data Eng. 7(3): 454-470(1995)
  17. Fatma Ozcan, Sena Nural, Pinar Koksal, Mehmet Altinel, Asuman Dogac: A Region Based Query Optimizer Through Cascades Query Optimizer Framework. IEEE Data Eng. Bull. 18(3): 30-40(1995)
  18. Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995)
  19. Weipeng P. Yan, Per-Åke Larson: Eager Aggregation and Lazy Aggregation. VLDB 1995: 345-357
  20. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  21. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  22. Martin Erwig, Ralf Hartmut Güting: Explicit Graphs in a Functional Model for Spatial Databases. IEEE Trans. Knowl. Data Eng. 6(5): 787-804(1994)
  23. Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114
  24. Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347
  25. Peter Gassner, Guy M. Lohman, K. Bernhard Schiefer, Yun Wang: Query Optimization in the IBM DB2 Family. IEEE Data Eng. Bull. 16(4): 4-18(1993)
  26. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
  27. Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542
  28. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
  29. Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
  30. Tobin J. Lehman, Eugene J. Shekita, Luis-Felipe Cabrera: An Evaluation of Starburst's Memory Resident Storage Component. IEEE Trans. Knowl. Data Eng. 4(6): 555-566(1992)
  31. Daniel F. Lieuwen, David J. DeWitt: A Transformation-Based Approach to Optimizing Loops in Database Programming Languages. SIGMOD Conference 1992: 91-100
  32. Guy M. Lohman, Bruce G. Lindsay, Hamid Pirahesh, K. Bernhard Schiefer: Extensions to Starburst: Objects, Types, Functions, and Rules. Commun. ACM 34(10): 94-109(1991)
  33. Steve Rozen, Dennis Shasha: A Framework for Automating Physical Database Design. VLDB 1991: 401-411
  34. Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373
  35. Sharma Chakravarthy: Divide and Conquer: A Basis for Augmenting a Conventional Query Optimizer with Multiple Query Proceesing Capabilities. ICDE 1991: 482-490
  36. Hans-Jörg Schek, H.-Bernhard Paul, Marc H. Scholl, Gerhard Weikum: The DASDBS Project: Objectives, Experiences, and Future Prospects. IEEE Trans. Knowl. Data Eng. 2(1): 25-43(1990)
  37. Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990)
  38. Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
  39. Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301
  40. Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673
  41. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
  42. Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321
  43. Marc H. Scholl, Hans-Jörg Schek: A Relational Object Model. ICDT 1990: 89-105
  44. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
  45. Tobin J. Lehman, Bruce G. Lindsay: The Starburst Long Field Manager. VLDB 1989: 375-383
  46. Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44
  47. Walter W. Chang, Hans-Jörg Schek: A Signature Access Method for the Starburst Database System. VLDB 1989: 145-153
  48. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  49. Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell: Extending a DBMS for Geographic Applications. ICDE 1989: 590-597
  50. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
  51. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  52. Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330
  53. Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:52 2009