DIMACS:CS Colloquium


Database Query Optimization for Parallel Executions


Sumit Ganguly
Rutgers University


CoRE Building 3rd Floor Conference Room "A"
Busch Campus, Rutgers University.


Thursday, December 15,1994


Query Optimization refers to the process of selecting an efficient execution tree from a set of candidate execution trees to evaluate a given database query. The design of successful query optimizers for sequential processing has contributed significantly to the success of relational database systems. However, current solutions to the problem of query optimization for parallel executions are unsatisfactory and limit the potential success of database systems on parallel machines.

We study the design of query optimizers for shared memory and shared nothing architectures. These optimizers are cost-based, i.e., they use an architecture-specific cost model to estimate the performance of an execution tree on the target architecture. The validity of the cost models is argued using a combination of theoretical arguments and simulations. Scheduling database execution trees introduces novel problems that have not been considered before, such as dealing with partitionable tasks, sequential and pipelined dependencies and memory constraints. We then discuss a specific scheduling problem, namely, scheduling partitionable pipelined tasks.

(Portions of this work are joint with Prof. Apostolos Gerasoulis, Akshay Goel and Weining Wang.)

Document last modified on December 10, 1994