An Adaptive, Load Balancing Parallel Join Algorithm
Minesh B. Amin, Donovan A. Schneider, Vineet Kumar Singh · 1994
Abstract Vineet Singh Many parallel join algorithms have been proposed in the last several years. However,most of these algorithms require that the amount of data to be joined is known in advancein order to choose the proper number of join processors. This is an unrealistic assumptionbecause datasizes are typically unknown, and are notoriously hard to estimate. We presentan adaptive, load-balancingparallel join algorithm called PJLH to address this problem.PJLH efficiently adapts itself to use additional processors if the amount of data is largerthan expected. Furthermore, while adapting, it ensures a good load balancing of data acrossthe processors.We have implemented and analyzed PJLH on a main memory database system implemented on a cluster of workstations. We show that PJLH is nearly as efficient as an optimalalgorithm when the amount of datais known in advance. Furthermore, we show that PJLHefficiently adapts to use additionaljoin processors when necessary, while maintaining a balanced load. This makes PJLH especially well-suited for processing multi-joinqueries wherethe cardinalities of intermediate relations are very difficult to estimate.