dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Implementing an Interpreter for Functional Rules in a Query Optimizer.

Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229
@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        = {http://www.vldb.org/conf/1988/P218.PDF},
  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.


Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Bac85]
John W. Backus: From Function Level Semantics to Program Transformation and Optimization. TAPSOFT, Vol.1 1985: 60-91 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bat87a]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DS85]
...
[Fre87]
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
[Fre88]
...
[GD87]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra86]
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
[H*88]
...
[KR78]
...
[LMP87]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Loh87]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ML86]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RH86]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SR86]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[UNI84]
...

Last update Mon Sep 17 22:00:45 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