ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Randomized Algorithms for Optimizing Large Join Queries.

Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321
@inproceedings{DBLP:conf/sigmod/IoannidisK90,
  author    = {Yannis E. Ioannidis and
               Younkyung Cha Kang},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {Randomized Algorithms for Optimizing Large Join Queries},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {312-321},
  ee        = {http://doi.acm.org/10.1145/93597.98740, db/conf/sigmod/IoannidisK90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the query size grows. Randomized algorithms, such as Simulated Annealing (SA) and Iterative Improvements (II), are viable alternatives to exhaustive search. We have adapted these algorithms to the optimization of project-select-join queries. We have tested them on large queries of various types with different databases, concluding that in most cases SA identifies a lower cost access plan than II. To explain this result, we have studied the shape of the cost function over the solution space associated with such queries and we have conjectured that it resembles a 'cup' with relatively small variations at the bottom. This has inspired a new Tw oPhase Optimization algorithm, which is a combination of Simulated Annealing and Iterative Improvement. Experimental results show that Two Phase Optimization outperforms the original algorithms in terms of both output quality and running time.

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

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 BibTeX , SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library

References

[Care86]
Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, M. Muralikrishna, Joel E. Richardson, Eugene J. Shekita: The Architecture of the EXODUS Extensible DBMS. OODBS 1986: 52-65 BibTeX
[Gran81]
John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX
[Ioan87]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 BibTeX
[Jark84]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
[John87]
...
[Kim86]
Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents BibTeX
[Kirk83]
...
[Kris86]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
[Litz88]
Michael J. Litzkow, Miron Livny, Matt W. Mutka: Condor - A Hunter of Idle Workstations. ICDCS 1988: 104-111 BibTeX
[Lohm88]
Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX
[Naha86]
...
[Ono88]
...
[Rome85]
...
[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 BibTeX
[Sel88]
Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX
[Swam88]
Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 BibTeX
[Swam89]
Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX
[Ullm82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[Whan85]
...

Referenced by

  1. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
  2. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  3. Viswanath Poosala, Venkatesh Ganti: Fast Approximate Answers to Aggregate Queries on a Data Cube. SSDBM 1999: 24-33
  4. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  5. Francis C. Chu, Joseph Y. Halpern, Praveen Seshadri: Least Expected Cost Query Optimization: An Exercise in Utility. PODS 1999: 138-147
  6. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
  7. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  8. Tolga Urhan, Michael J. Franklin, Laurent Amsaleg: Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998: 130-141
  9. Michael Steinbrunn, Guido Moerkotte, Alfons Kemper: Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB J. 6(3): 191-208(1997)
  10. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB J. 6(2): 132-151(1997)
  11. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: Duplicate-Free Generation of Alternatives in Transformation-Based Optimizers. DASFAA 1997: 117-124
  12. Chiang Lee, Chi-Sheng Shih, Yaw-Huei Chen: A Graph-Theoretic Model for Optimizing Large Join Queries. DASFAA 1997: 87-96
  13. Lionel Brunie, Harald Kosch: ModParOpt: A Modular Query Optimizer for Multi-Query Parallel Databases. ADBIS 1997: 97-106
  14. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
  15. Yannis E. Ioannidis: Query Optimization. ACM Comput. Surv. 28(1): 121-123(1996)
  16. William J. McKenna, Louis Burger, Chi Hoang, Melissa Truong: EROC: A Toolkit for Building NEATO Query Optimizers. VLDB 1996: 111-121
  17. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  18. Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference 1996: 294-305
  19. Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160
  20. Bojan Groselj, Qutaibah M. Malluhi: Combinatorial Optimization of Distributed Queries. IEEE Trans. Knowl. Data Eng. 7(6): 915-927(1995)
  21. Hongjun Lu, Kian-Lee Tan, Son Dao: The Fittest Survives: An Adaptive Approach to Query Optimization. VLDB 1995: 251-262
  22. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: A Cost Model for Clustered Object-Oriented Databases. VLDB 1995: 323-334
  23. Weimin Du, Ming-Chien Shan, Umeshwar Dayal: Reducing Multidatabase Query Response Time by Tree Balancing. SIGMOD Conference 1995: 293-303
  24. Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94
  25. César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Uniformly-Distributed Random Generation of Join Orders. ICDT 1995: 280-293
  26. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
  27. Abdelkader Hameurlain, Franck Morvan: Scheduling and Mapping for Parallel Execution of Extended SQL Queries. CIKM 1995: 197-204
  28. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  29. Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili: Large Join Optimization on a Hypercube Multiprocessor. IEEE Trans. Knowl. Data Eng. 6(2): 304-315(1994)
  30. Ophir Frieder, Chaitanya K. Baru: Site and Query Scheduling Policies in Multicomputer Database Systems. IEEE Trans. Knowl. Data Eng. 6(4): 609-619(1994)
  31. Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155
  32. César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95
  33. Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
  34. Tadeusz Morzy, Maciej Matysiak, Silvio Salza: Tabu Search Optimization of Large Join Queries. EDBT 1994: 309-322
  35. Philip S. Yu, Douglas W. Cornell: Buffer Management Based on Return on Consumption in a Multi-Query Environment. VLDB J. 2(1): 1-37(1993)
  36. Allen Van Gelder: Multiple Join Size Estimation by Virtual Domains. PODS 1993: 180-189
  37. Arun N. Swami, Balakrishna R. Iyer: A Polynomial Time Algorithm for Optimizing Join Queries. ICDE 1993: 345-354
  38. Manish Mehta, Valery Soloviev, David J. DeWitt: Batch Scheduling in Parallel Database Systems. ICDE 1993: 400-410
  39. Jorng-Tzong Horng, Gwo-Dong Chen, Baw-Jhiune Liu: Query Processing Techniques in the Team-Oriented Database Query Language. DASFAA 1993: 245-252
  40. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  41. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB 1992: 103-114
  42. Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies. SIGMOD Conference 1992: 256-265
  43. Georges Gardarin, Rosana S. G. Lanzelotte: Optimizing Object-Oriented Datbase Queries using Cost-Controlled Rewriting. EDBT 1992: 534-549
  44. Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560
  45. Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373
  46. 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
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:03 2009