Anatomy of a Mudular Multiple Query Optimizer.

@inproceedings{DBLP:conf/vldb/RosenthalC88,
  author    = {Arnon Rosenthal and
               Upen S. Chakravarthy},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Anatomy of a Mudular Multiple 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     = {230-239},
  ee        = {db/conf/vldb/RosenthalC88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We critically evaluate the current state of research in multiple query optmization, synthesize the requirements for a modular optimizer, and propose an architecture. Our objective is to facilitate future research by providing modular subproblems and a good general-purpose data structure. In the context of this architecture, we provide an improved subsumption algorithm, and discuss migration paths from single-query to multiple-query optimizers.

The architecture has three key ingredients. First, each type of work is performed at an appropriate level of abstraction. Second, a uniform and very compact representation stores all candidate strategies. Finally, search is handled as a discrete optimization problem separable from the query processing tasks.

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

[BATO87]

...

[CHAK86]

Upen S. Chakravarthy, Jack Minker: Multiple Query Processing in Deductive Databases using Query Graphs. VLDB 1986: 384-391

[DAYA88]

Umeshwar Dayal, Barbara T. Blaustein, Alejandro P. Buchmann, Upen S. Chakravarthy, Meichun Hsu, R. Ledin, Dennis R. McCarthy, Arnon Rosenthal, Sunil K. Sarin, Michael J. Carey, Miron Livny, Rajiv Jauhari: The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17(1): 51-70(1988)

[FINK82]

Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245

[FREY87]

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

[GARE79]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7

[GARE87]

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

[GRAN80]

John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234

[NILS80]

...

[ROSE82]

Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255

[ROSE86]

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

[SELI79]

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

[SELL86]

Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205