Join processing in database systems with large main memories

Abstract

We study algorithms for computing the equijoin of two relations in a system with a standard architecture hut with large amounts of main memory. Our algorithms are especially efficient when the main memory available is a significant fraction of the size of one of the relations to he joined; but they can be applied whenever there is memory equal to approximately the square root of the size of one relation. We present a new algorithm which is a hybrid of two hash-based algorithms and which dominates the other algorithms we present, including sort-merge. Even in a virtual memory environment, the hybrid algorithm dominates all the others we study. Finally, we describe how three popular tools to increase the efficiency of joins, namely filters, Babb arrays, and semijoins, can he grafted onto any of our algorithms.