分布式数据库下基于剪枝的并行合并连接策略

• 作者: 刘文洁 李战怀 杜洪涛 高锦涛
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 分布式 排序合并连接 剪枝 双边邻接表 并行
• 年，卷（期）: 2019,（11）
• 所属期刊栏目: 数据库技术
• 页码范围: 3364-3381
• 页数: 18页
• 分类号: TP311
• 字数: 13449字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005579

摘要

排序合并连接是数据库系统一种重要的连接实现方式,比哈希连接有更广泛的应用.分布式环境下,数据分片、分布存储,面对昂贵的网络代价,进行高效排序合并连接的挑战巨大.传统策略首先针对连接数据进行排序,然后基于排好序的数据执行合并连接.这两部分操作均基于原始数据进行操作,通常情况下,原始连接数据存在无用数据块,这些数据块无需连接,但会增加额外开销,包括网络开销.随着数据量的增多,出现无用数据块的概率增大,额外开销随之增多.传统策略没有预先处理这些无用数据块.针对这个问题,提出一种分布式环境下基于剪枝的并行排序合并连接策略(parallel sort-merge join based on prune,简称Pr_PSMJ).其特点是,连接发生之前高效完成对连接对象无用数据块的剪枝处理,提高整体连接效率.基本思想是,根据连接对象对应的连接分区数据统计信息,构造一种双边邻接表(bilateral adjacency list,简称BAL),用来对连接数据中无用数据块进行剪枝,并保证最终连接结果的正确性;剪枝完成后,利用BAL计算出各个最佳本地连接执行点,并指导分区数据的迁移,使数据移动量最小;在连接阶段,由于BAL保证本地连接执行节点的独立性,因此能够轻松并行执行整个连接过程,并在每个连接点本地利用多核环境完成局部并行排序合并连接;最后,将局部结果合并成最终结果.由于Pr PSMJ中的高效剪枝策略是在连接执行之前完成的,因此几乎适合任何合并连接操作,并且对于其他连接策略也有借鉴作用.给出了基于Pr PSMJ的算法的正确性、效率性以及适应性分析,并且给出实验验证,证明了在分布式大数据量排序合并连接情况下,Pr PSMJ相对于其他策略能够有效减少网络开销,并提高连接效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李战怀	西北工业大学计算机学院	254	2139	21.0	35.0
2	刘文洁	西北工业大学计算机学院	18	64	4.0	7.0
3	高锦涛	西北工业大学计算机学院	4	3	1.0	1.0
4	杜洪涛	西北工业大学计算机学院	5	10	2.0	3.0