An Architecture for Query Optimization.

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

@inproceedings{DBLP:conf/sigmod/RosenthalR82,
  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        = {http://doi.acm.org/10.1145/582353.582401, db/conf/sigmod/RosenthalR82.html},
  crossref  = {DBLP:conf/sigmod/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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 ...

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/smod7592 or /cdrom

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

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

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

Contents

Online Edition: ACM Digital Library

References

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

Last update Thu May 24 04:43:14 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page