TY - GEN
T1 - Optimizing multi-join queries in parallel relational databases
AU - Srivastava, Jaideep
AU - Elsesser, Gary
PY - 1993/1/1
Y1 - 1993/1/1
N2 - Query optimization for parallel machines needs to consider machine architecture, processor and memory resources available, and different types of parallelism, making the search space much larger than the sequential case. In this paper our aim is to determine a plan that makes the execution of an individual query very fast, making minimizing parallel execution time the right objective. This creates the following circular dependence: a plan tree is needed for effective resource assignment, which is needed to estimate the parallel execution time, and this is needed for the cost-based search for a good plan tree. In this paper we propose a new search heuristic that breaks the cycle by constructing the plan tree layer by layer in a bottom-up manner. To select nodes at the next level, the lower and upper bounds on the execution time for plans consistent with the decisions made so far are estimated and are used to guide the search. A query plan representation for intra- and inter-operator parallelism, pipelining, and processor and memory assignment is proposed. Also proposed is a new approach to estimating the parallel execution time of a plan that considers sum and mat of operators working sequentially and in parallel, respectively. The results obtained from a prototype optimizer are presented.
AB - Query optimization for parallel machines needs to consider machine architecture, processor and memory resources available, and different types of parallelism, making the search space much larger than the sequential case. In this paper our aim is to determine a plan that makes the execution of an individual query very fast, making minimizing parallel execution time the right objective. This creates the following circular dependence: a plan tree is needed for effective resource assignment, which is needed to estimate the parallel execution time, and this is needed for the cost-based search for a good plan tree. In this paper we propose a new search heuristic that breaks the cycle by constructing the plan tree layer by layer in a bottom-up manner. To select nodes at the next level, the lower and upper bounds on the execution time for plans consistent with the decisions made so far are estimated and are used to guide the search. A query plan representation for intra- and inter-operator parallelism, pipelining, and processor and memory assignment is proposed. Also proposed is a new approach to estimating the parallel execution time of a plan that considers sum and mat of operators working sequentially and in parallel, respectively. The results obtained from a prototype optimizer are presented.
UR - http://www.scopus.com/inward/record.url?scp=84994073615&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994073615&partnerID=8YFLogxK
U2 - 10.1109/PDIS.1993.253068
DO - 10.1109/PDIS.1993.253068
M3 - Conference contribution
AN - SCOPUS:84994073615
T3 - Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, PDIS 1993
SP - 84
EP - 92
BT - Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems, PDIS 1993
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2nd International Conference on Parallel and Distributed Information Systems, PDIS 1993
Y2 - 20 January 1993 through 22 January 1993
ER -