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

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

13. for i ← 1 to N do
14. for j ← 1 to N do
15. if j = i then
16. continue
17. end if

18. pht j_i ← pht i_i OR pv j_i ← pv i_i
19. end for
20. end for
21. probe 阶段
22. for thread k in all threads do
23. start ← startoffset k in S 表
24. i ← 1, location ← i + start
25. sum ← 0
26. repeat
27. key ← S.tuple[location].key
28. index ← (Hash(key) OR key)
29. numaid ← get_numa_id(thread k )
30. for j ← 1 to N do
31. if pht numaid_j [index] , NULL OR pv numaid_j [index] , NULL then
32. sum ← sum + (pht numaid_j [index].payload OR pv numaid_j [index])
33. Break
34. end if
35. end for
36. until i > S_slice_length k
37. end for
38. return sum

2.2.3 分区复制策略 (partitioned replication)
如图 4(c) 所示, 该策略为向量连接的优化算法. 首先将 R 表记录按 PK 主键排序后分区, 每个分区主键值递增
且不相交, 在各 NUMA 上独立创建连接向量, 再复制到其他 NUMA 节点. 在探测阶段每个 S 表分区上的记录的

FK 键值映射到单一向量入口进行探测. 该策略增加了创建向量阶段 R 表的排序代价. 基于分区复制策略的 NUMA
节点内私有哈希表或私有向量连接算法如算法 4 所示.

算法 4. 基于分区复制策略的 NUMA 节点内私有哈希表或私有向量连接算法.

数据处理: 将 R 表中各元组按 key 值升序排列并生成新数据副本 R n ;
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