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