软件学报

作者：高锦涛,李战怀,杜洪涛,刘文洁

单位：高锦涛，西北工业大学 计算机学院, 陕西 西安 71012911,李战怀，西北工业大学 计算机学院, 陕西 西安 71012902,杜洪涛，西北工业大学 计算机学院, 陕西 西安 71012903,刘文洁，西北工业大学 计算机学院, 陕西 西安 71012904

关键词：分布式;排序合并连接;剪枝;双边邻接表;并行

基金：国家自然科学基金（61732014，61672432，61672434，61472321）；陕西省基础研究计划（2017JM6104）

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

来源：2019年第11期

《软件学报》期刊编辑部

查看软件学报杂志2019年第11期