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
  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        = {, db/conf/sigmod/BlakeleyMG93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP,}


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.

ACM SIGMOD Anthology

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

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1300 KB]


François Bancilhon, Won Kim: Object-Oriented Database Systems: In Transition. SIGMOD Record 19(4): 49-53(1990) BibTeX
Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392 BibTeX
Goetz Graefe, David Maier: Query Optimization in Object-Oriented Database Systems: A Prospectus. OODBS 1988: 358-363 BibTeX
Goetz Graefe: Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) BibTeX
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 BibTeX
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 BibTeX
Alfons Kemper, Guido Moerkotte: Advanced Query Processing in Object Bases Using Access Support Relations. VLDB 1990: 290-301 BibTeX
David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182 BibTeX
M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 BibTeX
O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) BibTeX
Jack A. Orenstein, Sam Haradhvala, Benson Margulies, Don Sakahara: Query Processing in the ObjectStore Database System. SIGMOD Conference 1992: 403-412 BibTeX
Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153 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
Gail M. Shaw, Stanley B. Zdonik: A Query Algebra for Object-Oriented Databases. ICDE 1990: 154-162 BibTeX
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 BibTeX
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
Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 BibTeX
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

  1. 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
  2. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
  3. Leonidas Fegaras: Query Unnesting in Object-Oriented Databases. SIGMOD Conference 1998: 49-60
  4. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315
  5. 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
  6. 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
  7. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
  8. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. VLDB 1996: 390-401
  9. Vassilis Christophides, Sophie Cluet, Guido Moerkotte: Evaluating Queries with Generalized Path Expressions. SIGMOD Conference 1996: 413-422
  10. Michael Stillger, Johann Christoph Freytag: Testing the Quality of a Query Optimizer. IEEE Data Eng. Bull. 18(3): 41-48(1995)
  11. 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)
  12. Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995)
  13. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  14. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334
  15. Georges Gardarin, Fernando Machuca, Philippe Pucheral: OFL: A Functional Execution Model for Object Query Languages. SIGMOD Conference 1995: 59-70
  16. Dinesh Das, Don S. Batory: Praire: A Rule Specification Framework for Query Optimizers. ICDE 1995: 201-210
  17. 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
  18. Karl Aberer, Gisela Fischer: Semantic Query Optimization for Methods in Object-Oriented Database Systems. ICDE 1995: 70-79
  19. M. Tamer Özsu, Adriana Muñoz, Duane Szafron: An Extensible Query Optimizer for an Objectbase Management System. CIKM 1995: 188-196
  20. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  21. 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
  22. Nathan Goodman, Steve Rozen, Lincoln Stein: Building a Laboratory Information System Around a C++-Based Object-Oriented DBMS. VLDB 1994: 722-729
  23. Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347
  24. Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160
  25. Richard H. Wolniewicz, Goetz Graefe: Algebraic Optimization of Computations over Scientific Databases. VLDB 1993: 13-24
  26. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
  27. Magdi M. A. Morsi, Shamkant B. Navathe: Application and System Prototyping Via an Extensible Object-Oriented Environment. ER 1993: 24-33
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:40:15 2009