Join Algorithm for Multidimensional Linear Hash Databases

Summary Fluent join is a new join algorithm that operates on relations organized as multidimensional linear hash files. Like merge join on relations already sorted on a joining attribute, its execution reads each page in the operand relations no more than once and does not create intermediate result files. The orthogonality of a hash function for a composite key allows symmetric performances of joins on different parts of the key. In this paper, basic fluent join, its multiway extension, and several other variations are introduced. Benchmark test results confirmed that the performance is linear with respect to the total number of pages in operand relations.