Implementing an Interpreter for Functional Rules in a Query Optimizer.

@inproceedings{DBLP:conf/vldb/LeeFL88,
  author    = {Mavis K. Lee and
               Johann Christoph Freytag and
               Guy M. Lohman},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Implementing an Interpreter for Functional Rules in a Query Optimizer},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {218-229},
  ee        = {db/conf/vldb/LeeFL88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Query optimizers translate a high-level, user-submitted query into an efficient plan for executing that query, usually by estimating the execution cost of many different alternative plans. Existing implementations of these sophisticated but complex components of relational database management systems (DBMSs) typically embed the available strategies in the optimizer code, making them difficult to modify or enhance as improved strategies become available. In the last few years, interest in making DBMSs customizable for new application areas has magnified this need for flexible specification of execution strategies in a query optimizer. Several researchers have recently proposed query optimizers that are generated from rules for transforming plans into alternative plans. However, little progress has been reported on developing an implementation design that satisfies the requirements for high degrees of both flexibility and performance in an extensible query optimizer.

This paper presents a design for implementing a query optimizer that interprets a new kind of compositional rules for specifying alternative execution strategies that are input to the optimizer as data. Modifications to these function-like rules do not necessitate recompilation of the query optimizer, providing greater flexibility. Yet the interpretation, which resembles a macro expander, is so simple that a large number of rules can be processed efficiently. We describe the interpreter's data structures and algorithm, and relate these to the experience we gained from implementing an experimental prototype of this interpreter for the Starburst extensible database system at the IBM Almaden Research Center.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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/vldb7588 or /cdrom

• 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

References

[Bac85]

John W. Backus: From Function Level Semantics to Program Transformation and Optimization. TAPSOFT, Vol.1 1985: 60-91 BibTeX

[B*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

[Bat87a]

Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986) BibTeX

[Bat87b]

...

[C*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

[DS85]

...

[Fre87]

Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX

[Fre88]

...

[GD87]

Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX

[Gra86]

Goetz Graefe: Software Modularization with the EXODUS Optimizer Generator. IEEE Database Eng. Bull. 9(4): 37-45(1986) BibTeX

[H*88]

...

[KR78]

...

[LMP87]

Bruce G. Lindsay, John McPherson, Hamid Pirahesh: A Data Management Extension Architecture. SIGMOD Conference 1987: 220-226 BibTeX

[L*85]

Guy M. Lohman, C. Mohan, Laura M. Haas, Dean Daniels, Bruce G. Lindsay, Patricia G. Selinger, Paul F. Wilms: Query Processing in R*. Query Processing in Database Systems 1985: 31-47 BibTeX

[Loh87]

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX

[ML85]

Lothar F. Mackert, Guy M. Lohman: Index Scans Using a Finite LRU Buffer: A Validated I/O Model. ACM Trans. Database Syst. 14(3): 401-424(1989) BibTeX

[ML86]

Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 BibTeX

[P*87]

H.-Bernhard Paul, Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum, Uwe Deppisch: Architecture and Implementation of the Darmstadt Database Kernel System. SIGMOD Conference 1987: 196-207 BibTeX

[RH86]

Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) BibTeX

[S*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

[S*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

[SR86]

Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX

[UNI84]

...

Referenced by

1. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
2. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
3. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
4. Marcelo F. Frias, Silvia E. Gordillo: Semantic Optimization of Queries in Deductive Object-Oriented Database. ADBIS 1995: 55-72
5. 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)
6. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
7. 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)
8. Georges Gardarin, Rosana S. G. Lanzelotte: Optimizing Object-Oriented Datbase Queries using Cost-Controlled Rewriting. EDBT 1992: 534-549
9. 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)
10. Béatrice Finance, Georges Gardarin: A Rule-Based Query Rewriter in an Extensible DBMS. ICDE 1991: 248-256
11. 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)
12. Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
13. John Sieg Jr., Edward Sciore: Extended Relations. ICDE 1990: 488-494
14. Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153
15. Tobin J. Lehman, Bruce G. Lindsay: The Starburst Long Field Manager. VLDB 1989: 375-383
16. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
17. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents