DISTRIBUTED LOAD BALANCING FOR PARALLEL MAIN MEMORY HASH JOIN

Parallel joins have been widely studied during the past decade and a n umber of efficient algorithms were presented. While it is known that t he 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 deve lopment and analysis of a new distributed data structure and an effect ive load balancing scheme for parallel main memory hash join on NUMA a rchitecture. Multiprocessors based on this architecture are scalable i n both size of main memory and number of processors, and provide very high memory bandwidth. The load balancing scheme is based on random pr obing to avoid the hot spot problems caused by probing sequentially. W e have modeled this load balancing scheme both analytically and experi mentally. The experiments were run on a BBN TC2000 multiprocessor syst em.