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 BibTeX

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

[FINK82]

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

[FREY87]

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

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

[GARE87]

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

[GRAN80]

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

[NILS80]

...

[ROSE82]

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

[ROSE86]

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

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

[SELL86]

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

Referenced by

1. Jianjun Chen, David J. DeWitt, Feng Tian, Yuan Wang: NiagaraCQ: A Scalable Continuous Query System for Internet Databases. SIGMOD Conference 2000: 379-390
2. Fa-Chung Fred Chen, Margaret H. Dunham: Common Subexpression Processing in Multiple-Query Processing. IEEE Trans. Knowl. Data Eng. 10(3): 493-499(1998)
3. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
   Contents
4. Ram D. Gopal, Ram Ramesh: The Query Clustering Problem: A Set Partitioning Approach. IEEE Trans. Knowl. Data Eng. 7(6): 885-899(1995)
5. Sharma Chakravarthy: Early Active Database Efforts: A Capsule Summary. IEEE Trans. Knowl. Data Eng. 7(6): 1008-1010(1995)
6. Hongjun Lu, Kian-Lee Tan: Batch Query Processing in Shared-Nothing Multiprocessors. DASFAA 1995: 238-245
7. Martin L. Kersten, M. F. N. de Boer: Query Optimization Strategies for Browsing Sessions. ICDE 1994: 478-487
8. Jamal R. Alsabbagh, Vijay V. Raghavan: Analysis of Common Subexpression Exploitation Models in Multiple-Query Processing. ICDE 1994: 488-497
9. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
10. Sharma Chakravarthy: Divide and Conquer: A Basis for Augmenting a Conventional Query Optimizer with Multiple Query Proceesing Capabilities. ICDE 1991: 482-490
11. Witold Litwin, Leo Mark, Nick Roussopoulos: Interoperability of Multiple Autonomous Databases. ACM Comput. Surv. 22(3): 267-293(1990)
12. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102