Hash-based and index-based join algorithms for cube and ring connected multicomputers

The authors compare the performance of two join algorithms on both cube and ring interconnections for message-based multicomputers, and investigate the effects that the number of processors and the type of interconnection scheme have on the performance. First, the parallel hybrid-hash join algorithm and the parallel join-index join algorithm for both the cube and ring connected multicomputers are presented. The performance of these algorithms is then compared through analytical cost modeling. The result shows that the join-index join algorithm gives good performance only when the join selectivity is very small, and the hybrid-hash join algorithm performs consistently well under most situations. It is shown that the cube topology yields better execution time than the same algorithm on the ring topology. Furthermore, increasing the number of processors has a more significant improvement on the execution time of the cube than for the ring configuration. The applicability of join indexes on the parallel database algorithms is also discussed