ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Measuring the Complexity of Join Enumeration in Query Optimization.

Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
@inproceedings{DBLP:conf/vldb/OnoL90,
  author    = {Kiyoshi Ono and
               Guy M. Lohman},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Measuring the Complexity of Join Enumeration in Query Optimization},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {314-325},
  ee        = {db/conf/vldb/OnoL90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Since relational database management systems typically support only diadic join operators as primitive operations, a query optimizer must choose the "best" sequence of two-way joins to achieve the N-way join of tables requestedby a query. The computational complexity of this optimization process is dominated by the number of such possible sequences that must be evaluated by the optimizer. This paper describes and measures the performance of the Starburst join enumerator, which can parameterically adjust for each query the space of join sequences that are evaluated by the optimizer to allow or disallow (1) composite tables (i.e., tables that are themselves the result of a join) as the inner operand of a join and (2) joins between two tables having no join predicate linkingthem (i.e., Cartesian products). To limit the size of their optimizer's search space, most earlier systems excluded both of these types of plans, which can execute significantly faster for some queries. By experimentally varying the parameters of the Starburst join enumerator, we have validated analytic formulas for the number of join sequences under a variety of conditions, and have proven their dependence upon the "shape" of the query. Specifically,"linear" queries, in which tables are connectcd by binary predicates in a straight line, can be optimized in polynomial time. Hence the dynamicprogramming techniques of System R and R* can still be used to optimize linearqueries of as many as 100 tables in a reasonable amount of time!

Copyright © 1990 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 ...

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[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
[HAA88]
...
[HAA90]
Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KOO80]
Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KRI84]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LEE80]
Mavis K. Lee, Johann Christoph Freytag, Guy M. Lohman: Implementing an Interpreter for Functional Rules in a Query Optimizer. VLDB 1988: 218-229 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOH84]
Guy M. Lohman, Dean Daniels, Laura M. Haas, Ruth Kistler, Patricia G. Selinger: Optimization of Nested Queries in a Distributed Relational Database. VLDB 1984: 403-415 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOH85]
Guy M. Lohman, C. Mohan, Laura M. Haas, Dean Daniels, Bruce G. Lindsay, Patricia G. Selinger, Paul F. Wilms: Query Processing in R*. Query Processing in Database Systems 1985: 31-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOH86]
Guy M. Lohman: Do semantically equivalent SQL queries perform differently? ICDE 1986: 225-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOH88]
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
[LOH89]
...
[ONO88]
...
[ROS82]
Arnon Rosenthal, David S. Reiner: An Architecture for Query Optimization. SIGMOD Conference 1982: 246-255 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SEL79]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SWA88]
Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SWA89]
...
[WON76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:01 2010 by Michael Ley (ley@uni-trier.de)