并行JOIN算法的优化子集合调整方法  

Optimal Subset-Adjusting Methods for Parallel Join Algorithms

作　　者：孙文隽[1] 李建中[1] 李金宝[1] 

机构地区：[1]黑龙江大学计算机科学系

出　　处：《黑龙江大学自然科学学报》1997年第3期39-46,54,共9页Journal of Natural Science of Heilongjiang University

基　　金：国家自然科学基金;国家八六三计划基金

摘　　要：子集合调整是克服数据偏斜影响的并行ＨＡＳＨ－ＪＯＩＮ算法的关键组成部分，现有的克服数据偏斜影响的ＨＡＳＨ－ＪＯＩＮ算法都没有很好地解决这个问题。作者深入地研究了子集合调整问题，提出了四种子集合调整算法。理论分析和实验结果都证明，这四种算法都能够很好地解决子集合调整问题，特别是启发式优化算法ＯＰ－ＡＤＪＵＳＴ在多数情况下都能给出优化解。Subset-adjusting is a very important problem for overcoming the harmful affection of the data skew in parallel hash-join algorithms. The parallel hash-join algorithms appeared up to now have not solved the problem effectively and efficiently. The problem is studied deeply in this paper. Four subsetadjusting algorithms are proposed. Theoretical and experimental results show that all the four algorithms can solve th subset-adjusting problem effectively and efficiently. Especially, the algorithm, OP-ADJUST, is able give optimal solution for the subset-adjusting problem in almost all the cases.

关 键 词：数据库 子集合调整 JOIN操作 并行JOIN算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]