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

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

接处理. 面向 NUMA 架构的存储策略需要数据库在存储引擎设计中支持 NUMA-aware 分区策略, 通过静态数据
分布存储策略消除跨 NUMA 数据访问延迟, 通过原生设计的 NUMA-aware 存储引擎支持 NUMA-conscious 的查
询处理引擎.
如第 2.1 节所述, 协同分区存储模型使用 PK-FK 上的 Radix 位进行 NUMA 分区, 创建不相交的 R 表和 S 表
分区, 支持 NUMA 本地连接操作. 当存储引擎不支持 NUMA-aware 分区存储时, 需要将 NUMA 分区作为数据预
处理, 付出额外的时间与存储空间代价. 该策略也适用于 PRO 算法, 通过 1+n 趟 Radix 分区首先使用 log 2 |NUMA
node|位将 R 表和 S 表划分到不同的 NUMA 分区中, 然后在本地 NUMA 节点中执行 n 趟 Radix 分区, 实现 NUMA
节点内的分区和哈希连接操作.
典型的 OLAP 数据库采用单一事实表 (如 SSB), 通过事实表物化策略消除大表连接. 或者采用多事实表 (如
TPC-DS) 中冗余事实表外键来独立访问共享维表, 减少大事实表之间的连接操作. OLAP 数据库模式上的优化策
略简化了 NUMA 集群上的并行连接算法设计. TPC-H 模式采用 3NF 结构, 有 3 个大事实表 LINEITEM, ORDERS
和 PARTSUPP, 面向 NUMA 集群进行协同分区时, 三表关联产生较大的数据冗余, 将 3 个事实表物化为 SSB 模式
中的单一事实表 LINEORDER 可以优化 NUMA 集群连接算法, 但增加了冗余存储代价和计算代价 (如 LO_
ORDTOTALPRICE 冗余存储, 需要去重计算). 一种更加灵活的策略是只将 PARTSUPP 表中用于度量计算的
SUPPLYCOST 列物化到 LINEITEM 表中, 消除 LINEITEM 表与 PARTSUPP 表之间利润计算时的连接需求.
PARTSUPP 表可以与共享 PART 表和 SUPPLIER 表构成独立的星形模型进行 NUMA 分区, LINEITEM 表和
ORDERS 表采用协同 NUMA 分区, 使不同的连接负载具有较好的 NUMA 局部性.
综上所述, 从软件维度来看, 数据库的查询优化是一个系统性的问题, 计算层的设计与存储层密切关联, 模式
层上的优化工作可以简化查询层的复杂度和效率. 从硬件维度来看, 传统的分布式系统以节点为粒度, 随着内存容
量和处理器核心数量的持续增长, NUMA 节点数量也呈增长趋势, 如 AMD EPYC 9004 可以配置为 1 个或 4 个
NUMA 节点, 为 NUMA 访问延迟敏感算法提供了不同的硬件解决方案. NUMA 架构的多样性需要数据库在存储
引擎和查询处理引擎上有灵活的软件架构相匹配, 传统集中式计算架构依赖动态分区策略, 从而带来较大的计算
和存储空间开销. 将分布式系统节点间 SN 并行计算架构下沉到节点内, 实现 NUMA 集群并行计算架构, 从而能
够更好地适应多 NUMA 节点处理器平台上的高效查询处理. 基于 NUMA 集群连接实现技术的私有哈希表或私有
向量连接算法如算法 5 所示.

算法 5. 基于 NUMA 集群连接实现技术的私有哈希表或私有向量连接算法.
数据预处理: 对 R 表和 S 表使用 PK-FK 上的 Radix 位进行 NUMA 分区, 分割成 N 份数据副本 R 0…N−1 , S 0…N−1 (N
对应于 NUMA 节点数), 并分别存储在对应 NUMA 节点的内存中;
Input: R 0…N− 表, S 0…N− 表, 私有哈希表 (pht k ) 或私有向量 (pv k ), k ∈ [0, N), N 是 NUMA 节点数;
1
1
Output: sum: 连接成功计数.
1. build 阶段
2. for thread k in all threads do
3. numaid ← get_numa_id(thread k )
4. start ←startoffset k in R numai 表
d
5. i ← 1, location ← i + start
6. repeat
7. key ← R numaid .tuple[location].key
8. index ← (Hash(key) OR key)
9. pht numaid [index] ← R numaid .tuple[location] OR pv numaid [index] ← R numaid .tuple[location].payload
10. i ← i + 1, location ← i + start