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

Optimization of Large Join Queries.

Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17
@inproceedings{DBLP:conf/sigmod/SwamiG88,
  author    = {Arun N. Swami and
               Anoop Gupta},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Optimization of Large Join Queries},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {8-17},
  ee        = {http://doi.acm.org/10.1145/50202.50203},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We investigate the problem of optimizing Select-Project-Join queries with large numbers of joins. Taking advantage of commonly used heuristics, the problem is reduced to that of determining the optimal join order. This is a hard combinatorial optimization problem. Some general techniques, such as iterative improvement and simulated annealing, have often proved effective in attacking a wide variety of combinatorial optimization problems. In this paper, we apply these general algorithms to the large join query optimization problem. We use the statistical techniques of factorial experiments and analysis of variance (ANOVA) to obtain reliable values for the parameters of these algorithms and to compare these algorithms. One interesting result of our experiments is that the relatively simple iterative improvement proves to be better than all the other algorithms (included the more complex simulated annealing). We also find that the general algorithms do quite well at the maximum time limit.

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


ACM SIGMOD Anthology

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

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 17(2), June 1988
Contents

Online Edition: ACM Digital Library


References

[BHH78]
...
[Dav78]
...
[DKO*84]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DW83]
...
[FBC*87]
Daniel H. Fishman, David Beech, H. P. Cate, E. C. Chow, Tim Connors, J. W. Davis, Nigel Derrett, C. G. Hoch, William Kent, Peter Lyngbæk, Brom Mahbod, Marie-Anne Neimat, T. A. Ryan, Ming-Chien Shan: Iris: An Object-Oriented Database Management System. ACM Trans. Inf. Syst. 5(1): 48-69(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HRS86]
...
[IK84]
Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IW87]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JAMS87]
...
[JK84]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KBZ86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KGV83]
...
[NMF87]
Richard E. Nance, Robert L. Moose Jr., Robert V. Foutz: A Statistical Technique for Comparing Heuristics: An Example from Capacity Assignment Strategies in Computer Network Design. Commun. ACM 30(5): 430-442(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NSS86]
...
[PS82]
...
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Swa87a]
...
[Swa87b]
...

Last update Tue Sep 18 00:25:01 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