ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources.

Minos N. Garofalakis, Yannis E. Ioannidis: Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources. VLDB 1997: 296-305
@inproceedings{DBLP:conf/vldb/GarofalakisI97,
  author    = {Minos N. Garofalakis and
               Yannis E. Ioannidis},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Parallel Query Scheduling and Optimization with Time- and Space-Shared
               Resources},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {296-305},
  ee        = {db/conf/vldb/GarofalakisI97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Scheduling query execution plans is a particularly complex problem in hierarchical parallel systems, where each site consists of a collection of local time-shared (e.g., CPU(s) or disk(s)) and space-shared (e.g., memory) resources and communicates with remote sites by message-passing. We develop a general approach to the problem, capturing the full complexity of scheduling distributed multi-dimensional resource units for all kinds of parallelism within and across queries and operators. We present heuristic algorithms for various forms of the problem, some of which are provably near-optimal. Preliminary experimental results confirm the effectiveness of our approach.

Copyright © 1997 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

From CS Dept., University Trier (Germany)

References

[1]
Chaitanya K. Baru, Gilles Fecteau, Ambuj Goyal, Hui-I Hsiao, Anant Jhingran, Sriram Padmanabhan, George P. Copeland, Walter G. Wilson: DB2 Parallel Edition. IBM Systems Journal 34(2): 292-322(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Luc Bouganim, Daniela Florescu, Patrick Valduriez: Dynamic Load Balancing in Hierarchical Parallel Database Systems. VLDB 1996: 436-447 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Soumen Chakrabarti, S. Muthukrishnan: Resource Scheduling for Parallel Database and Scientific Applications. SPAA 1996: 329-335 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Edward G. Coffman Jr., M. R. Garey, David S. Johnson, Robert Endre Tarjan: Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms. SIAM J. Comput. 9(4): 808-826(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Sumit Ganguly, Akshay Goel, Abraham Silberschatz: Efficient and Acurate Cost Models for Parallel Query Optimization. PODS 1996: 172-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
Minos N. Garofalakis, Yannis E. Ioannidis: Multi-dimensional Resource Scheduling for Parallel Queries. SIGMOD Conference 1996: 365-376 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Ronald L. Graham: Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics 17(2): 416-429(1969) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Waqar Hasan, Daniela Florescu, Patrick Valduriez: Open Issues in Parallel Query Optimization. SIGMOD Record 25(3): 28-33(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Waqar Hasan, Rajeev Motwani: Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism. VLDB 1994: 36-47 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Wei Hong: Exploiting Inter-Operation Parallelism in XPRS. SIGMOD Conference 1992: 19-28 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Hui-I Hsiao, Ming-Syan Chen, Philip S. Yu: On Parallel Execution of Multiple Pipelined Hash Joins. SIGMOD Conference 1994: 185-196 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Viswanath Poosala, Yannis E. Ioannidis: Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing. VLDB 1996: 448-459 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
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
[22]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Jaideep Srivastava, Gary Elsesser: Optimizing Multi-Join Queries in Parallel Relational Databases. PDIS 1993: 84-92 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
John Turek, Joel L. Wolf, Krishna R. Pattipati, Philip S. Yu, Icel Wolf: Scheduling Parallelizable Tasks: Putting it All on the Shelf. SIGMETRICS 1992: 225-236 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers: Parallelism in a Main-Memory DBMS: The Performance of PRISMA/DB. VLDB 1992: 521-532 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Sachin More, S. Muthukrishnan, Elizabeth A. M. Shriver: Efficient Sequencing Tape-Resident Jobs. PODS 1999: 33-43
  2. Clara Nippl, Bernhard Mitschang: TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer. VLDB 1998: 251-262
  3. Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden: Resource Scheduling for Composite Multimedia Objects. VLDB 1998: 74-85

Copyright © Mon Nov 2 21:19:09 2009 by Michael Ley (ley@uni-trier.de)