计算机工程2026，Vol.52Issue(9)：388-401,14.DOI:10.19678/j.issn.1000-3428.0252206
基于格结构的分布式表连接优化方法
Distributed Table Joining Optimization Method Based on Lattice Structure
摘要
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.关键词
Spark/连接查询/等价类/格结构/数据ShuffleKey words
Spark/join query/equivalence class/lattice structure/data Shuffle分类
信息技术与安全科学引用本文复制引用
尚文,游进国,吴康,付琬婷,李晓武,贾连印..基于格结构的分布式表连接优化方法[J].计算机工程,2026,52(9):388-401,14.基金项目
国家自然科学基金(62462042,62062046). （62462042,62062046）
