A number of hybrid systems have been proposed to combine the advantages of shared nothing and shared everything concepts for computing relational join operations. Most of these proposed systems, however, presented a few analytical results and have produced limited or no implementations on actual multiprocessors. In this paper, we present a parallel join algorithm with load-balancing for a hybrid system that combines both shared-nothing and shared-everything architectures. We derive an analytical model for the join algorithm on this architecture and validate it using both hardware/software simulations and actual experimentations. We study the performance of the join on the hybrid system for a wide range of system parameter values. We conclude that the hybrid system outperforms both shared-nothing and shared-everything architectures.

Parallel joins have been widely studied during the past decade and a number of efficient algorithms were presented. While it is known that the performance of these algorithms may suffer greatly in the presence of skewed input data, the work on load balancing schemes for parallel join has been limited. The main contribution of this paper is the development and analysis of a new distributed data structure and an effective load balancing scheme for parallel main memory hash join on NUMA architecture. Multiprocessors based on this architecture are scalable in both size of main memory and number of processors, and provide very high memory bandwidth. The load balancing scheme is based on random probing to avoid the hot spot problems caused by probing sequentially. We have modeled this load balancing scheme both analytically and experimentally. The experiments were run on a BBN TC2000 multiprocessor system.>

In data parallel applications, a major source of load trnbalance is in the uneven didribtitton of data between the nodes. The majar contribution of this paper is the analysis o j a new distributed Ioad balancing scheme based on random probing. Sequential probing was shown to create hot spot problems. Random probing, on the other hand, avoids these hot spots problems. We hove modeled this load balancing scheme bath anaiytically and experimentally. Distributed Hash Joan was used as an example application. The experimenls were done on a BEN TC2OOO rnulttprocessov- system.