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

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

PAYLOAD 值组成) 和一个整数型值 (记录该哈希桶中元组的数量)) 设计简化为向量结构 (通常是一个整数型数
组, 存储对应 R 表元组中的 PAYLOAD 值). 代理键是数据仓库和 OLAP 中普遍使用的技术, 如 TPC-H、SSB 和
TPC-DS 大部分表均使用了代理键作为主键. 向量连接算法可以看作是一种简化的 NPO 算法, 向量相对于哈希表更小
(如在 SSB 及 TPC-H 中, 向量可以压缩到 1 字节宽度), 具有更高的 cache 局部性. 向量连接算法性能优于传统的哈
希连接算法 [4,5] (也称为 array-join), 在内存效率方面优于 NPO 算法的哈希表, 也优于 PRO 算法额外的分区代价,
是一种内存利用率较高的 hardware-oblivious 连接算法. 因此向量连接算法也可以作为面向 OLAP 模式和负载的
定制化连接优化技术.

One hash table S
Shared per partition Shared
hash table R vector
S S
b 1 R r 1 h 2 h 2 s 1
R h … h 1,2
h b 2 h 1,2 r 2 … … s 2
… … … scan h 1,1 r 3 … … … s 3 h 1,1 scan …
h h 1,2 h 1,2
h
…
r 4 h 2 h 2 s 4
b k
pass 1 pass 2 pass 2 pass 1
① build ② probe
① partition ② build ③ probe ① partition
① build ② probe
(a) NPO 连接算法 [1] (b) PRO 连接算法 [1] (c) Vector Join 向量连接算法
图 2 NPO 连接算法、PRO 连接算法和向量连接算法示例

NUMA 节点通过 QPI 连接, QPI 带宽低于本地 NUMA 带宽, 跨 NUMA 数据访问延迟是 NUMA 优化的主要
目标. 传统内存连接算法采用集中式设计, 在算法执行中优化 NUMA 本地访问, 当跨 NUMA 访问延迟足够高时,
需要针对 NUMA 节点的 SN (shared-nothing 无共享) 微集群做表存储的分布存储优化, 静态或动态地将连接表在
NUMA 节点上协同分片, 提高连接操作的 NUMA 局部性. 这种轻量 NUMA SN 集群并行连接优化策略是一种存
储与计算一体化的优化设计, 需要在存储引擎和查询处理引擎进行协同优化.
1.2 CPU 架构及性能
CPU 架构和 NUMA 架构的差异化对连接优化设计有较大影响. 表 1 列出了 5 种代表性的 CPU 架构, 包括
Intel CLX、Intel ICX、AMD Zen2 和 AMD Zen3. CLX(28) 为 6 通道内存, 内存带宽低于其他 4 个 CPU 型号.
AMD Rome 和 Milan CPU 采用小芯片 (chiplet) 架构, 每个小芯片中集成了 8 个核心, 其中, Rome Zen2 小芯片中
每 4 个核心共享 16 MB L3 cache, Milan Zen3 小芯片中每 8 个核心共享 32 MB L3 cache, L3 cache 总容量均为 256
MB, 平均每核心 4 MB L3 cache slice. 与 AMD 架构不同, Intel x86 的两个型号 CLX(28) 和 ICX(38) 均采用 MESH
架构 L3 cache, 全部核心共享访问统一的 L3 cache 容量, 尽管 L3 cache 总容量低于 AMD CPU, 但核心有效 L3
cache 容量较 AMD 小芯片结构上的有效 L3 cache 容量更大. L3 cache 容量和缓存效率对 hardware-oblivious 的
NPO 算法和向量连接算法性能有较大的影响, 也间接影响了 NUMA 优化的效果.

表 1 代表性 CPU 架构及性能

主频
CPU型号 类别 核心 缓存 内存
(GHz)
64 KB L1, 512 KB L2, 64 MB L3,
华为鲲鹏920 7200 2代ARM v8 2.6 64 8通道, 带宽190.7 GB/s
2×32 MB 1 MB/核
Intel Xeon Gold 6258R 2代Cascade Lake (CLX) 2.7 28 32 KB L1, 1 MB L2, 38.5 MB L3 6通道, 带宽131.13 GB/s
32 KB L1, 512 KB L2, 256 MB L3,
AMD EPYC7742 2代Rome Zen2 2.24 64 8通道, 带宽190.7 GB/s
8×32 MB 16 MB/4核
Intel Xeon Platinum 8368 3代Ice Lake (ICX) 2.4 38 48 KB L1, 1.25 MB L2, 57 MB L3 8通道, 带宽200 GB/s
32 KB L1, 512 KB L2, 256 MB L3,
AMD EPYC 7763 3代Milan Zen3 2.45 64 8通道, 带宽204.8 GB/s
8×32 MB 32 MB/8核