Heuristic and Randomized Optimization for the Join Ordering Problem.
Michael Steinbrunn, Guido Moerkotte, Alfons Kemper:
Heuristic and Randomized Optimization for the Join Ordering Problem.
VLDB J. 6(3): 191-208(1997)@article{DBLP:journals/vldb/SteinbrunnMK97,
author = {Michael Steinbrunn and
Guido Moerkotte and
Alfons Kemper},
title = {Heuristic and Randomized Optimization for the Join Ordering Problem},
journal = {VLDB J.},
volume = {6},
number = {3},
year = {1997},
pages = {191-208},
ee = {db/journals/vldb/SteinbrunnMK97.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Recent developments in database technology, such as deductive database systems, have given rise to the demand for new, cost-effective optimization techniques for join expressions.
In this paper many different algorithms that compute approximate solutions for optimizing join orders are studied since traditional dynamic programming techniques are not appropriate for complex problems.
Two possible solution spaces, the space of left-deep and bushy processing trees, are evaluated from a statistical point of view.
The result is that the common limitation to left-deep processing trees is only advisable for certain join graph types.
Basically, optimizers from three classes are analysed: heuristic, randomized and genetic algorithms.
Each one is extensively scrutinized with respect to its working principle and its fitness for the desired application.
It turns out that randomized and genetic algorithms are well suited for optimizing join expressions.
They generate solutions of high quality within a reasonable running time.
The benefits of heuristic optimizers, namely the short running time, are often outweighed by merely moderate optimization performance.
Key Words
Query optimization, Join ordering, Heuristic algorithms, Randomized algorithms, Genetic algorithms
Copyright © 1997 by Springer, Berlin, Heidelberg.
Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or
direct commercial advantage, and that copies show this notice along with the full citation.
Citation Page
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
References
- [BFI91]
- ...
- [EN94]
- Ramez Elmasri, Shamkant B. Navathe:
Fundamentals of Database Systems, 2nd Edition.
Benjamin/Cummings 1994, ISBN 0-8053-1748-1
Contents 
- [GLPK94]
- César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten:
Fast, Randomized Join-Order Selection - Why Use Transformations?
VLDB 1994: 85-95
- [Gol89]
- David E. Goldberg:
Genetic Algorithms in Search Optimization and Machine Learning.
Addison-Wesley 1989, ISBN 0-201-15767-5
- [IK84]
- Toshihide Ibaraki, Tiko Kameda:
On the Optimal Nesting Order for Computing N-Relational Joins.
ACM Trans. Database Syst. 9(3): 482-502(1984)
- [IK90]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Randomized Algorithms for Optimizing Large Join Queries.
SIGMOD Conference 1990: 312-321
- [IK91]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization.
SIGMOD Conference 1991: 168-177
- [IW87]
- Yannis E. Ioannidis, Eugene Wong:
Query Optimization by Simulated Annealing.
SIGMOD Conference 1987: 9-22
- [KBZ86]
- Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo:
Optimization of Nonrecursive Queries.
VLDB 1986: 128-137
- [KM92]
- Alfons Kemper, Guido Moerkotte:
Access Support Relations: An Indexing Method for Object Bases.
Inf. Syst. 17(2): 117-145(1992)
- [KM94]
- Alfons Kemper, Guido Moerkotte:
Object-Oriented Database Management: Applications in Engineering and Computer Science.
Prentice-Hall 1994, ISBN 0-13-629239-9
Contents - [Kru56]
- ...
- [Law78]
- ...
- [LV93]
- Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït:
On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces.
VLDB 1993: 493-504
- [ME92]
- Priti Mishra, Margaret H. Eich:
Join Processing in Relational Databases.
ACM Comput. Surv. 24(1): 63-113(1992)
- [MS79]
- ...
- [OL90]
- Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325
- [SAC+79]
- 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
- [SG88]
- Arun N. Swami, Anoop Gupta:
Optimization of Large Join Queries.
SIGMOD Conference 1988: 8-17
- [Sha86]
- Leonard D. Shapiro:
Join Processing in Database Systems with Large Main Memories.
ACM Trans. Database Syst. 11(3): 239-264(1986)
- [SI93]
- Arun N. Swami, Balakrishna R. Iyer:
A Polynomial Time Algorithm for Optimizing Join Queries.
ICDE 1993: 345-354
- [Swa89]
- Arun N. Swami:
Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques.
SIGMOD Conference 1989: 367-376
- [VM96]
- Bennet Vance, David Maier:
Rapid Bushy Join-order Optimization with Cartesian Products.
SIGMOD Conference 1996: 35-46
- [WY76]
- Eugene Wong, Karel Youssefi:
Decomposition - A Strategy for Query Processing.
ACM Trans. Database Syst. 1(3): 223-241(1976)
- [YW79]
- Karel Youssefi, Eugene Wong:
Query Processing in a Relational Database Management System.
VLDB 1979: 409-417
Referenced by
- Alin Deutsch, Lucian Popa, Val Tannen:
Physical Data Independence, Constraints, and Optimization with Universal Plans.
VLDB 1999: 459-470
- Daniela Florescu, Alon Y. Levy, Ioana Manolescu, Dan Suciu:
Query Optimization in the Presence of Limited Access Patterns.
SIGMOD Conference 1999: 311-322
- Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina:
Optimizing Large Join Queries in Mediation Systems.
ICDT 1999: 348-364
Copyright © Mon Nov 2 22:00:50 2009
by Michael Ley (ley@uni-trier.de)
