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

by Minos N. Garofalakis and Yannis E. Ioannidis.
Proceedings of VLDB'97, Athens, Greece, August 1997, pp. 296-305.


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.

[ camera-ready paper (pdf) (ps.gz) | extended version (ps.gz) | my talk slides (ps.gz) ]

Copyright © 1997, 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 permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.