Parallel execution of hash joins in parallel databases

Abstract

In this paper, we explore two important issues, processor allocation and the use of hash filters, to improve the parallel execution of hash joins. To exploit the opportunity of pipelining for hash join execution, a scheme to transform a bushy execution tree to an allocation tree is first devised. In an allocation tree, each node denotes a pipeline. Then, using the concept of synchronous execution time, processors are allocated to the nodes in the allocation tree in such a way that inner relations in a pipeline can be made available at approximately the same time. Also, the approach of hash filtering is investigated to further improve the parallel execution of hash joins. Extensive performance studies are conducted via simulation to demonstrate the importance of processor allocation and to evaluate various schemes using hash filters. It is experimentally shown that processor allocation is, in general ,the dominant factor to performance, and the effect of hash filtering becomes more prominent as the number of relations in a query increases. © 1997 IEEE.