dblp.uni-trier.de www.dagstuhl.de www.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},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, 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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BATO 87a]
...
[BATO 87b]
Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BERN 81]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRAT 84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHU 82]
...
[CLEA 77]
...
[DANI 82]
...
[DEWI 85]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EPST 78]
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FREY 87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRAE 87a]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRAE 87b]
Goetz Graefe: Software Modularization with the EXODUS Optimizer Generator. IEEE Database Eng. Bull. 9(4): 37-45(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KOST 71]
...
[LEE 88]
...
[LIND 87]
Bruce G. Lindsay, John McPherson, Hamid Pirahesh: A Data Management Extension Architecture. SIGMOD Conference 1987: 220-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOHM 85]
...
[MACK 86]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MORR 86]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ROSE 87]
Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON 86]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ULLM 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VALD 87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WONG 76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WONG 83]
Eugene Wong, Randy H. Katz: Distributing A Database for Parallelism. SIGMOD Conference 1983: 23-29 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:01 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page