Scheduling problems in parallel query optimization

Chandra Chekuri, Waqar Hasan, Rajeev Motwani

Research output: Contribution to conferencePaperpeer-review


We introduce a class of novel multiprocessor scheduling problems that arise in the optimization of SQL queries for parallel machines. These consist of scheduling a tree of inter-dependent communicating operators while exploiting both inter-operator and intra-operator parallelism. We develop algorithms for the specific problem of scheduling a Pipelined Operator Tree in which all operators run in parallel using inter-operator parallelism. Weights associated with nodes and edges represent respectively the cost of operators and communication. Communication cost is incurred only if adjacent operators are assigned different processors. The optimization problem is to assign operators to processors so as to minimize the maximum processor load. We develop two approximation algorithms for this NP-hard problem. The faster algorithm has a performance ratio of 3.56 while the slower algorithm has a ratio of 2.87.

Original languageEnglish (US)
Number of pages11
StatePublished - 1995
Externally publishedYes
EventProceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - San Jose, CA, USA
Duration: May 22 1995May 25 1995


OtherProceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
CitySan Jose, CA, USA

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Scheduling problems in parallel query optimization'. Together they form a unique fingerprint.

Cite this