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

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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