排序合并Join算法的新结果

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