面向多表数据连接投影和连接顺序的优化方法

doi:10.3778/j.issn.1673-9418.2009099

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (1): 106-119.DOI: 10.3778/j.issn.1673-9418.2009099

面向多表数据连接投影和连接顺序的优化方法

宗枫博¹, 赵宇海¹^,⁺(), 王国仁², 季航旭¹

1.东北大学计算机科学与工程学院,沈阳 110169
2.北京理工大学计算机学院,北京 100081

收稿日期:2020-08-06 修回日期:2020-10-16 出版日期:2022-01-01 发布日期:2020-11-06
通讯作者: + E-mail: zhaoyuhai@mail.neu.edu.cn
作者简介:宗枫博（1995—）,男,河北唐山人,硕士研究生,主要研究方向为大数据。
赵宇海（1975—）,男,辽宁鞍山人,博士,教授,博士生导师,CCF高级会员,主要研究方向为数据挖掘、机器学习。
王国仁（1966—）,男,湖北崇阳人,博士,教授,博士生导师,CCF高级会员,主要研究方向为不确定数据管理、分布式查询处理与优化技术等。
季航旭（1990—）,男,辽宁沈阳人,博士研究生,主要研究方向为分布式计算、网络表示学习。
基金资助:
科技部国家重点研发计划(2018YFB1004402);国家自然科学基金(61772124)

Optimization Method of Projection and Order for Multiple Tables Join

ZONG Fengbo¹, ZHAO Yuhai¹^,⁺(), WANG Guoren², JI Hangxu¹

1. School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China
2.School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China

Received:2020-08-06 Revised:2020-10-16 Online:2022-01-01 Published:2020-11-06
About author:ZONG Fengbo, born in 1995, M.S. candidate. His research interest is big data.
ZHAO Yuhai, born in 1975, Ph.D., professor, Ph.D. supervisor, senior member of CCF. His research interests include data mining and machine learning.
WANG Guoren, born in 1966, Ph.D., professor, Ph.D. supervisor, senior member of CCF. His research interests include uncertain data mana-gement, distributed query processing and opti-mization technologies, etc.
JI Hangxu, born in 1990, Ph.D. candidate. His research interests include distributed computing and network representation learning.
Supported by:
National Key Research and Development Program of China(2018YFB1004402);National Natural Science Foundation of China(61772124)

摘要/Abstract

摘要：

多表连接运算是大数据处理中常见的运算。类似于数据库运算中常见的连接操作,多表连接运算的顺序会对计算资源和传输资源的消耗产生巨大影响。对多表连接顺序的优化是一个经典的优化问题,同时每次连接中表的投影结果大小也会影响节点间传输的数据体积,因此整体连接的顺序和每次连接的投影关系都会对连接效率产生显著的影响,而在传统的优化策略中,往往不会考虑到中间投影关系的取舍问题,以及基于中间投影关系而对最优连接策略产生的影响。针对这个问题,建立了一种连接关系索引,能够在构建优化连接策略中调整每次连接的投影关系,及时删除冗余列,减少对传输资源的消耗,同时基于投影关系的优化调整连接顺序的优化策略,从全局考量上尽可能地同时减少对传输资源和计算资源的消耗。该优化策略在Flink系统实现后进行了实验,结果表明有显著的优化效果。

关键词: 大数据, 连接优化, 投影优化

Abstract:

Multiple tables join operation is a common operation in big data processing. Similar to the common Join operations in database operations, the order of multiple tables join operation will have a great impact on the consumption of computing resources and transmission resources. The optimization of the join order of multiple tables is a classical optimization problem, and the size of the projection result of the table in each join will also affect the data volume transmitted between nodes. Therefore, the overall connection order and the projection relationship of each connection will have a significant impact on the join efficiency. But in the traditional optimiza-tion strategy, the choice of intermediate projection relation, and the influence on the optimal join strategy based on the intermediate projection relation are often not considered. In order to solve this problem, this paper establishes a connection relation index, which can adjust the projection relation of each join in the construction optimization connection strategy, delete redundant columns in time, and reduce the consumption of transmission resources. At the same time, the optimization strategy of adjusting join order based on projection relation can reduce the consumption of transmission resources and computing resources as much as possible. After the implementation in the Flink system, the optimization strategy is tested, and the results show that it has a significant optimization effect.

Key words: big data, join optimization, project optimization

中图分类号:

TP311.133.1

宗枫博, 赵宇海, 王国仁, 季航旭. 面向多表数据连接投影和连接顺序的优化方法[J]. 计算机科学与探索, 2022, 16(1): 106-119.

ZONG Fengbo, ZHAO Yuhai, WANG Guoren, JI Hangxu. Optimization Method of Projection and Order for Multiple Tables Join[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(1): 106-119.

图/表 34

图1 原连接树

Fig.1 Origin join tree

图2 改变连接顺序

Fig.2 Modify join order

图3 RR传输策略

Fig.3 RR ship strategy

图4 BF传输策略

Fig.4 BF ship strategy

图5 SM连接策略

Fig.5 SM join strategy

图6 HH连接策略

Fig.6 HH join strategy

图7 列保留示例

Fig.7 Example of column retention

图8 原连接树

Fig.8 Origin join tree

图9 优化后的连接树

Fig.9 Optimized join tree

表1 Source表对应的TPC-H表

Table 1 TPC-H table corresponding to Source table

Source表	TPC-H表
Source₀	lineitem
Source₁	orders
Source₂	partsupp
Source₃	part
Source₄	customer
Source₅	supplier
Source₆	nation
Source₇	region

图10 对列6的溯源结果

Fig.10 Result of tracing column 6

图11 对Join2表中的列3溯源得到索引

Fig.11 Index of tracing column 3 in Join2 table

图12 对Join3表中的列6溯源得到索引

Fig.12 Index of tracing column 6 in Join3 table

图13 对Join4表中的列6溯源得到索引

Fig.13 Index of tracing column 6 in Join4 table

图14 原连接树的连接关系索引

Fig.14 Join relations of origin join tree

图15 连接索引查询

Fig.15 Query by join index

图16 删除冗余列及所在索引

Fig.16 Delete redundant columns and indexes

图17 TPC-H关系模式图

Fig.17 Relational schema of TPC-H

表2 TPC-H表数据体积及分布

Table 2 Data size and distribution of TPC-H tables

连接表	不同数据集规模下的连接表大小
连接表	100 MB	500 MB	600 MB	700 MB	800 MB
lineitem	71 MB	360 MB	433 MB	506 MB	579 MB
Orders	17 MB	82 MB	98 MB	115 MB	131 MB
Partsupp	12 MB	57 MB	68 MB	80 MB	91 MB
Customer	2.4 MB	12 MB	14 MB	17 MB	19 MB
Part	2.3 MB	12 MB	14 MB	17 MB	19 MB
Supplier	140 KB	692 KB	828 KB	964 KB	1.1 MB
Region	4.0 KB	4.0 KB	4.0 KB	4.0 KB	4.0 KB
nation	4.0 KB	4.0 KB	4.0 KB	4.0 KB	4.0 KB

图18 5表连接的优化前后执行时间

Fig.18 Execution time before and after optimization in 5 tables join

图19 6表连接的优化前后执行时间

Fig.19 Execution time before and after optimization in 6 tables join

图20 7表连接的优化前后执行时间

Fig.20 Execution time before and after optimization in 7 tables join

图21 8表连接的优化前后执行时间

Fig.21 Execution time before and after optimization in 8 tables join

图22 不同表数下平均执行时间优化比例

Fig.22 Average execution time optimization ratio of different tables

图23 5表连接优化前后的中间数据传输体积

Fig.23 Intermediate data ship size before and after optimization in 5 tables join

图24 6表连接优化前后的中间数据传输体积

Fig.24 Intermediate data ship size before and after optimization in 6 tables join

图25 7表连接优化前后的中间数据传输体积

Fig.25 Intermediate data ship size before and after optimization in 7 tables join

图26 8表连接优化前后的中间数据传输体积

Fig.26 Intermediate data ship size before and after optimization in 8 tables join

图27 冗余率为0时的中间数据传输体积优化比例

Fig.27 Intermediate data ship size optimization ratio in redundant ratio 0

图28 冗余率为0时的执行时间优化比例

Fig.28 Execution time optimization ratio in redundant 0

图29 不同冗余率下执行时间优化比例

Fig.29 Execution time optimization ratio in different redundant ratios

图30 不同冗余率下数据传输优化比例

Fig.30 Data ship optimization ratio in different redundant ratios

表3 0%和9.70%冗余率下中间节点的数据发送量

Table 3 Data ship of intermediate nodes in 0% and 9.70% redundant ratios

中间节点	不同冗余率下的数据发送量
中间节点	0%	9.70%
JoinNode0	54.4 MB	54.4 MB
JoinNode1	320 MB	411 MB
JoinNode2	205 MB	594 MB
JoinNode3	228 MB	228 MB
JoinNode4	44.7 GB	62.6 GB
JoinNode5	44.7 GB	62.6 GB
JoinNode6	44.2 GB	44.2 GB

图31 不同并行度下执行时间优化比例

Fig.31 Execution time optimization ratio in different parallelism

参考文献 14

[1]	KADKHODAEI H, MAHMOUDI F. A combination me-thod for join ordering problem in relational databases using genetic algorithm and ant colony[C]// Proceedings of the 2011 IEEE International Conference on Granular Computing,Taiwan, China, Nov 8-10, 2011. Washington: IEEE Computer Society, 2011: 312-317.
[2]	WILSCHUT A N, FLOKSTRA J. APERS P M G. Parallel evaluation of multi-join queries[C]// Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, May 22-25, 1995. New York: ACM, 1995: 115-126.
[3]	STEINBRUNN M, MOERKOTTE G, KEMPER A. Heuris-tic and randomized optimization for the join ordering pro-blem[J]. The VLDB Journal, 1997, 6(3):191208.
[4]	VELLEV S. Review of algorithms for the join ordering pro-blems in database query optimization[J]. Information Tec-hnologies and Control, 2009, 1:3240.
[5]	SELINGER P G, ASTRAHAN M M, CHAMBERLIN D D, et al. Access path selection in a relational database manage-ment system[C]// Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, May 30-Jun 1, 1979. New York: ACM, 1979: 23-34.
[6]	IOANNIDIS Y E, WONG E. Query optimization by simulated annealing[J]. ACM SIGMOD Record, 1987, 16(3):9-22. DOI URL
[7]	LI N N, LIU Y J, DONG Y F, et al. Application of ant colony optimization algorithm to multi-join query optimiza-tion[C]// LNCS 5370: Proceedings of the 3rd International Symposium on Intelligence Computation and Applications, Wuhan, Dec 19-21, 2008. Berlin, Heidelberg: Springer, 2008: 189-197.
[8]	DE JONG EDWIN D, POLLACK J B. Ideal evaluation from coevolution[J]. Evolutionary Computation, 2004, 12(2):159192.
[9]	SHEKITA E J, YOUNG H C, TAN K L. Multi-join optimi-zation for symmetric multiprocessors[C]// Proceedings of the 19th International Conference on Very Large Data Bases, Dublin, Aug 24-27, 1993. San Mateo: Morgan Kaufmann, 1993: 479-492.
[10]	AFRATI F N, ULLMAN J D. Optimizing joins in a map-reduce environment[C]// Proceedings of the 13th Interna-tional Conference on Extending Database Technology, Lausanne, Mar 22-26, 2010. New York: ACM, 2010: 99-110.
[11]	HÜSKE F. Peeking into Apache Flink’s engine room[EB/OL].(2015-03-13) [2020-05-26]. https://flink.apache.org.
[12]	BLAKELEY J A, MARTIN N L. Join index, materialized view, and hybrid-hash join: a performance analysis[C]// Proceedings of the 6th International Conference on Data Engineering, Los Angeles, Feb 5-9, 1990. Washington: IEEE Computer Society, 1990: 256-263.
[13]	COLE R. Parallel merge sort[J]. SIAM Journal on Com-puting, 1988, 17(4):770-785.
[14]	TPC Benchmark^TM H standard specification revision 2.17.1[J]. San Francisco: Transaction Processing Performance Council, 2014.

[1]	陈剑南, 杜军平, 薛哲, 寇菲菲. 基于多重注意力的金融事件大数据精准画像[J]. 计算机科学与探索, 2021, 15(7): 1237-1244.
[2]	赵学武, 吴宁, 王军, 阮利, 李玲玲, 徐涛. 航空大数据研究综述[J]. 计算机科学与探索, 2021, 15(6): 999-1025.
[3]	郭子菁, 罗玉川, 蔡志平, 郑腾飞. 医疗健康大数据隐私保护综述[J]. 计算机科学与探索, 2021, 15(3): 389-402.
[4]	郑娅峰, 赵亚宁, 白雪, 傅骞. 教育大数据可视化研究综述[J]. 计算机科学与探索, 2021, 15(3): 403-422.
[5]	王沐贤，丁小欧，王宏志，李建中. 基于相关性的多维时序数据异常溯源方法[J]. 计算机科学与探索, 2021, 15(11): 2142-2150.
[6]	包盼盼，陶传奇，黄志球. 面向开源源码大数据的数据质量研究[J]. 计算机科学与探索, 2020, 14(3): 389-400.
[7]	胡健，徐锴滨，毛伊敏. 基于加权网格和信息熵的并行密度聚类算法[J]. 计算机科学与探索, 2020, 14(12): 2094-2107.
[8]	赵一宁，肖海力. 国家高性能计算环境事件流系统的设计[J]. 计算机科学与探索, 2019, 13(3): 374-382.
[9]	刘正涛，王建东. Web大数据系统数据源选择[J]. 计算机科学与探索, 2018, 12(3): 360-369.
[10]	张大坤，任淑霞. 超图可视化方法研究综述[J]. 计算机科学与探索, 2018, 12(11): 1701-1717.
[11]	鲁鹏凯，江大伟，陈珂，寿黎但，陈刚. RStore：基于BigTable的关系数据模型存储系统[J]. 计算机科学与探索, 2018, 12(10): 1547-1558.
[12]	王永坤，金耀辉. 数据平台的设计和实现以及大赛中的应用[J]. 计算机科学与探索, 2018, 12(1): 39-48.
[13]	邓诗卓，信俊昌，聂铁铮，王国仁. 双缀过滤的大数据相似性连接处理算法[J]. 计算机科学与探索, 2017, 11(8): 1235-1245.
[14]	汪忠国，吴敏，谭芳芳. 稀疏混合图随机跳跃Web对象多标签半监督分类[J]. 计算机科学与探索, 2017, 11(7): 1166-1174.
[15]	史荧中，汪菊琴，许敏，王士同. 正则化多任务学习的快速算法[J]. 计算机科学与探索, 2017, 11(6): 988-997.

面向多表数据连接投影和连接顺序的优化方法

Optimization Method of Projection and Order for Multiple Tables Join

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 34

参考文献 14

相关文章 15

编辑推荐

Metrics