Abstract
We consider the problem of optimizing select-project-join relational queries for minimum response time on parallel machines. The design of the optimizer is based on three ideas: (1) the concept and quantification of degree of coarse grain parallelism for an execution tree, (2) the design of a parallelizing scheduler for a tree of coarse grain operations which is provably near optimal, and (3) the analysis of the scheduling algorithm to obtain a cost formula for parallel execution time. The search algorithm of the optimizer is presented as a multi-dimensional dynamic programming algorithm. We present two three- dimensional search algorithms for the case when placement of relations in the parallel machine do not overlap. We propose the tree placement strategy and demonstrate, by means of examples, how the number of dimensions in the search can be significantly reduced, thereby increasing the efficiency of the search algorithm.