Tree structured multiple processor join methods
Roger K. Shultz, Ila Miller · 1987
This paper summarizes the execution cost of join operations performed by parallel executing processors. Four different parallel join algorithms are proposed for execution on multiple processing nodes interconnected on a tree structured communication network. Secondary storage is accessed in parallel by leaf nodes. An average execution cost analysis is presented for the multiple processor join methods. For a reasonable ratio of result to operand cardinality, joins which use hashing for semi-join of operands at the leaf node secondary storage interface are predicted to perform better than nested-loop and sort-merge joins. Both node memory capacity and join result cardinality have a large influence on the relative performance of the join methods. This analysis method forms a basis for selecting among alternative processing methods for statically linked, multiple processor computer architectures.