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

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

内存数据库在磁盘上的数据存储布局通常只考虑 I/O 访问效率, 在内存上存储布局则需要考虑在不同 NUMA
架构下通过行组内的 NUMA-conscious Radix 分区来提高数据访问的局部性.
2.2 NUMA-conscious 共享中间结果集复制策略
NPO 算法和向量连接算法使用共享哈希表和向量, 创建哈希表/向量及探测操作中会产生跨 NUMA 访问延
迟, 为减少跨 NUMA 访问延迟, 设计了 3 个共享哈希表/向量复制策略, 通过在 NUMA 节点复制较小 R 表生成的
哈希表/向量实现 NUMA 内的哈希/向量连接操作.
2.2.1 细粒度复制策略 (fine-grained replication)
如图 4(a) 所示, 每个 NUMA 节点中 R 表分区中的记录在各 NUMA 节点并发地创建哈希表/向量, 从而在探
测阶段使每个 NUMA 节点中的 S 表分区记录可以执行 NUMA 内的哈希/向量连接. 该策略通过牺牲哈希表/向量
创建阶段的跨 NUMA 写代价来消除探测阶段的跨 NUMA 读延迟, 适用于连接探测阶段的代价远高于创建阶段的
应用场景. 基于细粒度复制策略的 NUMA 节点内私有哈希表或私有向量连接算法如算法 2 所示.

R R

Build Build
... ...
Replicated HT Replicated HT Replicated HT Replicated HT
... ... ... ... ... ... ... ...
Probe Probe

S S
(a) Fine-grained replication strategy (b) Coarse-grained replication strategy
R
Partition

Build

... ... ... ...
Probe

S
(c) Partitioned replication strategy
图 4 NUMA-conscious 连接实现技术

算法 2. 基于细粒度复制策略的 NUMA 节点内私有哈希表或私有向量连接算法.

Input: R 表, S 表, 私有哈希表 (pht k ) 或私有向量 (pv k ), k ∈ [0, N), N 对应于 NUMA 节点数;
Output: sum: 连接成功计数.
1. build 阶段
2. for thread k in all threads do
3. start ← startoffset k in R 表
4. i ← 1, location ← i + start
5. repeat
6. key ← R.tuple[location].key
7. index ← (Hash(key) OR key)