Page 442 - 《软件学报》2025年第12期
P. 442

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


                 引为下标的内存向量        (数组), 因此相对于哈希表而言更小, 具有更高的              cache 局部性, 从而能够更好地适应当前
                 CPU L3 cache 容量持续增长的硬件发展趋势; 另一方面, 键值-地址映射消除了哈希探测的哈希值计算、记录遍历
                 和键值匹配代价, 使得       CPU cycle 消耗更低, 从而降低了     CPU  对复杂指令性能的依赖, 能更好地自适应当前              CPU
                 核心数量快速增长的趋势. 向量连接算法与              NPO  算法相似, 均依赖对共享数据结构           (共享向量) 的访问, 但     NPO
                 算法使用较大的哈希表从而具有较高的哈希探测代价, 而向量连接算法具有更好的                           cache 局部性和内存访问性能,
                 在  NUMA  架构下具有趋势相近但幅度不同的性能特征. 在硬件方面, 不同                  CPU NUMA  架构的差异对算法性能及
                 NUMA  优化技术的需求不同, 例如         ARM  和  AMD CPU  的跨  NUMA  访问延迟相对于     Intel CPU  较高, 不同代的
                 CPU  跨  NUMA  访问延迟也有较大的差异, 相同的         NUMA  优化技术对不同算法、不同          CPU  架构、不同的负载有
                 不同的性能特征. 本文设计了         NUMA-conscious (NUMA  感知) 和  NUMA-oblivious (非  NUMA  感知) 外键连接算法
                 库, 对不同的数据布局策略、不同的哈希表、向量创建方法、NUMA-conscious 协同分区                       (co-partition) 方法等进
                 行深入研究, 探索不同      NUMA  架构下的外键连接优化算法的性能特征. 本文的贡献主要体现在以下几个方面.
                    • NUMA-conscious 优化技术受多种硬件因素影响, 如不同           CPU  架构跨  NUMA  访问延迟、cache 大小和效率
                 等. 本文对比了    5  个不同的  CPU  平台, 验证了不同    NUMA  优化技术在不同       CPU  平台上的性能特征, 提供了不同
                 架构、不同硬件配置       CPU  平台上不同的     NUMA  优化算法选择策略, 为数据库查询优化器提供了第一手的连接算
                 法性能数据.
                    • 研究揭示了不同外键连接算法对           NUMA   架构有不同的依赖强度. 如        NPO  算法对  NUMA  架构有强依赖性,
                 PRO  算法对  NUMA  架构有中等依赖性, 向量连接算法对           NUMA  架构依赖性最弱.
                    • 提出一种新的连接基准. 与相关研究通常采用|R|=|S|或|S|=10×|R|的相对比例不同的是, 本文所提出的连接基
                 准采用固定    S  表长度  (如|S|=SF×6M, 本文中设置   SF=200, 对应  12  亿条记录) 与  TPC-H  和  SSB  基准中事实表数据
                                    5
                                      29
                 量相当, |R|大小设置为     2 –2 行, 模拟代表性数据库基准         TPC-H、SSB、TPC-DS   中维表长度的变化范围, 覆盖
                 OLAP  负载中代表性的维表和事实表数据范围, 使连接操作性能可以映射到代表性基准查询中. 连接基准测试揭
                 示了连接性能与      CPU  架构、cache 大小、NUMA    延迟的相关性, 实验结果表明, 良好的模式设计能够简化                 NUMA
                 优化的复杂度, 提高连接性能.
                    实验结果给出如下结论: NUMA-conscious 数据布局能够更充分利用                NUMA  架构的内存带宽性能; 向量连接
                 算法不仅具有     hardware-oblivious 硬件自适性能, 又具有  NUMA-oblivious 特性, 相对于  NUMA  延迟而言    cache 效
                 率对性能有更显著的影响, 当跨          NUMA  访问延迟降低时, NUMA-conscious 优化收益降低; 通用的哈希连接算法
                 受  NUMA  架构影响较大, 在    NUMA  架构上设计轻量      SN NUMA  系统  (shared-nothing NUMA) 能够更有效地降低
                 跨  NUMA  访问延迟对性能的影响, 提高        NUMA  内存访问的局部性.

                  1   技术背景

                    本节首先介绍两个哈希连接算法和向量连接算法, 然后介绍不同                      CPU NUMA  架构下的数据分区及连接基准
                 设计.
                  1.1   连接实现技术
                    本文主要聚焦于两类连接算法: 哈希连接算法和向量连接算法. 哈希连接的                        NPO  算法和  PRO  算法来源于文
                 献  [1] 的源码, 向量连接算法基于      NPO  源码扩展设计. NPO    哈希连接算法包含两个微操作: 一是具有弱局部性特
                 征的顺序表扫描操作        (外键表  S), 另一个是具有强局部性特征的哈希表操作              (主键表   R  上创建哈希表). 弱局部性
                 的表扫描操作依赖内存带宽性能, 需要将数据分布在不同                  NUMA  节点并由本地      NUMA  节点的  CPU  线程访问, 来
                 提高内存访问局部性. 强局部性的哈希表操作既涉及                 cache 局部性也涉及内存局部性, cache 局部性取决于哈希表
                 相对于   L3 cache 大小. 当哈希表较小或    L3 cache 较大时, cache 的自动缓存机制保证哈希表访问具有较好的              cache
                 局部性, 受  NUMA   架构影响较小. 当哈希表超过         L3 cache 大小时会产生跨    NUMA  访问延迟, 优化策略需要平衡
                 跨  NUMA  访问, 或者通过额外的分区操作来提高数据访问的               NUMA  局部性, 从而减少跨     NUMA  访问延迟. 如图    1
   437   438   439   440   441   442   443   444   445   446   447