A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment

File(s):

Author(s): Schneider, Donovan A; DeWitt, David J
Publisher: University of Wisconsin-Madison Department of Computer Sciences
Date: Mar 15, 2012
Abstract: In this paper we analyze and compare four parallel join algorithms. Grace and Hybrid hash represent the class of hash-based methods. Simple hash represents a looping algorithm with hashing, and our last algorithm is the more traditional sort-merge. The performance of each of the algorithms with different tuple distribution policies, the addition of bit vector filters, varying amounts of main-memory for joining, and non-uniformly distributed join attribute values is studied. The Hybrid hash-join algorithm is found to be superior except when the join attribute values of the inner relation are non-uniformly distributed and memory is limited. In this case, a more conservative algorithm such as the sort-merge algorithm should be used. The Gamma database machine serves as the host for the performance comparison.
Permanent link: http://digital.library.wisc.edu/1793/59102
Export: Export to RefWorks