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: Jive-join range-partitions input relation tuple-ids then processes each partition, while Slam-join forms ordered runs of input relation tuple-ids and then merges the results. Each algorithm has features that make it preferable to the other depending on the context in which it is being used. Both algorithms make a single sequential pass through each input relation, in addition to one pass through the join index and two passes through a temporary file whose size is half that of the join index. Both algorithms perform this efficiently even when the relations are much larger than main memory, as long as the number of blocks in main memory is of the order of the square root of the number of blocks in the smaller 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. Almost all the I/O of our algorithms is sequential, thus minimizing the impact of seek and rotational latency. The algorithms are resistant to data skew and adaptive to memory fluctuations. They can be extended to handle joins of multiple relations by using multidimensional partitioning while still making only a single pass over each input relation. They can also be extended to handle joins of relations that do not satisfy the memory bound by recursively applying the algorithms. We also show how selection conditions can be incorporated into the algorithms. Using a detailed cost model, the algorithms are analyzed and compared with competing algorithms. For large input relations, our algorithms perform significantly better than Valduriez's algorithm and hash join algorithms. An experimental study is also conducted to validate the analytical results and to demonstrate the performance characteristics of each algorithm in practice.