Fast joins using join indices

Two new algorithms, "Jive join" and "Slam join," are proposed for computing the join of two relations using a join index. The algorithms are duals: Ji ve join range-partitions input relation tuple ids and then processes each p artition, while Slam join forms ordered runs of input relation tuple ids an d then merges the results. Both algorithms make a single sequential pass th rough each input relation, in addition to one pass through the join index a nd two passes through a temporary file, whose size is half that of the join index. Both algorithms require only that the number of blocks in main memo ry is of the order of the square root of the number of blocks in the smalle r relation. By storing intermediate and final join results in a vertically partitioned fashion, our algorithms need to manipulate less data in memory at a given time than other algorithms. The algorithms are resistant to data skew and adaptive to memory fluctuations. Selection conditions can be inco rporated into the algorithms. Using a detailed cost model, the algorithms a re analyzed and compared with competing algorithms. For large input relatio ns, our algorithms perform significantly better than Valduriez's algorithm, the TID join algorithm, and hash join algorithms. An experimental study is also conducted to validate the analytical results and to demonstrate the p erformance characteristics of each algorithm in practice.