Anatomy of a Mudular Multiple Query Optimizer.

Arnon Rosenthal, Upen S. Chakravarthy: Anatomy of a Mudular Multiple Query Optimizer. VLDB 1988: 230-239
  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,
  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,}


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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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


Upen S. Chakravarthy, Jack Minker: Multiple Query Processing in Deductive Databases using Query Graphs. VLDB 1986: 384-391 BibTeX
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
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX
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
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX
Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255 BibTeX
Arnon Rosenthal, Paul Helman: Understanding and Extending Transformation-Based Optimizers. IEEE Database Eng. Bull. 9(4): 44-51(1986) BibTeX
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
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
  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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:38 2009