ACM SIGMOD Anthology VLDB dblp.uni-trier.de

OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization.

Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
@article{DBLP:journals/vldb/KabraD99,
  author    = {Navin Kabra and
               David J. DeWitt},
  title     = {OPT++: An Object-Oriented Implementation for Extensible Database
               Query Optimization},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {1},
  year      = {1999},
  pages     = {55-78},
  ee        = {db/journals/vldb/KabraD99.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we describe the design and implementation of OPT++, a tool for extensible database query optimization that uses an object-oriented design to simplify the task of implementing, extending, and modifying an optimizer. Building an optimizer using OPT++ makes it easy to extend the query algebra (to add new query algebra operators and physical implementation algorithms to the system), easy to change the search space, and also to change the search strategy. Furthermore, OPT++ comes equipped with a number of search strategies that are available for use by an optimizer-implementor. OPT++ considerably simplifies both, the task of implementing an optimizer for a new database system, and the task of evaluating alternative optimization techniques and strategies to decide what techniques are best suited for that database system. We present the results of a series of performance studies. These results validate our design and show that, in spite of its flexibility, OPT++ can be used to build efficient optimizers.

Key Words

Object-relational databases - Query optimization - Extensibility - Software architecture

Copyright © 1999 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.


Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[BG92]
Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992) BibTeX
[BMG93]
José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 BibTeX
[FG91]
Béatrice Finance, Georges Gardarin: A Rule-Based Query Rewriter in an Extensible DBMS. ICDE 1991: 248-256 BibTeX
[Fre87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX
[GD87]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
[GLPK94]
César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95 BibTeX
[GLSW83]
Peter Gassner, Guy M. Lohman, K. Bernhard Schiefer, Yun Wang: Query Optimization in the IBM DB2 Family. IEEE Data Eng. Bull. 16(4): 4-18(1993) BibTeX
[GM93]
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 BibTeX
[Gra87]
Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
BibTeX
[Gra95]
Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995) BibTeX
[Hel94]
Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335 BibTeX
[HP88]
...
[IK90]
Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 BibTeX
[IW87]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 BibTeX
[Kan91]
Younkyung Cha Kang: Randomized Algorithms for Query Optimization. Ph.D. thesis, Univ. of Wisconsin-Madison 1991
BibTeX
[KBZ86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
[KGM91]
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 BibTeX
[KMP93]
Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554 BibTeX
[LFL88]
Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229 BibTeX
[Loh88]
...
[LV91]
Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373 BibTeX
[MBHT96]
William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121 BibTeX
[MDZ93]
Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528 BibTeX
[OL90]
Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325 BibTeX
[OMS95]
M. Tamer Özsu, Adriana Muñoz, Duane Szafron: An Extensible Query Optimizer for an Objectbase Management System. CIKM 1995: 188-196 BibTeX
[Pea84]
...
[PHH92]
Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48 BibTeX
[Sac+79]
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
[SC90]
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 BibTeX
[SG88]
Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 BibTeX
[SS90]
Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153 BibTeX
[Swa89]
Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX
[VM96]
Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46 BibTeX

Referenced by

  1. Praveen Seshadri: Enhanced Abstract Data Types in Object-Relational Databases. VLDB J. 7(3): 130-140(1998)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:36 2009