关键在于内存延迟：Pivot 的基数分区 GROUP BY
一个 CPU 报告为 100% 利用率时，可能大部分周期都在等待内存，而不是执行有效指令。Pivot 的博客文章《关键在于内存延迟》通过 ClickBench hits 数据集上 9900 万行的单核 GROUP BY 查询证明了这一点：朴素哈希表版本有 50.1% 的 CPU 槽位因内存而停滞，只有 16.1% 在退休操作；而基数分区版本将内存停滞降至 23.5%，DRAM 流量从 4.5 GB 降至 1.5 GB，运行时间从 3.6 秒降至 2.7 秒。
为什么 100% 的 CPU 可能大部分时间处于空闲
Linux 在任务需要 CPU 时间时将 CPU 标记为忙碌；这并不意味着每个周期核心都在发出指令。一个核心可能显示 100% 利用率，而大部分执行槽位被内存访问阻塞。
CPU 与内存之间的规模差距是原因所在。Pivot 的文章估计，现代 CPU 每纳秒大约能处理 4-8 条指令，而一次 DRAM 访问大约需要 50-100 纳秒。这意味着在 DRAM 访问一次的时间内，CPU 可以执行大约 400-800 条指令。
| 层级 | 近似延迟 | 近似大小 | 每次访问的指令数 |
|---|---|---|---|
| L1 缓存 | ~1 纳秒 | ~64 KB | ~4-8 |
| L2 缓存 | ~3-4 纳秒 | ~1 MB | ~15-30 |
| L3 缓存 | ~10-15 纳秒 | 最多几百 MB | ~50-100 |
| DRAM | ~50-100 纳秒 | GB 级 | ~400-800 |
CPU 缓存的存在是为了隐藏这种差距，但它们相对于真实数据集来说很小。一个希望获得可预测性能的数据库必须让工作集靠近核心，而不是依赖 CPU 来吸收重复的冷 DRAM 访问。
朴素的 GROUP BY：一个哈希表，数百万次冷未命中
Pivot 将其引擎简化为一个简单的哈希表聚合，以展示缓存局部性差的代价。查询是 SELECT count(*), UserID FROM hits GROUP BY UserID，针对 ClickBench 的 hits 数据集，该数据集有 9900 万行和约 1700 万个唯一的 UserID 值。
朴素实现在一个不断增长的哈希表中为每个键插入或更新一个条目：
fn consume(
&mut self,
batch: RecordBatch,
_sender: &mut dyn Sender<RecordBatch>,
) -> unary::Result<()> {
let group_keys = batch.column(self.key_column).as_primitive::<Int64Type>();
for &key in group_keys.values() {
*self.counts.entry(key).or_insert(0) += 1;
}
}
由于有数百万个唯一分组，几乎每次哈希表访问都是冷未命中，需要访问 DRAM。CPU 可能看起来很忙，但大部分时间都在等待。
测量在 CherryServers 裸机服务器上进行，配备 AMD EPYC 9124 Genoa、16 核和 128 GB DDR5。进程被固定到单个核心，因为朴素的 GROUP BY 无法在多核上运行。第一次运行耗时 3.9 秒；第二次运行，数据已在页缓存中且无磁盘参与，耗时 3.6 秒。
perf stat 直接显示了问题：
- 50.1%
backend_bound_memory - 16.1%
retiring - 8,364,109,137
ex_no_retire.load_not_complete - 11,431,618,219
ex_ret_ops
另一个计数器 ls_dmnd_fills_from_sys.dram_io_near 记录了 76,190,837 次 DRAM 填充。按每个缓存行 64 字节计算，查询期间从 DRAM 拉取了约 4.5 GB 数据，且没有预取。
基数分区：更多指令，更少的 DRAM 访问
基数分区将聚合分为两个阶段，使工作哈希表足够小以保持在 CPU 缓存中。
在第一阶段，Pivot 对每个键进行哈希，并使用哈希的高 12 位将行路由到 4,096 个分区之一。分区是 SlabVecs，一种基于已分页内存的向量结构。在第二阶段，Pivot 一次处理一个分区，为该分区构建一个小型哈希表，进行聚合，并发出结果。
这种方法做了更多总工作：每一行都被哈希和路由，然后在聚合时再次哈希。这种权衡是有意的。较小的哈希表更可能适合 L1、L2 或 L3 缓存，因此查找会命中缓存而不是 DRAM。Pivot 的文章认为，将冷 DRAM 访问转换为 CPU 指令通常是一个好的权衡。
在同一个单核上的结果：
- 第一次基数分区运行：3.3 秒
- 第二次基数分区运行：2.7 秒
backend_bound_memory：23.5%retiring：32.2%ex_ret_ops：19,350,459,182，高于朴素版本的 11,431,618,219- DRAM 填充：25,688,280，按每次填充 64 字节计算约 1.5 GB
基数版本执行了更多操作，但花费在内存停滞上的时间大大减少。内存停滞从 8,364,109,137 个 CPU 槽位降至 3,790,955,223，DRAM 流量从约 4.5 GB 降至约 1.5 GB。
Pivot 的调优实现和并行结果
Pivot 自己的实现比演示版本更进一步。在单核上，文章报告同一查询耗时 1,848.353 毫秒，DRAM 填充为 14,917,958 次，相当于约 954 MB 的 DRAM 流量。
在 16 核上，Pivot 报告查询耗时 171.773 毫秒。文章表示，缓存利用率并不是隐藏 DRAM 延迟的唯一方法；预取和最大化内存吞吐量的算法将在后续关于 JOIN 探测的文章中介绍。
Hacker News 评论者的争论
Hacker News 上的提交获得了 254 分和 92 条评论。讨论分为两派：一派赞赏缓存局部性的演示，另一派则怀疑该技术或产品是否新颖。
一位评论者描述了在生产系统中忽视机械同理心的更广泛代价：
我和另一个团队合作，他们大量使用消息传递、深层类层次结构中的 C++ 虚方法、大型 DOM 和现成的 C++ STL 容器……在 STM32MP1 上，它有一个顺序执行的 Cortex-A7 和极少的缓存。另一方面，在我的团队中，我编写了自定义的 C++ STL 容器，内联分配，SAX 风格的处理库，以及一个使用索引+代际链接的对象池，就像 2000 年代的游戏……在 STM32H5 上，内存不到 1 MB。机械同理心对我来说像是一门失传的艺术，我向人们演示时……我不得不向第一个团队用基准数字证明，我不会成为我们之间的瓶颈，而且差距是数量级的。
另一位评论者给出了 CPU 利用率陷阱的直接例子：
我记得和我工作的一个团队进行过一场很长的争论，他们大多确信我们的服务无法更快地处理请求，因为 CPU 已经 100% 了。最后，我们通过清理服务的内存访问模式，将每秒请求数提高了三倍……
其他评论者质疑其新颖性。一位写道：
呃，这不就是基数分区聚合吗？分层（固定两级）聚合已经很老了。这里有什么新颖的？我想这就是 Pivot 本身的缩影。我只是不明白为什么在 DuckDB 和 Clickhouse 都存在的情况下，这个项目还要存在。
另一位将这种方法描述为聚簇哈希映射：
我觉得提出的解决方案只是一个聚簇哈希映射，或者如果你愿意，可以说是“局部性敏感”的。仍然没有数量级的提升。
文章并没有声称发明了基数分区。它的贡献在于通过测量展示了数据库查询可能因内存停滞而损失多少，以及 Pivot 如何在其引擎中应用缓存感知聚合。评论线程反映了关于这种演示是否足以证明新数据库项目合理性的更广泛分歧。
最后一条评论框架化了干净代码与快速代码之间的权衡：
干净的代码是美丽的，就像一个方便的谎言让我们愉悦。缓存感知的代码是丑陋的，就像一个痛苦的真相。道德建议从一开始就诚实，追求缓存局部性并不算早熟。
实际要点比产品争论更窄：CPU 达到 100% 并不能证明 CPU 已饱和。对于数据密集型工作负载，内存停滞和 DRAM 流量通常是更好的解释，而将数据分区以适应 CPU 缓存可以减少运行时间，即使它增加了指令数。
SUMMARY: Pivot 的博客文章表明，报告为 100% 利用率的 CPU 可能大部分时间在 DRAM 上停滞，并演示了基数分区 GROUP BY 聚合如何将 ClickBench 查询的 DRAM 流量从 4.5 GB 降至 1.5 GB，单核运行时间从 3.6 秒降至 2.7 秒。
TITLE: 关键在于内存延迟：Pivot 的基数分区 GROUP BY
Sources
相关
- Dispatch
- Dispatch
- Dispatch
- Dispatch
- Dispatch