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



Abstract:Sort-merge join is an important implementation method of join in database system, and is more widely used than hash join. Under distributed environment, data is sharded and distributed across many nodes, and usually needed to be transmitted by network which is very expensive. Therefore, it is far more challenging to efficiently process sort-merge join in distributed database. Traditional strategy firstly sorts data, and then carries out merge-join based on sorted data, which are both related with original data. But original data usually has useless data blocks, which does not participate in join, but will increase the extra cost during join including network cost. The bigger of data size, the higher of possibility of useless data blocks. Traditional sort-merge join strategy does not prehandle these useless data. In this study, a parallel sort-merge join is proposed based on prune, called Pr_PSMJ, which can efficiently prune the useless data ahead from join data, and improve the efficiency of join. Firstly, a bilateral adjacency list (BAL) is constructed by the statistic information from shards of join data. Using BAL, the useless data of join data can be pruned and the correctness of final join result is guaranteed. Secondly, after the pruning, the optimal local-join executing place can be computed by BAL, and the quantity of data mitigating among nodes is minimized. Finally, during the join step, for the independence of local-join guaranteed by BAL, the executing of sort-merge join can be easily parallelled, and in every executing node, it is natural to parallel the local-partitial-join using multi-core environment. The final result is achieved by merging local-result. Because high efficient prune operation is done before executing join, Pr_PSMJ is almost fit for every sort-merge strategy, and it is a good lesson for other join strategies. The correctness, efficiency, and adaptability of algorithm are analyzed based on Pr_PSMJ. By experiments, it is proved that under distributed environment, orienting large data, Pr_PSMJ can effectively decrease the overhead of network and improve the join efficiency than other strategies.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5579