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

Query Optimization for Parallel Execution.

Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18
@inproceedings{DBLP:conf/sigmod/GangulyHK92,
  author    = {Sumit Ganguly and
               Waqar Hasan and
               Ravi Krishnamurthy},
  editor    = {Michael Stonebraker},
  title     = {Query Optimization for Parallel Execution},
  booktitle = {Proceedings of the 1992 ACM SIGMOD International Conference on
               Management of Data, San Diego, California, June 2-5, 1992},
  publisher = {ACM Press},
  year      = {1992},
  pages     = {9-18},
  ee        = {http://doi.acm.org/10.1145/130283.130291, db/conf/sigmod/GangulyHK92.html},
  crossref  = {DBLP:conf/sigmod/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The decreasing cost of computing makes it economically viable to reduce the response time of decision support queries by using parallel execution to exploit inexpensive resources. This goal poses the following query optimization problem: Minimize response time subject to constraints on throughput, which we motivate as the dual of the traditional DBMS problem. We address this novel problem in the context of Select-Project-Join queries by extending the execution space, cost model and search algorithm that are widely used in commercial DBMSs. We incorporate the sources and deterrents of parallelism in the traditional execution space. We show that a cost model can predict response time while accounting for the new aspects due to parallelism. We observe that the response time optimization metric violates a fundamental assumption in the dynamic programming algorithm that is the linchpin in the optimizers of most commercial DBMSs. We extend dynamic programming and show how optimization metrics which correctly predict response time may be designed.

Copyright © 1992 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

Michael Stonebraker (Ed.): Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. ACM Press 1992 BibTeX , SIGMOD Record 21(2), June 1992
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1113 KB]

References

[AHY83]
Peter M. G. Apers, Alan R. Hevner, S. Bing Yao: Optimization Algorithms for Distributed Queries. IEEE Trans. Software Eng. 9(1): 57-68(1983) BibTeX
[Bel57]
...
[CHK+91]
Tim Connors, Waqar Hasan, Curtis P. Kolovson, Marie-Anne Neimat, Donovan A. Schneider, W. Kevin Wilkinson: The Papyrus Integrated Data Server. PDIS 1991: 139 BibTeX
[DG90]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of Database Processing or a Passing Fad? SIGMOD Record 19(4): 104-112(1990) BibTeX
[DGS+90]
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX
[GHK92]
...
[Gra91]
Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents BibTeX
[HS91]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. PDIS 1991: 218-225 BibTeX
[PMC+90]
...
[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 BibTeX
[Sch90]
...
[SD89]
Donovan A. Schneider, David J. DeWitt: A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. SIGMOD Conference 1989: 110-121 BibTeX

Referenced by

  1. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  2. Clara Nippl, Bernhard Mitschang: TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer. VLDB 1998: 251-262
  3. Tolga Urhan, Michael J. Franklin, Laurent Amsaleg: Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998: 130-141
  4. Anant Jhingran, Timothy Malkemus, Sriram Padmanabhan: Query Optimization in DB2 Parallel Edition. IEEE Data Eng. Bull. 20(2): 27-34(1997)
  5. Minos N. Garofalakis, Yannis E. Ioannidis: Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources. VLDB 1997: 296-305
  6. Michael J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference 1997: 219-230
  7. Lionel Brunie, Harald Kosch: ModParOpt: A Modular Query Optimizer for Multi-Query Parallel Databases. ADBIS 1997: 97-106
  8. 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)
  9. Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu: Optimization of Parallel Execution for Multi-Join Queries. IEEE Trans. Knowl. Data Eng. 8(3): 416-428(1996)
  10. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  11. Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
  12. Minos N. Garofalakis, Yannis E. Ioannidis: Multi-dimensional Resource Scheduling for Parallel Queries. SIGMOD Conference 1996: 365-376
  13. Michael J. Franklin, Björn Þór Jónsson, Donald Kossmann: Performance Tradeoffs for Client-Server Query Processing. SIGMOD Conference 1996: 149-160
  14. Sumit Ganguly, Akshay Goel, Abraham Silberschatz: Efficient and Acurate Cost Models for Parallel Query Optimization. PODS 1996: 172-181
  15. Ming-Syan Chen, Ming-Ling Lo, Philip S. Yu, Honesty C. Young: Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins. IEEE Trans. Knowl. Data Eng. 7(4): 656-668(1995)
  16. Waqar Hasan, Rajeev Motwani: Coloring Away Communication in Parallel Query Optimization. VLDB 1995: 239-250
  17. Surajit Chaudhuri, Umeshwar Dayal, Tak W. Yan: Join Queries with External Text Sources: Execution and Optimization Techniques. SIGMOD Conference 1995: 410-422
  18. Chandra Chekuri, Waqar Hasan, Rajeev Motwani: Scheduling Problems in Parallel Query Optimization. PODS 1995: 255-265
  19. Gerhard Weikum: Tutorial on Parallel Database Systems. ICDT 1995: 33-37
  20. Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200
  21. Ophir Frieder, Chaitanya K. Baru: Site and Query Scheduling Policies in Multicomputer Database Systems. IEEE Trans. Knowl. Data Eng. 6(4): 609-619(1994)
  22. Waqar Hasan, Rajeev Motwani: Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism. VLDB 1994: 36-47
  23. Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
  24. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441
  25. Hui-I Hsiao, Ming-Syan Chen, Philip S. Yu: On Parallel Execution of Multiple Pipelined Hash Joins. SIGMOD Conference 1994: 185-196
  26. Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160
  27. Michael Stonebraker, Paul M. Aoki, Robert Devine, Witold Litwin, Michael A. Olson: Mariposa: A New Architecture for Distributed Data. ICDE 1994: 54-65
  28. Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet: Parallel Query Processing with Zigzag Trees. VLDB J. 2(3): 277-301(1993)
  29. Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492
  30. Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504
  31. Surajit Chaudhuri, Kyuseok Shim: Query Optimization in the Presence of Foreign Functions. VLDB 1993: 529-542
  32. Waqar Hasan, Michael L. Heytens, Curtis P. Kolovson, Marie-Anne Neimat, Spyros Potamianos, Donovan A. Schneider: Papyrus GIS Demonstration. SIGMOD Conference 1993: 554-555
  33. Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan: Query Optimization in a Heterogeneous DBMS. VLDB 1992: 277-291
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:08 2009