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

5824 软件学报 2025 年第 36 卷第 12 期

所示, NUMA-conscious 优化可以分为 NUMA 分区和 NUMA 协同分区两类: NUMA 分区策略将大表 (S) 按
NUMA 节点分区存储, 小表 (R) 根据处理线程动态分配内存页, 从而创建共享哈希表. 当哈希表探测时, S 表分片
上的本地线程并行探测共享哈希表, 此策略只保证 S 表扫描的 NUMA 局部性, 无法保证哈希表创建与探测操作
的 NUMA 局部性; NUMA 协同分区策略首先将 R 表和 S 表按 NUMA 节点数量使用同一哈希函数划分不相交的
分区, 保证每对分区存储在相同 NUMA 节点内, 从而可以保证连接操作在 NUMA 分区内执行. 这种无共享数据分
区策略可以获得最大的 NUMA 局部性, 其代价是动态数据分区的空间和时间开销, 或者依赖表存储模型的静态数
据分区策略.

分区 创建 探测
S S

R R

私有哈希表
跨 NUMA 共享哈希表
R表分区
NUMA NUMA NUMA NUMA NUMA NUMA NUMA NUMA
node0 node1 node2 node3 S表分区 node0 node1 node2 node3
(a) NUMA 分区 (b) NUMA 协同分区
图 1 NUMA-conscious 分区策略

本文使用的 NPO 和 PRO 源码中缺省的执行模式作为 NUMA-oblivious 模式基准, 该模式采用随机内存分配
模式, 在连接中产生远程 NUMA 访问延迟. --basic-numa 执行模式作为 NUMA-conscious 执行模式基准, 在 NUMA
节点平衡地分配内存. 该优化选项保证每个线程在相同的 NUMA 节点生成并扫描 R 表和 S 表数据, 创建 NPO 算
法中共享哈希表和 PRO 算法中的分区. 该 NUMA-conscious 优化模式在动态生成数据集时隐式地由各线程分别
生成 NUMA 节点的本地数据分片. 在真实内存数据库应用场景中 NUMA-conscious 分区策略通常由显式的静态
数据 NUMA 分布存储策略和 NUMA-conscious 扫描操作来支持. NPO 算法需要创建跨 NUMA 节点的共享哈希
表, 在探测阶段需要跨 NUMA 节点访问该哈希表, 可以在 NUMA 节点中复制 R 表创建私有哈希表来优化算法,
以保证哈希探测阶段的 NUMA 局部性, 但代价是增加了 R 表复制存储空间开销和创建多个哈希表的计算代价.
NUMA-conscious PRO 算法的进一步优化 [4] 采用分块 (chunked) 并行 Radix 连接方法, 与原始的跨 NUMA 分区、
NUMA 节点内创建哈希表、NUMA 节点内哈希探测的方法不同, 采用了 NUMA 内分区、跨 NUMA 创建哈希表
和跨 NUMA 哈希探测策略. 该方法性能有 20% 的提升, 主要原因是将原始分区阶段跨 NUMA 随机写记录的代价
转换为从远程 NUMA 节点分块顺序读代价, 降低了 NUMA 访问延迟. Radix 连接采用的是面向 cache 的动态分区
哈希连接方法, 当采用面向 NUMA 节点的分区存储策略时, 动态分区简化为静态分区存储和 NUMA 节点内 Radix
连接执行, 能够较好地消除跨 NUMA 访问延迟, 将该优化技术融合于 NUMA 数据分区技术中, 因此 PRO 算法的
NUMA 优化技术本文不作进一步的研究与比较, 研究重点聚焦于对 cache 和 NUMA 局部性更加敏感的 NPO 算法
和向量连接算法.
如图 2 所示, 基于哈希的 NPO 连接算法和 PRO 连接算法是通用的等值连接方法, 没有发挥数据库模式优化
的优势, 如模式特征等. 向量连接算法则是面向 OLAP 数据库模式特征而设计的优化连接算法 [3] . 向量连接算法
在 R 表主键约束的基础上面向 OLAP 多维数据模型增加了地址映射约束, 使用连续的整数型代理键 (1, 2, 3,…)
作为 R 表主键, R 表创建向量代替传统的哈希表, 由 PAYLOAD 向量构成. 向量单元偏移地址作为默认的主键, 不
需要显式存储, 消除了传统哈希表键值和溢出桶的存储开销. S 表外键直接用作连接索引, 将外键值映射为 R 表向
量对应偏移地址单元完成连接操作, 消除传统哈希探测阶段的计算代价, 包括哈希值计算、哈希值比较和哈希记
录遍历, 并且将 NPO 算法中的复杂哈希桶数据结构 (包含多个 R 表元组 (一个元组通常由一个主键值和一个