Optimizing multi-joint queries in parallel relational databases

The authors determine a plan that makes the execution of an individual query very fast, with minimizing parallel execution time as the objective. This creates a circular dependence: a plan tree is needed for effective resource assignment, which is needed to estimate the parallel execution time, and which in turn is needed for the cost-based search for a good plan tree. A search heuristic that breaks the cycle by constructing the plan tree layer by layer in a bottom-up manner is proposed. 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 intraoperator and interoperator parallelism, pipelining, and processor and memory assignment is proposed, as is a new approach for estimating the parallel execution time of a plan that considers sum and max of operators working sequentially and in parallel, respectively