DSE精选文章
Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement
Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE近期发文。在现代分析引擎中，高效执行大规模分布式数据上的连接操作至关重要，但涉及大量网络传输与远程输入输出等代价高昂的混洗操作，往往会制约性能。现有数据布局技术在处理复杂多表连接时存在诸多不足：分配键的设定方式缺乏灵活性、聚类键的选择并非最优且需要大量人工调优、与下游连接策略的协同优化效果较差。针对这些问题，本文提出一种新型的查询感知型数据布局 ——PAC 树（分区对齐协同连接树），以端到端的方式全面克服上述局限性。PAC树采用双层结构：上层通过对事实表采用多种分配键进行数据复制，提升不同连接模式下的数据共置性；下层则实施基于谓词感知分割的高级多维分区策略，实现细粒度的分片内数据过滤。借助 PAC 树生成的统计信息，本文进一步提出两项优化算法：一是在内存约束下构建协同分区的块分组算法，二是面向多表连接的基于PRIM的连接重排序策略，二者共同大幅降低混洗开销。在真实 Spark 集群上开展的实验表明：相较于当前主流的数据布局方案，PAC 树可将查询延迟降低高达 45.7%，吞吐量提升至原来的2倍，在连接密集型工作负载场景下的优化效果尤为显著。查询感知型数据分区是指基于收集到的查询模式，为每张数据表构建对应的数据布局。该布局由多个逻辑分区构成，能够在查询执行阶段实现更高效的数据检索。为便于构建和维护互不重叠的逻辑分区，通常会采用一种索引树结构。由于连接操作往往是分布式查询处理中开销最大的算子，因此相关研究提出了分层连接树（详见定义 1），用于优化多表连接任务。定义1（分层连接树）。连接树 T 是一种粗粒度索引结构，其每个非叶子节点存储元数据，包括其子节点的数据值域及其对应的存储地址；每个叶子节点对应一个逻辑分区 R，且叶子节点的数量等于分区数量。该连接树分为两个层级构建：顶层 Tt 基于连接属性构建，底层Tb 基于所有高选择性属性构建。该结构的形式化表示为T=Tt⋈Tb。基于上述研究背景，本文对所解决的核心问题进行形式化定义。问题 1（工作负载感知的逻辑分区优化）。给定n张数据表的集合{M1,……,Mn}以及一组代表性历史工作负载QH ，假设在足够长的时间周期内，未来高频工作负载QF满足QF ≈QH。本问题的优化目标为：为每张数据表Mi 构建一颗连接树Ti ，并基于该连接树将数据划分为布局Ri ,使得在最终得到的布局集合R={R1,……,Rn}上执行工作负载QH的总I/O代价最小化，形式化表述如下}：其中，Ti (Q) 表示根据捕获的工作负载模式扩展得到的连接树；Ri (Ti ) 表示由数据表 Mi 的连接树Ti 所生成的逻辑分区；代价函数 C (⋅,QH ) 用于估算在最终的分区布局上执行工作负载 QH所产生的总 I/O 开销。并且，该问题被证明为是NP难问题。首先，一个专用的实时组件（后台规划器）会周期性监控并采集来自三类数据源的关键特征：查询工作负载、数据库基础配置、以及数据表的采样数据。具体来说：分析查询日志，提取被访问过的列、过滤谓词、连接键及其出现频率等信息；然后从数据库配置中获取计算节点内存容量、可用节点数量、存储节点容量、典型分区文件大小（如HDFS中每个文件256MB）、网络延迟等参数；最后从采样表数据中获取存储引擎生成的“.part”文件详情，包括数据集大小、采样比例、表结构、列类型和数据分布。PAC 树利用历史遥测数据为每张表确定最优数据布局。分层的 PAC 树结构充当数据路由器，用于实例化数据块。每张表可以基于不同的列键构建一棵或多棵 PAC 树，树的数量由复制因子决定。通过构建多份数据布局副本，PAC 树能够最大化协同分区的机会，从而支持更多的本地连接操作。查询优化器将PAC树作为索引，为传入的查询快速的生成更优的查询计划。其中包括：快速搜索相关数据块以执行过滤操作；确定表的最优连接顺序。实验评估了三种包含复杂 SQL 查询的标准 OLAP 工作负载，TPC-H 和 TPC-DS 数据集分别在 1、10、20、50 和 100 的比例因子下运行，此外，还在 6.9GB 的 IMDB 数据集上运行了连接顺序基准测试（JOB）。
为了回答RQ1，本文将PAC-Tree与PAW和AD-MTO(SOTA基线)进行了比较。图2说明了PAC-Tree实现了很强的跨数据库泛化。由于直接测量查询延迟受磁盘读取率、工作内存和缓冲区缓存的影响，因此本文在这里使用扫描的数据量作为一个健壮的度量。在使用来自不同应用程序数据集的表模式的各种工作负载中，与PAW相比，PAC-Tree实现了高达67%的扫描数据减少，与AD-MTO相比，PAC-Tree实现了高达45%的减少。模型效率分析。只有在能够有效地识别和组织数据布局时，实例优化的数据布局才有价值。本文分析了PAC-Tree的离线模型运行时间和数据路由时间以及比较方法。如图3所示，“数据路由时间”测量通过联接树对整个数据集进行本地分区所需的时间(即，将元组分配给块)。这两个时间通常随着候选连接树的数量而增长：AD-MTO的平均模型运行时间最短(33秒)，而PAC-Tree需要的时间最长(81秒)。图3. 不同数据布局上执行查询期间观察到的数据扫描度量的比较连接键选择的消融实验。为克服固定连接键的局限性，本文提出了一种基于权重的键选择策略。随后，本文将该策略与其他对比方案的有效性进行验证，实验结果如表 4 所示。边界节点分割的消融实验。为评估面向小节点的边界分割（bs）优化机制的效果，本文对比了启用与禁用该机制时，单表算子的扫描代价。连接顺序优化的消融实验。在完成数据分区与布局构建后，确定最优连接顺序对于多表查询的性能至关，本文将默认查询优化器生成的连接顺序，与基于QDG 驱动的超连接重排序策略进行对比。实验结果表明，PAC树生成的连接顺序性能始终优于默认方案。从单条查询的维度来看，对于包含复杂连接图的查询，该策略带来的性能提升最为显著，这与本文的预期完全一致。本文讨论了优化分布式连接的关键挑战，分布式连接通常受到低效数据布局的限制。从而引入了PAC-Tree，这是一种新颖的分层数据布局，通过查询感知的方法缓解了现有分区方案的局限性。实验证明，PAC-Tree取得了显著的改进，包括与最先进的布局相比，查询延迟减少了45.7%，吞吐量提高了2倍。
刘鹏举，中国人民大学信息学院2025届博士。主要研究方向：表结构优化、查询预估、负载管理等。李翠平，中国人民大学信息学院教授，博士生导师。主要研究方向为数据库、大数据管理与分析、大数据推荐系统等。
陈红，中国人民大学信息学院教授，博士生导师。主要研究方向为数据库、大数据管理与分析、大数据隐私保护等。
Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办，数据库专业委员会承办，施普林格·自然（Springer Nature）出版的开放获取（Open Access）期刊。DSE致力于发表与数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据为研究重点，建设国际学术交流的重要平台，推动学术界和企业界的深度融合。征稿范畴主要包括：数据库系统、大数据管理与分析、大数据治理等相关基础理论、关键技术与系统实践。现任主编（Editors-in-Chief）为数据科学与工程领域的知名专家北京大学崔斌教授和意大利英苏布里亚大学Elena Ferrari教授，现任执行主编(Managing Editor)为数据库专业委员会主任、华东师范大学周傲英教授和浙江大学高云君教授。
目前期刊已被EI、ESCI与SCOPUS收录，2024年影响因子(Impact Factor)为4.6，CiteScore为11.9，在计算机科学应用领域排名前8.87%(84/947)、计算机软件领域排名前9.6%(47/490)、信息系统领域排名前9.7%(46/474)，人工智能领域排名前12.7%(57/450)。欢迎大家免费下载阅读期刊全文，并积极投稿。
原文链接：
https://link.springer.com/article/10.1007/s41019-025-00324-8
