dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

EROC: A Toolkit for Building NEATO Query Optimizers.

William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
@inproceedings{DBLP:conf/vldb/McKennaBHT96,
  author    = {William J. McKenna and
               Louis Burger and
               Chi Hoang and
               Melissa Truong},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {EROC: A Toolkit for Building NEATO Query Optimizers},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {111-121},
  ee        = {http://www.vldb.org/conf/1996/P111.PDF},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

EROC (Extensible, Reusable Optimization Components) is a toolkit for building query optimizers. EROC's components are C++ classes based on abstractions we have identified as central to query optimization, not only in relational DBMSs, but in extended relational and object-oriented DBMSs as well. EROC's use of C++ classes clarifies the mapping from application domain (optimization) abstractions to solution domain (EROC) abstractions, and these classes provide: (1) complex predicate definition and manipulation; (2) representations for common operators, such as join and groupby, and associated property derivation functions, including key derivation; (3) management of catalog and type information; (4) implementations of common algebraic equivalence rules, and (5) System R- and Volcano-style search strategies. The classes are designed to provide optimizer implementors reusability and extensibility through layering and inheritance. EROC provides much more functionality than previous optimization tools because all of EROC's optimization classes are extensible and reusable, not just the search components.

In addition to describing EROC's architecture and software engineering, we also show how EROC's classes were extended to build NEATO (New EROC-based Advanced Teradata Optimizer), a join optimizer for a massively parallel environment. Based on the extensions required we give an indication of the savings EROC provided us. To show NEATO's efficiency and effectiveness, we present results of optimizing complex TPC/D benchmark queries and show that NEATO easily searches the entire space of query execution plans. We outline plans for extensions to NEATO and overview how the flexibility of EROC will enable these extensions.

Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

References

[AG89]
Rakesh Agrawal, Narain H. Gehani: ODE (Object Database and Environment): The Language and the Data Model. SIGMOD Conference 1989: 36-45 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ATT95]
...
[BMG93]
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
[CKP+93]
Albert Chen, Yung-Feng Kao, Mike Pong, Diana Shak, Sunil Sharma, Jay Vaishnav, Hansjörg Zeller: Query Processing in NonStop SQL. IEEE Data Eng. Bull. 16(4): 29-41(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CLR89]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cop92]
James Coplien: Advanced C++: Programming Syles and Idioms. Addison-Wesley 1992, ISBN 0-201-54855-0
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CS94]
Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Day87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GD87]
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GHQ95]
Ashish Gupta, Venky Harinarayan, Dallan Quass: Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995: 358-369 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GLL+95]
...
[GLPK94]
César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GM93]
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
[Gra87]
Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra95]
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
[GW87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS93]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IK90]
Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KD95]
...
[Kim82]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMS94]
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LV91]
Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LVZZ94]
Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït, Mikal Ziane: Invited Project Review: Industrial-strength parallel query optimization: issues and lessons. Inf. Syst. 19(4): 311-330(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McK93]
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
[MGB93]
...
[Mur92]
M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OL88]
...
[OL90]
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
[Pv93]
Marinus J. Plasmeijer, Marko C. J. D. van Eekelen: Functional Programming and Parallel Graph Rewriting. Addison-Wesley 1993, ISBN 0-201-41663-8
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Raa95]
...
[Sha92]
Dennis Shasha: Database Tuning - A Principled Approach. Prentice-Hall 1992, ISBN 0-13-205246-6
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SHL+96]
Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Str91]
Bjarne Stroustrup: The C++ Programming Language, Second Edition. Addison-Wesley 1991, ISBN 0-201-53992-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Mon Sep 17 22:00:59 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page