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
  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        = {db/conf/vldb/McKennaBHT96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP,}


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.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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 BibTeX

Electronic Edition


Rakesh Agrawal, Narain H. Gehani: ODE (Object Database and Environment): The Language and the Data Model. SIGMOD Conference 1989: 36-45 BibTeX
José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 BibTeX
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) BibTeX
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
James Coplien: Advanced C++: Programming Syles and Idioms. Addison-Wesley 1992, ISBN 0-201-54855-0
Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366 BibTeX
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 BibTeX
Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX
Ashish Gupta, Venky Harinarayan, Dallan Quass: Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995: 358-369 BibTeX
César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95 BibTeX
Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 BibTeX
Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
Goetz Graefe: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19-29(1995) BibTeX
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 BibTeX
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 BibTeX
Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 BibTeX
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv: Query Optimization by Predicate Move-Around. VLDB 1994: 96-107 BibTeX
Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373 BibTeX
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) BibTeX
William J. McKenna: Efficient Search in Extensible Query Optimization: The Volcano Optimizer Generator. Ph.D. thesis, University of Colorado-Boulder 1993
M. Muralikrishna: Improved Unnesting Algorithms for Join Aggregate SQL Queries. VLDB 1992: 91-102 BibTeX
Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325 BibTeX
Marinus J. Plasmeijer, Marko C. J. D. van Eekelen: Functional Programming and Parallel Graph Rewriting. Addison-Wesley 1993, ISBN 0-201-41663-8
Dennis Shasha: Database Tuning - A Principled Approach. Prentice-Hall 1992, ISBN 0-13-205246-6
Contents BibTeX
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 BibTeX
Bjarne Stroustrup: The C++ Programming Language, Second Edition. Addison-Wesley 1991, ISBN 0-201-53992-6

Referenced by

  1. Divesh Srivastava: Review - EROC: A Toolkit for Building NEATO Query Optimizers. ACM SIGMOD Digital Review 2: (2000)
  2. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
  3. Clara Nippl, Bernhard Mitschang: TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer. VLDB 1998: 251-262
  4. Felipe Cariño, William O'Connell: Plan-Per-Tuple Optimization Solution - Parallel Execution of Expensive User-Defined Functions. VLDB 1998: 690-695
  5. Michael Jaedicke, Bernhard Mitschang: On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS. SIGMOD Conference 1998: 379-389
  6. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:10 2009