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}
}
BibTeX
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
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
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 BibTeX
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) BibTeX
- [2]
- Luc Bouganim, Daniela Florescu, Patrick Valduriez:
Dynamic Load Balancing in Hierarchical Parallel Database Systems.
VLDB 1996: 436-447 BibTeX
- [3]
- Soumen Chakrabarti, S. Muthukrishnan:
Resource Scheduling for Parallel Database and Scientific Applications.
SPAA 1996: 329-335 BibTeX
- [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) BibTeX
- [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) BibTeX
- [7]
- David J. DeWitt, Jim Gray:
Parallel Database Systems: The Future of High Performance Database Systems.
Commun. ACM 35(6): 85-98(1992) BibTeX
- [8]
- Sumit Ganguly, Akshay Goel, Abraham Silberschatz:
Efficient and Acurate Cost Models for Parallel Query Optimization.
PODS 1996: 172-181 BibTeX
- [9]
- Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy:
Query Optimization for Parallel Execution.
SIGMOD Conference 1992: 9-18 BibTeX
- [10]
- ...
- [11]
- Minos N. Garofalakis, Yannis E. Ioannidis:
Multi-dimensional Resource Scheduling for Parallel Queries.
SIGMOD Conference 1996: 365-376 BibTeX
- [12]
- ...
- [13]
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
- [14]
- Ronald L. Graham:
Bounds on Multiprocessing Timing Anomalies.
SIAM Journal of Applied Mathematics 17(2): 416-429(1969) BibTeX
- [15]
- Waqar Hasan, Daniela Florescu, Patrick Valduriez:
Open Issues in Parallel Query Optimization.
SIGMOD Record 25(3): 28-33(1996) BibTeX
- [16]
- Waqar Hasan, Rajeev Motwani:
Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism.
VLDB 1994: 36-47 BibTeX
- [17]
- Wei Hong:
Exploiting Inter-Operation Parallelism in XPRS.
SIGMOD Conference 1992: 19-28 BibTeX
- [18]
- Hui-I Hsiao, Ming-Syan Chen, Philip S. Yu:
On Parallel Execution of Multiple Pipelined Hash Joins.
SIGMOD Conference 1994: 185-196 BibTeX
- [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 BibTeX
- [20]
- Viswanath Poosala, Yannis E. Ioannidis:
Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing.
VLDB 1996: 448-459 BibTeX
- [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 BibTeX
- [22]
- Leonard D. Shapiro:
Join Processing in Database Systems with Large Main Memories.
ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
- [23]
- Jaideep Srivastava, Gary Elsesser:
Optimizing Multi-Join Queries in Parallel Relational Databases.
PDIS 1993: 84-92 BibTeX
- [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 BibTeX
- [25]
- Patrick Valduriez:
Parallel Database Systems: Open Problems and New Issues.
Distributed and Parallel Databases 1(2): 137-165(1993) BibTeX
- [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 BibTeX
Referenced by
- Sachin More, S. Muthukrishnan, Elizabeth A. M. Shriver:
Efficient Sequencing Tape-Resident Jobs.
PODS 1999: 33-43
- Clara Nippl, Bernhard Mitschang:
TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer.
VLDB 1998: 251-262
- Minos N. Garofalakis, Yannis E. Ioannidis, Banu Özden:
Resource Scheduling for Composite Multimedia Objects.
VLDB 1998: 74-85
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
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:46:16 2009