Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization.
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@inproceedings{DBLP:conf/sigmod/IoannidisK91,
author = {Yannis E. Ioannidis and
Younkyung Cha Kang},
editor = {James Clifford and
Roger King},
title = {Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and
its Implications for Query Optimization},
booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
Management of Data, Denver, Colorado, May 29-31, 1991},
publisher = {ACM Press},
year = {1991},
pages = {168-177},
ee = {http://doi.acm.org/10.1145/115790.115813, db/conf/sigmod/IoannidisK91.html},
crossref = {DBLP:conf/sigmod/91},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
We present a combination of analytical and experimental
results that shed some light into the shape of the cost function
of the strategy spaces that query optimizers must deal
with. These are the space that includes only left-deep trees
and the space that includes both deep and bushy trees. We
conclude that the cost functions of both spaces essentially
form a "well" but of a distinctly different quality. Based
on this result, we discuss how Iterative Improvement,
Simulated Annealing, and Two Phase Optimization perform
on these spaces. We conclude that the space of both
deep and bushy trees is easier to optimize than the space of
left-deep trees alone.
Copyright © 1991 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
James Clifford, Roger King (Eds.):
Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991.
ACM Press 1991 
,
SIGMOD Record 20(2),
June 1991
Contents
[Index Terms]
[Full Text in PDF Format, 1180 KB]
References
- [Gran81]
- ...
- [Ibar84]
- Toshihide Ibaraki, Tiko Kameda:
On the Optimal Nesting Order for Computing N-Relational Joins.
ACM Trans. Database Syst. 9(3): 482-502(1984)
- [Ioan87]
- Yannis E. Ioannidis, Eugene Wong:
Query Optimization by Simulated Annealing.
SIGMOD Conference 1987: 9-22
- [Ioan90]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Randomized Algorithms for Optimizing Large Join Queries.
SIGMOD Conference 1990: 312-321
- [Jark84]
- Matthias Jarke, Jürgen Koch:
Query Optimization in Database Systems.
ACM Comput. Surv. 16(2): 111-152(1984)
- [Kang91]
- ...
- [Kim86]
- Won Kim, David S. Reiner, Don S. Batory (Eds.):
Query Processing in Database Systems.
Springer 1985, ISBN 3-540-13831-5
Contents - [Kirk83]
- ...
- [Kris86]
- Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo:
Optimization of Nonrecursive Queries.
VLDB 1986: 128-137
- [Monm79]
- ...
- [Naha86]
- ...
- [Roth86]
- ...
- [Seli79]
- 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
- [Sell86]
- Timos K. Sellis:
Global Query Optimization.
SIGMOD Conference 1986: 191-205
- [Swam88]
- Arun N. Swami, Anoop Gupta:
Optimization of Large Join Queries.
SIGMOD Conference 1988: 8-17
- [Ullm82]
- Jeffrey D. Ullman:
Principles of Database Systems, 2nd Edition.
Computer Science Press 1982, ISBN 0-914894-36-6
Copyright © Mon Dec 21 21:56:48 2009
by Michael Ley (ley@uni-trier.de)
