Page 466 - 《软件学报》2025年第12期

韩瑞琛 等: NUMA-conscious 外键连接优化技术 5847

5 相关工作

连接是关系数据库中最重要的操作之一, 在数据仓库和 OLAP 中对性能的影响尤为重要, 庞大的事实表与多
个维表之间的连接代价是 OLAP 查询中最大的代价. 当前内存数据库基于多核处理器和大内存平台, 连接算法性
能研究是一个重要的研究热问题. 什么样的连接算法具备最高的性能近年来持续更新中, 新型硬件架构的差异性
增加了问题研究的维度和难度, 硬件架构的特征对连接算法性能研究具有重要的影响作用.
面对硬件技术的飞速发展和硬件差异性的增大, 连接算法性能是 hardware-conscious 还是 hardware-oblivious,
哪个更优的讨论起源于文献 [6], 最初的结论是简单的 hardware-oblivious 连接算法在性能上比更为复杂和依赖硬
件的 hardware-conscious 连接算法有竞争力. 因此鼓励数据库系统开发时采用更简单的无分区哈希连接算法和一
些自动优化技术, 如自动预取等来提升内存连接算法性能. 无分区哈希连接算法需要创建全局共享访问哈希表, 在
创建阶段受多线程并发访问控制代价影响, 在探测阶段受 L3 cache 大小和缓存访问效率影响, 在硬件架构的亲和
性上更倾向于较大共享 L3 cache 架构, 其性能主要受共享哈希表相对于 L3 cache 大小的影响, 内存利用率相对较
高. 连接性能的结论被 Balkesen 等人 [1] 反转, 提出了面向硬件特性的优化与调优策略使 hardware-conscious 的
Radix 分区连接算法性能优于 hardware-oblivious 的无分区哈希连接算法. 其优化技术的基本假设基于连接性能最
主要的影响因素是数据访问的 cache 局部性, cache 容量不足产生会内存访问延迟, 因此需要通过 Radix 分区技术
将大数据集划分为适合 cache 大小的数据集, 来实现 in-cache 连接操作, 从而可以降低连接操作的数据访问延迟.
Radix 分区连接算法是以 CPU 核心的私有 cache 容量为粒度, 进行“分而治之”的优化策略, 可以实现在哈希表创
建阶段无锁化以及在哈希探测阶段降低内存访问延迟. 但分区操作加倍了内存空间消耗, 产生大量内存读写操作
代价. Lang 等人 [8] 进一步探索了 NUMA 架构对连接性能的影响, 提出了 NUMA-aware 无分区哈希连接算法, 其性
能在 4 个 NUMA 节点 64 线程的硬件平台上显著优化 Radix 分区连接算法. Albutiu 等人 [10] 提出了 MPSM (massively
parallel sort-merge join) 连接算法, 基于 NUMA 友好的排序归并算法提高了跨 NUMA 访问效率, 提升了性能.
Balkesen 等人 [2] 进一步优化了无分区哈希连接算法、Radix 分区连接算法和排序归并算法, 实验结果显示哈希连
接算法相对于排序归并连接算法仍然有较好的性能优势. 随着连接优化研究工作的深入, 丰富的连接优化技术给出
了各不相同的连接性能结论, Schuh 等人 [4] 对 13 个基于 NUMA 架构进行优化的连接算法进行了深入的性能对比,
通过统一的连接基准揭示全面的连接算法性能特征, 研究结果表明在现代多 NUMA 架构计算平台上, hardware-
conscious 的 Radix 分区连接算法普遍优于 hardware-oblivious 的无分区哈希连接算法性能, 该研究还指出在 TPC-
H 查询负载中只有较小部分代价发生在连接操作上.
哈希连接性能研究从 CPU 平台扩展到硬件加速器平台, 如 GPU 和 FPGA 平台. He 等人 [11] 研究了集成 CPU-
GPU 处理器架构上的哈希连接优化技术和性能, Halstead 等人 [12] 设计了 FPGA 平台上无分区哈希连接实现技术,
Kara 等人 [13] 开发了 FPGA 平台 Radix 分区哈希连接算法. Rui 等人 [14] 研究了 GPU 上基于排序归并的连接算法,
Sioulas 等人 [15] 的研究揭示了相似的结论, 即 GPU 平台上 Radix 分区哈希连接算法面向硬件特性进行优化, 其性能
较无分区哈希连接算法同样有较大的性能优势. 从多核 CPU 平台到 GPU 和 FPGA 平台, 通用的结论是 hardware-
conscious 的 Radix 分区连接算法性能优于 hardware-oblivious 的无分区哈希连接算法. 但该结论忽略了无分区哈希
连接算法性能依赖于 CPU L3 cache 容量, 随硬件技术迅速提升所产生的性能优势越来越明显. 而优势的 Radix 分区
连接算法由于内存空间利用率低以及物化连接策略难以适应现代流水线处理模型, 因此带来综合性能损失.
哈希连接算法研究工作通常使用定制的连接负载, 相对于现实世界的 SSB、TPC-H、TPC-DS 等数据库连接
负载相比, 在应用中不仅要考虑性能维度, 还需要综合考虑更多的优化因素. Shanbhab 等人 [16] 在 GPU 平台上,
SSB 基准负载实现技术中不再使用 Radix 分区连接算法, 主要原因是在 GPU 平台的连接物化导致显存利用率降
低并且无法支持优化的流水处理模型. 传统的哈希连接和排序归并连接是无索引的等值连接算法, 连接算法的核
心功能是根据外键值在连接表上的等值匹配操作, 没有数据库模式特征的支持, 没有使用面向连接的索引技术, 如
连接索引 [17] 来加速外键值查找性能. 在 OLAP 负载中, 当主键使用代理键时, 外键成为连接索引, 即将 R 表的哈希