On a Three-Way Hash Join Algorithm

We develop hash-based algorithms for computing a three-way join. The method involves hashing all three relations into buckets, and then joining buckets in main memory, three buckets at a time. Comparing to twocascaded hash joins, the algorithms avoid materializing an intermediate result. We present a cost model for this approach, from which we identify the range of parameters for queries that benefit from our technique. We also validate our analysis with experimental results, comparing our approach to performing two hybrid-hash joins. This approach is almost always preferable to computing to consecutive GRACE hash joins, and in many cases it is also preferable to two consequtive hybrid-hash joins. 1 Introduction Decision support is an emerging area of database processing that has created new demands on database systems. Traditional OLTP systems are built around the assumption that they will be called to execute a sequence queries, arriving at a high rate, but where each query w..