2019分布式数据库下基于剪枝的并行合并连接策略-高锦涛 , 李战怀 , 杜洪涛 , 刘文洁.pdf

上善若水

149

18页

0次

2022-05-23

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2019,30(11):3364−3381 [doi: 10.13 328/j.cnki.jos.005579] http://www.jos.org.cn

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

∗

高锦涛

李战怀

杜洪涛

刘文洁

(西北工业大学计算机学院,陕西西安 710129)

通讯作者: 高锦涛, E-mail: gaojintao@mail.nwpu.edu.cn

摘要: 排序合并连接是数据库系统一种重要的连接实现方式,比哈希连接有更广泛的应用.分布式环境下,数据

分片、分布存储,面对昂贵的网络代价,进行高效排序合并连接的挑战巨大.传统策略首先针对连接数据进行排序,

然后基于排好序的数据执行合并连接.这两部分操作均基于原始数据进行操作,通常情况下,原始连接数据存在无用

数据块,这些数据块无需连接,但会增加额外开销,包括网络开销.随着数据量的增多,出现无用数据块的概率增大,额

外开销随之增多.传统策略没有预先处理这些无用数据块.针对这个问题,提出一种分布式环境下基于剪枝的并行排

序合并连接策略(parallel sort-merge join based on prune,简称 Pr_PSMJ).其特点是,连接发生之前高效完成对连接对

象无用数据块的剪枝处理,提高整体连接效率.基本思想是,根据连接对象对应的连接分区数据统计信息,构造一种

双边邻接表(bilateral adjacency list,简称 BAL),用来对连接数据中无用数据块进行剪枝,并保证最终连接结果的正确

性;剪枝完成后,利用 BAL 计算出各个最佳本地连接执行点,并指导分区数据的迁移,使数据移动量最小;在连接阶段,

由于 BAL 保证本地连接执行节点的独立性,因此能够轻松并行执行整个连接过程,并在每个连接点本地利用多核环

境完成局部并行排序合并连接;最后,将局部结果合并成最终结果.由于 Pr_PSMJ 中的高效剪枝策略是在连接执行之

前完成的,因此几乎适合任何合并连接操作,并且对于其他连接策略也有借鉴作用.给出了基于 Pr_PSMJ 的算法的正

确性、效率性以及适应性分析,并且给出实验验证,证明了在分布式大数据量排序合并连接情况下,Pr_PSMJ 相对于

其他策略能够有效减少网络开销,并提高连接效率.

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

中图法分类号: TP311

中文引用格式: 高锦涛, 李战怀,杜洪涛,刘文洁.分布式数据库下基于剪枝的并行合并连接策略.软件学报, 2019,30(11):

3364−3381. http ://www.jos.org.cn/1000-9825/5579.htm

英文引用格式: Gao JT, Li ZH, Du HT, Liu WJ. Strategy of parallel merge join based on prune in distributed database. Ruan Jian

Xue Bao/Journal of Software, 2019,30(11):3364−3381 (in Chinese). http://www.jos.org.cn/1000-9825/5579.ht m

Strategy of Parallel Merge Join Based on Prune in Distribute d Databa se

GAO Jin-Tao, LI Zhan-Huai, DU Hong-Tao, LIU Wen-Jie

(School of Computer, Northwestern Polytechni cal Universit y, Xi’an 710129, China)

Abstra ct : Sort-merge join is an important implementation method of join in database system, and is more widely used than hash join.

Under distributed environment, d ata is sh arded and dis tributed across man y nodes, and usu ally 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 ar e both related with original data. But original data usually

has useless data blocks, whi ch does not participate in join, but will increase the extra cost during join including n etwork cost. The bigger

∗ 基金项目: 国家自然科学基金(61732014, 61672432, 61 672434, 61472321) ; 陕西省基础研究计划(2017JM6104)

Foundation item: National Natural Science Foundation of China (61732014, 61672432, 61672434, 61472321); Natural Science

Basic Research Plan of Shaanxi Province (2017J M6104)

收稿时间: 2017-07-27; 修改时间: 2017-09-29, 2018-02-28; 采用时间: 2018-04-04; jos 在线出版时间: 2018 -04-16

CNKI 网络优先出版: 2018-04-16 11 :00:01, http: //kns.cnki.net/kcms/d etail/11.2560.TP.20180416.1059.010.html

高锦涛等:分布式数据库下基于剪枝的并行合并连接策略

3365

of data size, the higher of possibili ty 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 fro m

join data, and improve the efficiency of join. Firstly, a bilateral adjacency list (BAL) is constructed by the statistic information from

shards of join dat a. Using BAL, th e useless d ata of join data can be prun ed 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 b y merging local-result. Because high efficient prune operation is done be fore executing join, Pr_PSMJ is almost fit fo r

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

effectiv el y decr e as e t h e o v erh e ad o f n et wo rk and impr ove th e j oi n effi ci en c y t h an o th er s tr a t eg ies .

Key words: distribution; sort-merge join; prune; bilateral adjacency list; parallel

排序合并连接是数据库系统的一种重要的连接实现方式

[1,2]

,比哈希连接有着更广泛的应用.分布式环境

下,数据量巨大,数据分片、分布存储,导致连接过程中存在大量网络代价,因此,高效地进行大数据量排序合并连

接,挑战巨大.根据经验及实验可得出,通常情况下,连接数据都可能存在无用数据块,即不需要进行连接的数据.

随着数据量增大,无用数据块比例可能越来越高,增加额外开销,比如分布式环境下的网络开销,降低连接效率.

排序合并连接过程涉及取数据、排序、连接等步骤,集中式架构下执行这些步骤涉及 CPU 和 IO 代价,分布

式环境下由于数据分片、跨域存储,需要额外考虑网络传输代价.以 OceanBase 数据库

[3]

为例,介绍分布式环境

下集中式处理排序合并连接过程.OceanBase 中,连接数据分布在不同存储节点,连接之前,将分散的数据全部拉

取到查询节点本地进行排序,排序完毕后进行合并连接,这种排序合并连接策略存在如下问题:(1) 没有对连接

数据中无用数据块进行剪枝;(2) 在查询节点进行集中式排序;(3) 在查询节点进行集中式全局合并连接.在处

理大数据量连接情况下,这些问题造成大量网络代价以及本地 CPU 和 IO 代价.一些文献

[4−7]

针对问题 2 和问题

3 提出了并行排序策略,将连接数据进行分区,分别迁移到多个进程上进行并行排序以及局部连接,最后全局合

并连接的策略.但并没有针对第 1 个问题给出很好的解决策略.

排序合并连接需要连接数据有序,通过比较两边连接数据是否符合连接条件决定输出结果.在数据量大的

情况下,两边连接数据大概率存在多个无效数据块,这些数据块不会产生输出结果,但会产生大量额外代价.如

两个有序序列 A(−1000000,...−1,0,1, 2,...,1000)和 B(−2000000, ...,−1000001,0,1,2,...,1000)进行等值合并连接,按照

传统策略,需要至少比较 1000000+1 000×2 次.但 A 的子区间[−1000000,0] 和 B 的子区间[−2000000,−1000001]无

连接结果输出,为无用数据块,因此对于此区间内的比较完全没有必要,并且分布式环境下会增加额外昂贵的网

络代价.如果能够将这些无用数据提前进行预处理,将其剪枝掉,将会大大减少连接代价.图 1 为在 OceanBase 中

进行排序合并连接实验时未剪枝(normal)和人工剪枝(prune)前后性能对比,连接对象为两个数据量为 1 000 000

的字符串序列.其中,重复度指匹配连接的数据占原始数据的百分比.

100

150

200

250

0 0.01 0.02 0.05 0.1 0.2 0.5 1

时间(s)

重复度(%)

normal

rune

Fig.1 Performance comparation of merge-join bet ween pru ne and non-pr une

图 1 未剪枝与剪枝前后合并连接性能对比

of 18

免费下载

软件学报计算机技术

关注

评论