排序合并Join算法的新结果

SortMergeJoin Algorithm Revisited

Ｊｏｉｎ操作是数据库中最昂贵和最常用的操作．排序合并Ｊｏｉｎ算法是实现Ｊｏｉｎ操作的重要算法，得到了普遍接受并广为应用．在重新研究了排序合并Ｊｏｉｎ算法后发现，同时对两个Ｊｏｉｎ关系进行外排序是不必要的，会带来很大的额外开销．针对这个问题，提出了一种基于单关系外排序的分治Ｊｏｉｎ算法，并在该算法的基础上提出了基于单关系外排序的并行分治Ｊｏｉｎ算法．理论和实验结果证明，基于单关系排序的分治Ｊｏｉｎ算法高于排序合并Ｊｏｉｎ算法．特别是在并行计算环境下，基于单关系排序的并行分治Ｊｏｉｎ算法的效率远远高于排序合并Ｊｏｉｎ算法的并行版本．

The SortMergeJoin algorithm is an effective and widely used algorithm for implementing the important Join operation in database systems. The algorithm is revisited in this paper. It is discovered that sorting both operand relations externally is not necessary in the algorithm. The cost of the algorithm would be reduced greatly if only one operand relation is sorted externally. In order to overcome the shortcomings of the SortMergeJoin algorithm, a new Join algorithm called SDCJoin algorithm, is proposed in this paper. The SDCJoin algorithm is a singlerelationsorting based divideandconquer algorithm. A parallel version of the SDCJoin algorithm is also presented in the paper. Theoretical analysis and experiment results show that the performance of the SDCJoin algorithm is much higher than that of the SortMergeJoin algorithm in both uniprocessor computer systems and parallel computer systems.