ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Region Based Query Optimizer Through Cascades Query Optimizer Framework.

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)
@article{DBLP:journals/debu/OzcanNKAD95,
  author    = {Fatma Ozcan and
               Sena Nural and
               Pinar Koksal and
               Mehmet Altinel and
               Asuman Dogac},
  title     = {A Region Based Query Optimizer Through Cascades Query Optimizer
               Framework},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {18},
  number    = {3},
  year      = {1995},
  pages     = {30-40},
  ee        = {db/journals/debu/OzcanNKAD95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The Cascades Query Optimizer Framework is a tool to help the database implementor (DBI) in constructing a query optimizer for a DBMS. It is data model independent and allows to code a query optimizer by providing the implementations of the subclasses of predefined interface classes. When the implementations of the required classes are provided properly, the generated optimizer produces the optimum execution plans for the queries. Although providing the complete set of rules and thus finding the optimum execution plans are beneficial for most of the queries, the query optimization time increases unacceptably for certain types of queries, e.g., for star queries. Hence it is important to be able to limit the number of alternative plans considered by the optimizer for specific types of queries by using the proper heuristics for each type. This leads to the concept of region based query optimization, where different types of queries are optimized by using different search strategies in each region.

This paper describes our experiences in developing a region based query optimizer through Cascades. Cascades' guidance structures provide the facilities required. The performance comparisons between a region based query optimizer and an exhaustive ( complete rule set without heuristic guidance) query optimizer, both generated through Cascades, indicate that the region based optimizer has a superior performance. Both the sum of optimization and execution times, namely the response time, and the quality of the plans generated are investigated.

Copyright © 1995 by the author(s). Abstract used with permission.


ACM SIGMOD Anthology

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

Online Edition:

Data Engineering Bulletin September 1995: Database Query Processing (Goetz Graefe, ed.)
( letter+figures , letter-figures , A4+figures , A4-figures , PDF+figures)

References

[BMG 93]
José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DAOD 95]
Asuman Dogac, Mehmet Altinel, Cetin Ozkan, Ilker Durusoy: Implementation Aspects of an Object-Oriented DBMS. SIGMOD Record 24(1): 9-14(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dog 95]
Asuman Dogac, Mehmet Altinel, Cetin Ozkan, Ismailcem Budak Arpinar, Ilker Durusoy, Ilker Altintas: METU Object-Oriented DBMS Kernel. DEXA 1995: 14-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dur 94]
...
[Frey 87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GD 87]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM 93]
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra 94]
Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HFLP 89]
Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IK 84]
Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kok 95]
...
[Loh 88]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McK 93]
William J. McKenna: Efficient Search in Extensible Query Optimization: The Volcano Optimizer Generator. Ph.D. thesis, University of Colorado-Boulder 1993
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MDZ 93]
Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MDZ 94]
Gail Mitchell, Stanley B. Zdonik, Umeshwar Dayal: Optimization of Object-Oriented Queries: Problems and Approaches. NATO ASI OODBS 1993: 119-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mit 93]
Gail Mitchell: Extensible Query Processing in an Object-Oriented Database. Ph.D. thesis, Brown University, Department of Computer Science 1993
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MZD 92]
...
[ODE 95]
Cetin Ozkan, Asuman Dogac, Cem Evrendilek: A Heuristic Approach for Optimization of Path Expressions. DEXA 1995: 522-534 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OL 90]
Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:26:38 2010 by Michael Ley (ley@uni-trier.de)