Optimization Method of Projection and Order for Multiple Tables Join

doi:10.3778/j.issn.1673-9418.2009099

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (1): 106-119.DOI: 10.3778/j.issn.1673-9418.2009099

• Database Technology • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP311.133.1

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.

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

Figures/Tables 34

Fig.1 Origin join tree

Fig.2 Modify join order

Fig.3 RR ship strategy

Fig.4 BF ship strategy

Fig.5 SM join strategy

Fig.6 HH join strategy

Fig.7 Example of column retention

Fig.8 Origin join tree

Fig.9 Optimized join tree

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

Fig.10 Result of tracing column 6

Fig.11 Index of tracing column 3 in Join2 table

Fig.12 Index of tracing column 6 in Join3 table

Fig.13 Index of tracing column 6 in Join4 table

Fig.14 Join relations of origin join tree

Fig.15 Query by join index

Fig.16 Delete redundant columns and indexes

Fig.17 Relational schema of 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

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

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

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

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

Fig.22 Average execution time optimization ratio of different tables

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

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

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

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

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

Fig.28 Execution time optimization ratio in redundant 0

Fig.29 Execution time optimization ratio in different redundant ratios

Fig.30 Data ship optimization ratio in different redundant ratios

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

Fig.31 Execution time optimization ratio in different parallelism

References 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]	CHEN Jiannan, DU Junping, XUE Zhe, KOU Feifei. Accurate Portrait of Big Data of Financial Events Based on Multiple Attention Mechanism [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(7): 1237-1244.
[2]	ZHAO Xuewu, WU Ning, WANG Jun, RUAN Li, LI Lingling, XU Tao. Overview of Aviation Big Data Research [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(6): 999-1025.
[3]	GUO Zijing, LUO Yuchuan, CAI Zhiping, ZHENG Tengfei. Overview of Privacy Protection Technology of Big Data in Healthcare [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(3): 389-402.
[4]	ZHENG Yafeng, ZHAO Yaning, BAI Xue, FU Qian. Survey of Big Data Visualization in Education [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(3): 403-422.
[5]	WANG Muxian, DING Xiaoou, WANG Hongzhi, LI Jianzhong. Correlation-Based Method for Tracing Multi-dimensional Time Series Data Anomalies [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2142-2150.
[6]	BAO Panpan, TAO Chuanqi, HUANG Zhiqiu. Research on Data Quality of Open Source Code Data [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(3): 389-400.
[7]	HU Jian, XU Kaibin, MAO Yimin. Parallel Density-Based Clustering Algorithm by Using Weighted Grid and Information Entropy [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(12): 2094-2107.
[8]	SONG Baoyan, MENG Yanwei, DING Linlin. KNN Query Method for Location Data Based on Voronoi Partition [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(12): 2015-2028.
[9]	LIU Zhengtao, WANG Jiandong. Data Source Selection for Web Big Data System [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(3): 360-369.
[10]	ZHANG Dakun, REN Shuxia. Survey on Hypergraph Visualization Method [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(11): 1701-1717.
[11]	LU Pengkai, JIANG Dawei, CHEN Ke, SHOU Lidan, CHEN Gang. RStore： Relational Storage System Built on Top of BigTable [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(10): 1547-1558.
[12]	WANG Yongkun, JIN Yaohui. Design of Data Platform and Application in Data Competition [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(1): 39-48.
[13]	DENG Shizhuo, XIN Junchang, NIE Tiezheng, WANG Guoren. Big Data Similarity Join Processing Based on Prefix-Suffix Filtering [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(8): 1235-1245.
[14]	WANG Zhongguo, WU Min, TAN Fangfang. Sparse Mixed Graph Random Jump Transition Policy for Web Object Multi-Label Classification [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(7): 1166-1174.
[15]	WANG Yi, REN Shuxia. Survey on Visualization of Medical Big Data [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(5): 681-699.

Optimization Method of Projection and Order for Multiple Tables Join

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 34

References 14

Related Articles 15

Recommended Articles

Metrics