| 摘要: |
| Join操作是数据库中最昂贵和最常用的操作.排序合并Join算法是实现Join操作的重要算法，得到了普遍接受并广为应用.在重新研究了排序合并Join算法后发现，同时对两个Join关系进行外排序是不必要的，会带来很大的额外开销.针对这个问题，提出了一种基于单关系外排序的分治Join算法，并在该算法的基础上提出了基于单关系外排序的并行分治Join算法.理论和实验结果证明，基于单关系排序的分治Join算法高于排序合并Join算法.特别是在并行计算环境下，基于单关系排序的并行分治Join算法的效率远远高于排序合并 |
| 关键词: Join操作，Join算法，排序合并Join算法. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家杰出青年基金和黑龙江省杰出青年基金资助. |
|
| Sort-Merge-Join Algorithm Revisited |
|
SUN Wen-jun,LI Jian-zhong
|
| Abstract: |
| The Sort-Merge-Join 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 Sort-Merge-Join algorithm, a new Join algorithm called SDC-Join algorithm, is proposed in this paper. The SDC-Join algorithm is a single-relation-sorting based divide-and-conquer algorithm. A parallel version of the SDC-Join algorithm is also presented in the paper. Theoretical analysis and experiment results show that the performance of the SDC-Join algorithm is much higher than that of the Sort-Merge-Join algorithm in both uniprocessor computer systems and parallel computer systems. |
| Key words: Join operation, Join algorithm, Sort-Merge-Join algorithm. |
