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

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

算法 1. 基于单表分区策略的跨 NUMA 共享哈希表或共享向量连接算法.
数据预处理: 将 S 表水平切割成 N 份数据副本 (N 对应于 NUMA 节点 数), 并分别存储在对应 NUMA 节点的内存中;
Input: R 表, S k 表, k ∈ [0, N), N 是 NUMA 节点数, 共享哈希表 (sht) 或共享向量 (sv);
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)
8. sht[index] ← R.tuple[location] OR sv[index] ← R.tuple[location].payload
9. i ← i + 1, location ← i + start

10. until i > R_slice_length k
11. end for
12. probe 阶段
13. for thread k in all threads do
14. numaid ← get_numa_id(thread k )
15. start ← startoffset k in S numai 表
d
16. i ← 1, location ← i + start
17. sum ← 0
18. repeat
19. key ← S numaid .tuple[location].key
20. index ← (Hash(key) OR key)
21. sum ← sum + (sht[index].payload OR sv[index])
22. i ← i + 1, location ← i + start
23. until i > S numaid _slice_length k
24. end for
25. return sum

2.1.2 协同 NUMA 分区策略
当表 R 和 S 较大时, 远程 NUMA 访问增加了连接延迟, 可以通过协同 NUMA 分区策略将 R 表和 S 表按连接
键 (R 表 PK 主键和 S 表 FK 外键) 划分为与 NUMA 节点数量相匹配的分区, 并将对应表分片存储在相同的
NUMA 分区中, 实现 NUMA 内 R 表和 S 表分区的本地化连接和跨 NUMA 分区数据的并行连接. 分区采用连接
键 Radix 基数分区, 即通过连接键列数据末尾 n 位进行分区, 如 n=2 时将连接表划分为 2 个分区. 如图 3 所示, R
n
表和 S 表行组执行 n=2 的 Radix 分区, 相同行组中的记录划分为 4 个数据子集, 对应 4 个 NUMA 节点, R 表和 S
表具有相同 Radix 值的分区存储到相同 NUMA 节点中, 执行 NUMA 内的 R 表和 S 表分区连接操作. 当 NUMA
2
节点数量比分区数据大或小时, 如 2 分区在 2 或 4 个 NUMA 节点的平台上通过扩展或收缩 Radix 位数来扩展或
合并 NUMA 分区.
协同分区策略适用于带有大表连接的应用场景, 如 TPC-H 中的 ORDERS⋈LINEITEM 或 PARTSUPP⋈LINEITEM
连接负载.