A Region Based Query Optimizer Through Cascades Query Optimizer Framework.

@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

• 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

• 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/aDVD2 or /dvd

Online Edition:

References

[BMG 93]

José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296

[DAOD 95]

Asuman Dogac, Mehmet Altinel, Cetin Ozkan, Ilker Durusoy: Implementation Aspects of an Object-Oriented DBMS. SIGMOD Record 24(1): 9-14(1995)

[Dog 95]

Asuman Dogac, Mehmet Altinel, Cetin Ozkan, Ismailcem Budak Arpinar, Ilker Durusoy, Ilker Altintas: METU Object-Oriented DBMS Kernel. DEXA 1995: 14-27

[Dur 94]

...

[Frey 87]

Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180

[GD 87]

Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172

[GM 93]

Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218

[Gra 94]

Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995)

[HFLP 89]

Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388

[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)

[Kok 95]

...

[Loh 88]

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27

[McK 93]

William J. McKenna: Efficient Search in Extensible Query Optimization: The Volcano Optimizer Generator. Ph.D. thesis, University of Colorado-Boulder 1993

[MDZ 93]

Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik: Control of an Extensible Query Optimizer: A Planning-Based Approach. VLDB 1993: 517-528

[MDZ 94]

Gail Mitchell, Stanley B. Zdonik, Umeshwar Dayal: Optimization of Object-Oriented Queries: Problems and Approaches. NATO ASI OODBS 1993: 119-146

[Mit 93]

Gail Mitchell: Extensible Query Processing in an Object-Oriented Database. Ph.D. thesis, Brown University, Department of Computer Science 1993

[MZD 92]

...

[ODE 95]

Cetin Ozkan, Asuman Dogac, Cem Evrendilek: A Heuristic Approach for Optimization of Path Expressions. DEXA 1995: 522-534

[OL 90]

Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325