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

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

CRVJ 连接算法采用粗粒度复制方法, 在创建阶段每个本地 NUMA 线程首先在本地 NUMA 节点创建连接向
量, 然后将整个连接向量复制到其他 NUMA 节点上. 在探测阶段, 每个 S 表记录探测本地 NUMA 节点中的多个
连接向量完成连接操作. CRVJ 算法通过粗粒度复制优化了跨 NUMA 访问延迟, 但在探测阶段增加了多次向量探
测延迟.

表 3 NUMA-conscious 连接算法描述

算法分类 算法缩写 算法描述
NPO 无分区哈希连接算法, no-partitioning hash join (with --basic-numa option)
基准连接算法 (默认和--basic-
PRO Radix分区哈希连接算法, Radix join (with --basic-numa option)
numa优化选项)
Vector Join 向量连接算法, vector index lookup based join (with --basic-numa option)
细粒度哈希表复制NPO算法, fine-grained replicated hash table based no partition
FRHNPO
hash join
FRVVJ 细粒度复制向量连接算法, fine-grained replicated vector based vector join
NUMA-conscious连接算法
CRVJ 粗粒度复制向量连接算法, coarse-grained replicated vector join
基于排序的粗粒度复制向量连接算法, sorted vector based coarse-grained replicated
SVCRVJ
vector join
PSNNPO 基于分区的NUMA SN集群NPO连接算法, partitioned shared-nothing NPO
NUMA SN集群并行连接算法 PSNVJ 基于分区的NUMA SN集群向量连接算法, partitioned shared-nothing vector join
RRNPO 基于R表全复制的NUMA SN集群NPO连接算法, replicated R table NPO
NUMA合并细粒度哈希表复制NPO算法, fine-grained replicated hash table based
FRHNPONM
no partition hash join for NUMA merge
NUMA合并细粒度复制向量连接算法, fine-grained replicated vector based vector
NUMA合并连接算法 FRVVJNM
join for NUMA merge
NUMA合并粗粒度复制向量连接算法, coarse-grained replicated vector join for
CRVJNM
NUMA merge

SVCRVJ 算法是一个定制化的向量连接优化技术. 在算法的数据生成器中 R 表主键为连续代理键, 但乱序存
储, 每个 NUMA 节点上 R 表数据分片创建的向量都覆盖全部的连接向量数值范围, 因此产生连接向量冗余创建
和访问代价. SVCRVJ 算法首先对 R 表按连接键排序, 数据均匀分布到不同的 NUMA 节点形成连续且不相交的
数据子集, 然后 NUMA 节点内的线程创建本地连接向量, 连接向量复制到其他 NUMA 节点构成物理独立逻辑连
接的连接向量, NUMA 节点内的 S 表记录根据键值映射到唯一的连接向量分片上完成向量连接操作. 相对于
CRVJ 算法, SVCRVJ 算法通过 R 表有序的连接键消除了 S 表探测多个连接向量的代价. 数据库系统通常为主键
创建聚集索引, 采用 SVCRVJ 算法时可以消除预排序代价, 降低创建连接向量代价.
3.3 NUMA SN 集群连接实现技术
n
PSNNPO 算法将 R 表和 S 表按主键和外键 Radix 位划分为 2 个分区, 分布式存储在 2 个 n NUMA 节点上. 每
个 NUMA 节点作为轻量 SN 集群, 执行本地 R 表和 S 表分片上的 NPO 连接算法. PSNVJ 算法与 PSNNPO 算法类
似, NUMA 分区后执行 NUMA 节点间并行的向量连接算法. RRNPO 算法仅对 S 表 NUMA 分区, R 表采用全复制
方法冗余存储在各 NUMA 节点上, 适合于 R 表较小的连接负载.

3.4 NUMA 节点合并连接实现技术
FRHNPONM 算法和 FRVVJNM 算法是应用于 ARM 平台的 NUMA 节点合并连接算法. 以 FRHNPO 和
FRVVJ 连接算法为基础, 将一个物理芯片上的两个逻辑 NUMA 节点合并为一个逻辑 NUMA 节点, 降低跨 NUMA
并发写操作数量. CRVJNM 算法是面向 ARM 平台定制化的 CRVJ 算法, 通过合并 NUMA 节点, 可将粗粒度连接
向量的复制和探测的数量减少 50%, 其代价是在创建阶段增加了一部分芯片内跨 NUMA 访问延迟. ARM 和新一
代 AMD CPU 支持片上多 NUMA 节点, 基于 NUMA 节点的 SN 并行连接算法, 所需的 NUMA 节点间复制的内存
开销和计算代价更高. 该算法用于评估是否可以通过减少逻辑 NUMA 节点数量, 从而获得更高的存储空间利用率