Parallelizing the Index-Nested-Loops Database Join Primitive on a Shared-Nothing Cluster

We describe an optimized parallel implementation of the index-nested-loops database join primitive for the Berkeley NOW, a shared-nothing cluster of commodity workstations. Using a dataset based on that of the TPC-D benchmark, we analyze the speedup of the parallel algorithm and the impact of a restricted memory environment on the individual node performance. We find that our variant of the index-nested-loops join algorithm demonstrates superlinear speedup on up to 8 processors, is scalable due to effective overlap of communication, and is not highly sensitive to the amount of memory on each node: for a sample join on a scale 3 TPC-D dataset, the algorithm performs equally well in 32 MB and 128 MB (ignoring OS overhead). We also demonstrate the importance of a carefully-tuned I/O strategy; in our environment, aggressive blocking combined with application-controlled caching via the Solaris 2.6 directio() interface were crucial to performance