Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor
Edward R. Omiecinski · 1991
Within the last several years, there has been a growing interest in applying general multiproces-sor systems to relational database query process-ing. Efficient parallel algorithms have been designed for the join operation but usually have a failing in that their performance deteriorates greatly when the data is nonuniform. In this paper, we propose a new version of the hash-based join algorithm that balances the load between the processors, for any given bucket, in a shared everything environment. We develop an analytical model of the cost of the algorithm and implement the algorithm on a shared memory multiprocessor machine. We also perform a number of experiments comparing our model with our empirical results. 1.