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

[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)

[Bat87a]

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

[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

[DS85]

...

[Fre87]

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

[Fre88]

...

[GD87]

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

[Gra86]

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

[H*88]

...

[KR78]

...

[LMP87]

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

[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

[Loh87]

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

[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)

[ML86]

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

[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

[RH86]

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

[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

[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

[SR86]

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

[UNI84]

...