摘要
Join操作是数据库中最昂贵和最常用的操作.排序合并Join算法是实现Join操作的重要算法,得到了普遍接受并广为应用.在重新研究了排序合并Join算法后发现,同时对两个Join关系进行外排序是不必要的,会带来很大的额外开销.针对这个问题,提出了一种基于单关系外排序的分治Join算法,并在该算法的基础上提出了基于单关系外排序的并行分治Join算法.理论和实验结果证明,基于单关系排序的分治Join算法高于排序合并Join算法.特别是在并行计算环境下,基于单关系排序的并行分治Join算法的效率远远高于排序合并Join算法的并行版本.
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.
出处
《软件学报》
EI
CSCD
北大核心
1999年第3期264-269,共6页
Journal of Software
基金
国家杰出青年基金
黑龙江省杰出青年基金