An Architecture for Query Optimization.

Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255
  author    = {Arnon Rosenthal and
               David S. Reiner},
  editor    = {Mario Schkolnick},
  title     = {An Architecture for Query Optimization},
  booktitle = {Proceedings of the 1982 ACM SIGMOD International Conference on
               Management of Data, Orlando, Florida, June 2-4, 1982},
  publisher = {ACM Press},
  year      = {1982},
  pages     = {246-255},
  ee        = {, db/conf/sigmod/RosenthalR82.html},
  crossref  = {DBLP:conf/sigmod/82},
  bibsource = {DBLP,}


We describe an optimizer for relational queries to databases stored as flat files and Codasyl networks. We include sophisticated manipulations a broad range of direct access structures (DAS's). To achieve this with minimum additional code, we allow operations like sort, scan, and join to apply to DAS's, and categorize indexes and other DAS's in terms of the operations which can be performed on them. Our storage model, based on indivisible units of access and a small set of associated physical operators, provides a uniform interface to both relational and Codasyl storage mechanisms. The optimizer derives a sequence of internal data structures at successively more detailed levels. For a given query, a graph representing an overview of alternative joins is constructed, and then used to derive a physical graph which considers the physical attributes (location and sort order) of the data objects involved. Using cost predictions and other heuristics, the optimizer prunes the physical graph to produce a final access strategy tree. This layered approach and reliance on primitive operators make explicit (and permit changes to) the universe of possible strategies for the query at hand, and ease extension of the optimizer to new storage structures.

Copyright © 1982 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Mario Schkolnick (Ed.): Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data, Orlando, Florida, June 2-4, 1982. ACM Press 1982 BibTeX

Online Edition: ACM Digital Library


Morton M. Astrahan, Mario Schkolnick, Won Kim: Performance of the System R Access Path Selection Mechanism. IFIP Congress 1980: 487-491 BibTeX
James A. Behymer, Robert A. Ogilive, Alan G. Merten: Analysis of Indexed Sequential and Direct Access File Organizations. SIGMOD Workshop, Vol. 1 1974: 389-417 BibTeX
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
Hai-Yann Hwang, Umeshwar Dayal: Using the Entity-Relationship Model for Implementing Multi-Model Database Systems. ER 1981: 235-256 BibTeX
Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187 BibTeX
Akifumi Makinouchi, Masayoshi Tezuka, Hajime Kitakami, S. Adachi: The Optimization Strategy for Query Evaluation in RDB/V1. VLDB 1981: 518-529 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
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Data Base Design. VLDB 1981: 320-332 BibTeX
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX

Referenced by

  1. Giansalvatore Mecca, Alberto O. Mendelzon, Paolo Merialdo: Efficient Queries over Web Views. EDBT 1998: 72-86
  2. Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conference 1996: 91-102
  3. Dave D. Straube, M. Tamer Özsu: Query Optimization and Execution Plan Generation in Object-Oriented Data Management Systems. IEEE Trans. Knowl. Data Eng. 7(2): 210-227(1995)
  4. Hongjun Lu, Kian-Lee Tan, Son Dao: The Fittest Survives: An Adaptive Approach to Query Optimization. VLDB 1995: 251-262
  5. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
  6. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
  7. Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
  8. C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43
  9. Johann Christoph Freytag, Nathan Goodman: On the Translation of Relational Queries into Iterative Programs. ACM Trans. Database Syst. 14(1): 1-27(1989)
  10. Arnon Rosenthal, Upen S. Chakravarthy: Anatomy of a Mudular Multiple Query Optimizer. VLDB 1988: 230-239
  11. Kazuhiro Satoh, Masashi Tsuchida, Fumio Nakamura, Kazuhiko Oomachi: Local and Global Query Optimization Mechanisms for Relational Databases. VLDB 1985: 405-417
  12. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  13. Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:32 2009