Distributed Table Joining Optimization Method Based on Lattice Structure

doi:10.19678/j.issn.1000-3428.0252206

Abstract

Abstract:

In distributed computing frameworks, inefficient data transfer in the Shuffle phase has become a key bottleneck in data connectivity. Existing methods have certain limitations in dealing with table joins, such as broadcast joins and Hash joins in Spark are both susceptible to data skewing, which makes the load between nodes unbalanced. Aiming at this problem, the paper focuses on joining aggregated queries, and proposes a table joining method based on lattice structure: by precomputing the storage table partition data in the form of lattice structure, and utilizing the convex set property of equivalence class, i.e., the data cells containing the upper bound of equivalence class and contained by the lower bound of equivalence class, whose aggregation values are equal to the aggregation values of equivalence class, so as to realize the quick matching and calculation. Since the query data cells as a compressed form of basic table data, the data size and skew are more concise and uniform, the article uses the query data cells instead of table data to perform data transfer and connection, which greatly reduces the data Shuffle and computational complexity. The method proposed in the paper has been implemented in Spark, and experiments based on the TPC-H dataset show that: the method of the paper reduces the data Shuffle by about 45.06% in large dataset scenarios, meanwhile, the workload among the nodes is more balanced compared to the benchmark method, and the query response time is shortened by 14.23% on average.

Key words: Spark, join query, equivalence class, lattice structure, data Shuffle

摘要：

在分布式计算框架中, Shuffle阶段的数据传输效率较低已成为数据连接的关键瓶颈。现有方法在处理表连接时存在一定的局限性, 如Spark中的广播连接和哈希连接均易受数据倾斜影响, 使得节点之间负载不均衡。针对此问题, 聚焦于连接聚集查询, 提出一种基于格结构的表连接方法。通过预计算存储表分区数据为格结构形式, 利用等价类的凸集性质, 即包含等价类上界且被等价类下界所包含的数据单元, 其聚集值与等价类聚集值相等, 从而实现对查询语句所映射生成的查询单元进行快速匹配和计算。由于查询单元作为基本表数据的一种压缩形式, 数据大小和倾斜度更加简洁、均匀, 使用查询单元代替基本表数据执行数据的传输和连接, 极大程度地减少了Shuffle阶段的数据大小和计算复杂度。所提方法已在Spark中实现, 基于TPC-H数据集的实验结果表明, 所提方法在大数据集场景中减少数据Shuffle约45.06%, 同时, 节点间的工作负载相较于基准方法更加均衡, 查询响应时间平均缩短了14.23%。

关键词: Spark, 连接查询, 等价类, 格结构, 数据Shuffle

SHANG Wen, YOU Jinguo, WU Kang, FU Wanting, LI Xiaowu, JIA Lianyin. Distributed Table Joining Optimization Method Based on Lattice Structure[J]. Computer Engineering, 2026, 52(9): 388-401.

尚文, 游进国, 吴康, 付琬婷, 李晓武, 贾连印. 基于格结构的分布式表连接优化方法[J]. 计算机工程, 2026, 52(9): 388-401.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0252206

https://www.ecice06.com/EN/Y2026/V52/I9/388

Figures/Tables 15

Fig.1 Query result computing process

Fig.2 Lattice structure

Fig.3 Implementing framework

Fig.4 Comparison of physical query plan between the two methods

Fig.5 Average response time

Fig.6 Network Shuffle read value

Fig.7 The total read value of Shuffle on small dataset

Fig.8 The total read value of Shuffle on large dataset

Fig.9 Comparison of methods at different skews

Fig.10 Comparison of workloads among nodes on large dataset

References 24

1	GU R, HUANG X, DAI H P, et al. Efficient, scalable and robust data shuffle service for distributed MapReduce computing on cloud[C]//Proceedings of the 24th International Conference on High Performance Computing & Communications. Hainan, China: IEEE Press, 2022: 337-346.
2	欧阳恒, 龙士工, 弓晓锋. 交互式框架中多次查询的差分隐私算法. 计算机与数字工程, 2024, 52 (8): 2259-2265, 2322. doi: 10.3969/j.issn.1672-9722.2024.08.003
	OUYANG H , LONG S G , GONG X F . Differential privacy algorithm for multi-query in interactive framework. Computer & Digital Engineering, 2024, 52 (8): 2259-2265, 2322. doi: 10.3969/j.issn.1672-9722.2024.08.003
3	吴恩慈. 广播机制解决Shuffle过程数据倾斜的方法. 计算机系统应用, 2019, 28 (6): 189- 197. doi: 10.15888/j.cnki.csa.006985
	WU E C . Method research to solve Shuffle data skew based on broadcast. Computer Systems & Applications, 2019, 28 (6): 189- 197. doi: 10.15888/j.cnki.csa.006985
4	AFRATI F N, ULLMAN J D. Optimizing joins in a Map-Reduce environment[C]//Proceedings of the 13th International Conference on Extending Database Technology. New York, USA: ACM Press, 2010: 99-110.
5	高锦涛, 李战怀, 杜洪涛, 等. 分布式数据库下基于剪枝的并行合并连接策略. 软件学报, 2019, 30 (11): 3364- 3381.
	GAO J T , LI Z H , DU H T , et al. Strategy of parallel merge join based on prune in distributed database. Journal of Software, 2019, 30 (11): 3364- 3381.
6	LAKSHMANAN L V S, PEI J, HAN J W. Quotient cube[C]//Proceedings of the 28th International Conference on Very Large Databases. Amsterdam: Elsevier, 2002: 778-789.
7	LIN Y T, AGRAWAL D, CHEN C, et al. Llama: leveraging columnar storage for scalable join processing in the MapReduce framework[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. New York, USA: ACM Press, 2011: 961-972.
8	乔百友, 朱俊海, 郑宇杰, 等. 一种基于Spark的多路空间连接查询处理算法. 计算机研究与发展, 2017, 54 (7): 1592- 1602. doi: 10.7544/issn1000-1239.2017.20160558
	QIAO B Y , ZHU J H , ZHENG Y J , et al. A multi-way spatial join querying processing algorithm based on Spark. Journal of Computer Research and Development, 2017, 54 (7): 1592- 1602. doi: 10.7544/issn1000-1239.2017.20160558
9	HAAS P J, HELLERSTEIN J M. Ripple joins for online aggregation[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1999: 287-298.
10	JOGLEKAR M R, PUTTAGUNTA R, RÉ C. AJAR: aggregations and joins over annotated relations[C]//Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. New York, USA: ACM Press, 2016: 91-106.
11	GARCÍA-GARCÍA F , CORRAL A , IRIBARNE L , et al. Efficient distributed algorithms for distance join queries in spark-based spatial analytics systems. International Journal of General Systems, 2023, 52 (3): 206- 250. doi: 10.1080/03081079.2023.2173750
12	AZHIR E , NAVIMIPOUR N J , HOSSEINZADEH M , et al. Join queries optimization in the distributed databases using a hybrid multi-objective algorithm. Cluster Computing, 2022, 25 (3): 2021- 2036. doi: 10.1007/s10586-021-03451-9
13	LIANG F , LAU F C M , CUI H M , et al. RelJoin: relative-cost-based selection of distributed join methods for query plan optimization. Information Sciences, 2024, 658, 120022. doi: 10.1016/j.ins.2023.120022
14	GUO R B, DAUDJEE K. Research challenges in deep reinforcement learning-based join query optimization[C]//Proceedings of the 3rd International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. New York, USA: ACM Press, 2020: 1-6.
15	EICH M , FENDER P , MOERKOTTE G . Efficient generation of query plans containing group-by, join, and groupjoin. The VLDB Journal, 2018, 27 (5): 617- 641. doi: 10.1007/s00778-017-0476-3
16	ZHOU X H , LI G L , CHAI C L , et al. A learned query rewrite system using Monte Carlo tree search. Proceedings of the VLDB Endowment, 2021, 15 (1): 46- 58. doi: 10.14778/3485450.3485456
17	GRAY J , CHAUDHURI S , BOSWORTH A , et al. Data cube: a relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Mining and Knowledge Discovery, 1997, 1 (1): 29- 53. doi: 10.1023/A:1009726021843
18	BASIL JOHN S, LINDNER P, JIANG Z K, et al. Aggregation and exploration of high-dimensional data using the Sudokube data cube engine[C]//Proceedings of the Companion of the 2023 International Conference on Management of Data. New York, USA: ACM Press, 2023: 175-178.
19	JOHN S B , KOCH C . High-dimensional data cubes. Proceedings of the VLDB Endowment, 2022, 15 (13): 3828- 3840. doi: 10.14778/3565838.3565839
20	LAKSHMANAN L V S, PEI J, ZHAO Y. QC-trees: an efficient summary structure for semantic OLAP[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2003: 64-75.
21	徐静文, 游进国, 王全鹍, 等. 数据立方体与频繁项集的统一计算框架研究. 计算机学报, 2023, 46 (4): 780- 802. doi: 10.11897/SP.J.1016.2023.00780
	XU J W , YOU J G , WANG Q K , et al. Unified computing framework for data cubes and frequent itemsets. Chinese Journal of Computers, 2023, 46 (4): 780- 802. doi: 10.11897/SP.J.1016.2023.00780
22	何培蕾. 数据库条件查询的非语义等价关系建模[D]. 昆明: 昆明理工大学, 2024.
	HE P L. Modeling of non-semantic equivalence relationships in conditional database queries[D]. Kunming: Kunming University of Science and Technology, 2024. (in Chinese)
23	何培蕾, 游进国, 王宇轩, 等. 数据库条件查询的非语义等价关系建模. 小型微型计算机系统, 2025, 46 (6): 1523- 1529. doi: 10.20009/j.cnki.21-1106/TP.2024-0126
	HE P L , YOU J G , WANG Y X , et al. Non-semantic equivalence relation modeling of conditional query in databases. Journal of Chinese Computer Systems, 2025, 46 (6): 1523- 1529. doi: 10.20009/j.cnki.21-1106/TP.2024-0126
24	TPS. TPC-H benchmark[EB/OL]. [2025-02-01]. https://www.tpc.org/tpch/.

[1]	HE Yulin, MO Peiheng, HUANG Zhexue, Philippe Fournier-Viger. A Novel Spark Job Scheduling Algorithm Oriented Deadline-Cost Balance [J]. Computer Engineering, 2026, 52(3): 318-331.
[2]	PAN Shunjie, YU Junyang, WANG Longge, LI Han, ZHAI Rui. Spark Adaptive Cache Optimization Strategy Based on the Reuse Degree of RDD [J]. Computer Engineering, 2025, 51(7): 190-198.
[3]	XIA Libin, LIU Xiaoyu, JIANG Xiaowei, SUN Gongxing. Memory Optimization Method for Parallel Computing Framework Based on Distributed Dataset [J]. Computer Engineering, 2023, 49(4): 43-51.
[4]	CAI Ruichu, ZHANG Wenhui, QIAO Jie, HAO Zhifeng. Causal Structure Learning Algorithm Based on Recursive Decomposition [J]. Computer Engineering, 2023, 49(3): 87-94.
[5]	GAO Wanbo, ZHU Junwu, ZHANG Yonglong, ZHANG Xiaowei. Unmanned Vehicle Path Planning Based on Selection Crossover Fireworks Algorithm [J]. Computer Engineering, 2022, 48(11): 314-320.
[6]	SHE Xin, HE Zhenying. Spark-based clique Community Search Algorithm Under Complex Attribute Condition [J]. Computer Engineering, 2021, 47(12): 54-61,70.
[7]	JIA Xiaofang, SANG Guoming, QI Wenkai. Research on ALS Acceleration Algorithm Based on Spark Platform [J]. Computer Engineering, 2020, 46(2): 103-109.
[8]	WANG Mohan, ZHAI Junhai, QI Jiaxing. Large-Scale Condensed Fuzzy K-Nearest Neighbor Algorithm Based on MapReduce and Spark [J]. Computer Engineering, 2020, 46(11): 139-147.
[9]	TONG Manqi, HUANG Jiangsheng, GUO Kun. Comprehensive User Influence Measurement Combining Spark and Recessive Interest [J]. Computer Engineering, 2020, 46(11): 61-69.
[10]	BAI Lingling, NING Zhenhu, XUE Fei, YANG Yongli. Application of Hidden Markov Model in Malicious Domain Name Detection [J]. Computer Engineering, 2019, 45(9): 161-168.
[11]	ZHANG Haoshenglun,LI Chong,KE Yong,ZHANG Shibo. A Distributed User Browse Click Model Algorithm [J]. Computer Engineering, 2019, 45(3): 1-6.
[12]	GAO Quan,WAN Xiaodong. Parallel FP-Growth Algorithm Based on Load Balance [J]. Computer Engineering, 2019, 45(3): 32-35,40.
[13]	ZHANG Wei,WANG Zhijie. Research on Join Operation of Temporal Big Data in Distributed Environment [J]. Computer Engineering, 2019, 45(3): 20-25,31.
[14]	WANG Lili,DENG Li,YU Yue,FEI Minrui. Hybrid Feature Selection Method for Tumor Gene Based on Spark [J]. Computer Engineering, 2018, 44(11): 1-6.
[15]	ZHANG Yutong,WANG Simeng,CAO Jia. Isomorphic Subgraph Search Algorithm Based on Neighborhood Equivalence Class [J]. Computer Engineering, 2017, 43(9): 7-11.

Please choose a citation manager

Content to export