Experiences Building the Open OODB Query Optimizer.
José A. Blakeley, William J. McKenna, Goetz Graefe:
Experiences Building the Open OODB Query Optimizer.
SIGMOD Conference 1993: 287-296@inproceedings{DBLP:conf/sigmod/BlakeleyMG93,
author = {Jos{\'e} A. Blakeley and
William J. McKenna and
Goetz Graefe},
editor = {Peter Buneman and
Sushil Jajodia},
title = {Experiences Building the Open OODB Query Optimizer},
booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
Management of Data, Washington, D.C., May 26-28, 1993},
publisher = {ACM Press},
year = {1993},
pages = {287-296},
ee = {http://doi.acm.org/10.1145/170035.170080, db/conf/sigmod/BlakeleyMG93.html},
crossref = {DBLP:conf/sigmod/93},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
This paper reports our experiences building the query optimizer for
TI's Open 00DB system. To the best of our knowledge, it is the
first working object query optimizer to be based on a complete
extensible optimization framework including logical algebra,
execution algorithms, property enforcers, logical transformation
rules, implementation rules, and selectivity and cost estimation.
Our algebra incorporates a new materialize operator with its
corresponding logical transformation and implementation rules that
enable the optimization of path expressions. Initial experiments on
queries obtained from the object query optimization literature
demonstrate that our optimizer is able to derive plans that are as
efficient as, and often substantially more efficient than, the plans
generated by other query optimization strategies. These
experiments demonstrate that our initial choices for populating
each part of our optimization framework are reasonable. Our
experience also shows that having a complete optimization
framework is crucial for two reasons. First, it allows the optimizer
to discover plans that cannot be revealed by exploring only the
alternatives provided by the logical algebra and its transformations.
Second, it helps and forces the database system designer to
consider all parts of the framework and to maintain a good balance
of choices when incorporating a new logical operator, execution
algorithm, transformation rule, or implementation rule. The Open
OODB query optimizer was constructed using the Volcano
Optimizer Generator, demonstrating that this second-generation
optimizer generator enables rapid development of efficient and
effective query optimizers for non-standard data models and systems.
Copyright © 1993 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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Peter Buneman, Sushil Jajodia (Eds.):
Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993.
ACM Press 1993 BibTeX
,
SIGMOD Record 22(2),
June 1993
Contents
[Index Terms]
[Full Text in PDF Format, 1300 KB]
References
- [1]
- François Bancilhon, Won Kim:
Object-Oriented Database Systems: In Transition.
SIGMOD Record 19(4): 49-53(1990) BibTeX
- [2]
- ...
- [3]
- Sophie Cluet, Claude Delobel:
A General Framework for the Optimization of Object-Oriented Queries.
SIGMOD Conference 1992: 383-392 BibTeX
- [4]
- Goetz Graefe, David Maier:
Query Optimization in Object-Oriented Database Systems: A Prospectus.
OODBS 1988: 358-363 BibTeX
- [5]
- Goetz Graefe:
Volcano - An Extensible and Parallel Query Evaluation System.
IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) BibTeX
- [6]
- Goetz Graefe, William J. McKenna:
The Volcano Optimizer Generator: Extensibility and Efficient Search.
ICDE 1993: 209-218 BibTeX
- [7]
- Thomas Keller, Goetz Graefe, David Maier:
Efficient Assembly of Complex Objects.
SIGMOD Conference 1991: 148-157 BibTeX
- [8]
- Alfons Kemper, Guido Moerkotte:
Advanced Query Processing in Object Bases Using Access Support Relations.
VLDB 1990: 290-301 BibTeX
- [9]
- ...
- [10]
- David Maier, Jacob Stein:
Indexing in an Object-Oriented DBMS.
OODBS 1986: 171-182 BibTeX
- [11]
- ...
- [12]
- M. Muralikrishna:
Improved Unnesting Algorithms for Join Aggregate SQL Queries.
VLDB 1992: 91-102 BibTeX
- [13]
- O. Deux:
The Story of O2.
IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) BibTeX
- [14]
- Jack A. Orenstein, Sam Haradhvala, Benson Margulies, Don Sakahara:
Query Processing in the ObjectStore Database System.
SIGMOD Conference 1992: 403-412 BibTeX
- [15]
- Edward Sciore, John Sieg Jr.:
A Modular Query Optimizer Generator.
ICDE 1990: 146-153 BibTeX
- [16]
- 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
- [17]
- Gail M. Shaw, Stanley B. Zdonik:
A Query Algebra for Object-Oriented Databases.
ICDE 1990: 154-162 BibTeX
- [18]
- Eugene J. Shekita, Michael J. Carey:
A Performance Evaluation of Pointer-Based Joins.
SIGMOD Conference 1990: 300-311 BibTeX
- [19]
- Dave D. Straube, M. Tamer Özsu:
Queries and Query Processing in Object-Oriented Database Systems.
ACM Trans. Inf. Syst. 8(4): 387-430(1990) BibTeX
- [20]
- ...
- [21]
- Scott L. Vandenberg, David J. DeWitt:
Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance.
SIGMOD Conference 1991: 158-167 BibTeX
- [22]
- David L. Wells, José A. Blakeley, Craig W. Thompson:
Architecture of an Open Object-Oriented Database Management System.
IEEE Computer 25(10): 74-82(1992) BibTeX
Referenced by
- Florian Waas, César A. Galindo-Legaria:
Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer.
SIGMOD Conference 2000: 499-509
- Navin Kabra, David J. DeWitt:
OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization.
VLDB J. 8(1): 55-78(1999)
- Leonidas Fegaras:
Query Unnesting in Object-Oriented Databases.
SIGMOD Conference 1998: 49-60
- Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten:
The Complexity of Transformation-Based Join Enumeration.
VLDB 1997: 306-315
- Jens Claußen, Alfons Kemper, Guido Moerkotte, Klaus Peithner:
Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases.
VLDB 1997: 286-295
- Wan-Sup Cho, Seung-Sun Lee, Kyu-Young Whang, Yong-Ik Yoon:
Query Optimization Techniques Utilizing Path Indexes in Object-Oriented Database Systems.
DASFAA 1997: 21-29
- William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong:
EROC: A Toolkit for Building NEATO Query Optimizers.
VLDB 1996: 111-121
- Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang:
Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases.
VLDB 1996: 390-401
- Vassilis Christophides, Sophie Cluet, Guido Moerkotte:
Evaluating Queries with Generalized Path Expressions.
SIGMOD Conference 1996: 413-422
- Michael Stillger, Johann Christoph Freytag:
Testing the Quality of a Query Optimizer.
IEEE Data Eng. Bull. 18(3): 41-48(1995)
- Fatma Ozcan, Sena Nural, Pinar Koksal, Mehmet Altinel, Asuman Dogac:
A Region Based Query Optimizer Through Cascades Query Optimizer Framework.
IEEE Data Eng. Bull. 18(3): 30-40(1995)
- Goetz Graefe:
The Cascades Framework for Query Optimization.
IEEE Data Eng. Bull. 18(3): 19-29(1995)
- Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper:
Bypassing Joins in Disjunctive Queries.
VLDB 1995: 228-238
- Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang:
A Cost Model for Clustered Object-Oriented Databases.
VLDB 1995: 323-334
- Georges Gardarin, Fernando Machuca, Philippe Pucheral:
OFL: A Functional Execution Model for Object Query Languages.
SIGMOD Conference 1995: 59-70
- Dinesh Das, Don S. Batory:
Praire: A Rule Specification Framework for Query Optimizers.
ICDE 1995: 201-210
- Alejandro P. Buchmann, Jürgen Zimmermann, José A. Blakeley, David L. Wells:
Building an Integrated Active OODBMS: Requirements, Architecture, and Design Decisions.
ICDE 1995: 117-128
- Karl Aberer, Gisela Fischer:
Semantic Query Optimization for Methods in Object-Oriented Database Systems.
ICDE 1995: 70-79
- M. Tamer Özsu, Adriana Muñoz, Duane Szafron:
An Extensible Query Optimizer for an Objectbase Management System.
CIKM 1995: 188-196
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken, Rolf A. de By:
From Nested-Loop to Join Queries in OODB.
VLDB 1994: 618-629
- Nathan Goodman, Steve Rozen, Lincoln Stein:
Building a Laboratory Information System Around a C++-Based Object-Oriented DBMS.
VLDB 1994: 722-729
- Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn:
Optimizing Disjunctive Queries with Expensive Predicates.
SIGMOD Conference 1994: 336-347
- Richard L. Cole, Goetz Graefe:
Optimization of Dynamic Query Evaluation Plans.
SIGMOD Conference 1994: 150-160
- Richard H. Wolniewicz, Goetz Graefe:
Algebraic Optimization of Computations over Scientific Databases.
VLDB 1993: 13-24
- Goetz Graefe, William J. McKenna:
The Volcano Optimizer Generator: Extensibility and Efficient Search.
ICDE 1993: 209-218
- Magdi M. A. Morsi, Shamkant B. Navathe:
Application and System Prototyping Via an Extensible Object-Oriented Environment.
ER 1993: 24-33
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:15 2009