Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins
Ming-Syan Chen⋆, Ming-Ling Lo, Philip S. Yu, Honesty C. Young · 1992
In this paper, we explore the execution of pipelined hash joins in a multiprocessor-based database system. To improve the query execution, an innovative approach on query execution tree selection is proposed to exploit segmented right-deep trees, which are bushy trees of right-deep subtrees. We first derive an analytical model for the execution of a pipeline segment, and then, in light of the model, develop heuristic schemes to determine the query execution plan based on a segmented right-deep tree so that the query can be efficiently executed. As shown by our simulation, the proposed approach, without incurring additional overhead on plan execution, possesses more flexibility in query plan generation, and leads to query plans of significantly better performance than those achievable by the previous schemes using right-deep trees. 1 Introduction In relational database systems, joins are the most expensive operations to execute, especially with the increases in database size and query ...