It's the Memory Latency, Stupid: Pivot's Radix-Partitioned GROUP BY
A CPU reported at 100% utilization may be spending most of its cycles waiting for memory, not executing useful instructions. Pivot's blog post 'It's the memory latency, stupid' demonstrates this with a single-core GROUP BY query on the 99-million-row ClickBench hits dataset: the naive hash-table version spent 50.1% of CPU slots stalled on memory and only 16.1% retiring operations, while a radix-partitioned version reduced memory stalls to 23.5%, cut DRAM traffic from 4.5 GB to 1.5 GB, and lowered runtime from 3.6 s to 2.7 s.
Why a 100% CPU can be mostly idle
Linux marks a CPU busy when a task needs CPU time; it does not mean the core is issuing instructions every cycle. A core can show 100% utilization while most of its execution slots are blocked on memory access.
The scale gap between CPU and memory is the reason. Pivot's post estimates that a modern CPU can process roughly 4-8 instructions per nanosecond, while a DRAM access takes roughly 50-100 ns. That means a CPU can execute around 400-800 instructions in the time one DRAM access takes.
| Level | Approximate latency | Approximate size | Instructions per access |
|---|---|---|---|
| L1 cache | ~1 ns | ~64 KB | ~4-8 |
| L2 cache | ~3-4 ns | ~1 MB | ~15-30 |
| L3 cache | ~10-15 ns | up to a few hundred MB | ~50-100 |
| DRAM | ~50-100 ns | GBs | ~400-800 |
CPU caches exist to hide this gap, but they are small relative to real datasets. A database that wants predictable performance must keep working sets close to the core, not rely on the CPU to absorb repeated cold DRAM accesses.
The naive GROUP BY: one hash table, millions of cold misses
Pivot stripped its engine down to a simple hash-table aggregation to show the cost of poor cache locality. The query was SELECT count(*), UserID FROM hits GROUP BY UserID on ClickBench's hits dataset, which has 99 million rows and about 17 million unique UserID values.
The naive implementation inserts or updates one entry per key in a single growing hash table:
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;
}
}
With millions of unique groups, nearly every hash-table access is a cold miss that goes to DRAM. The CPU may look busy, but it is mostly waiting.
The measurements ran on a CherryServers bare-metal server with an AMD EPYC 9124 Genoa, 16 cores, and 128 GB DDR5. The process was pinned to a single core because the naive GROUP BY could not run on many cores. The first run took 3.9 seconds; the second run, with data already in page cache and no disk involvement, took 3.6 seconds.
perf stat showed the problem directly:
- 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
A separate counter, ls_dmnd_fills_from_sys.dram_io_near, recorded 76,190,837 DRAM fills. At 64 bytes per cache line, that is about 4.5 GB pulled from DRAM during the query, without prefetching.
Radix partitioning: more instructions, fewer DRAM trips
Radix partitioning splits the aggregation into two phases to make the working hash tables small enough to stay in CPU cache.
In phase one, Pivot hashes each key and uses the top 12 bits of the hash to route the row into one of 4,096 partitions. The partitions are SlabVecs, a vector-like structure over memory that is already paged in. In phase two, Pivot processes one partition at a time, builds a small hash table for that partition, aggregates it, and emits the results.
This approach does more total work: every row is hashed and routed, then hashed again during aggregation. The trade is deliberate. Smaller hash tables are more likely to fit in L1, L2, or L3 cache, so lookups hit cache instead of DRAM. Pivot's post argues that converting cold DRAM accesses into CPU instructions is usually a good trade.
The results on the same single core:
- First radix-partitioned run: 3.3 seconds
- Second radix-partitioned run: 2.7 seconds
backend_bound_memory: 23.5%retiring: 32.2%ex_ret_ops: 19,350,459,182, up from 11,431,618,219 in the naive version- DRAM fills: 25,688,280, or about 1.5 GB at 64 bytes per fill
The radix version executed more operations but spent far less time stalled on memory. Memory stalls fell from 8,364,109,137 CPU slots to 3,790,955,223, and DRAM traffic fell from about 4.5 GB to about 1.5 GB.
Pivot's tuned implementation and parallel result
Pivot's own implementation goes further than the demonstration version. On a single core, the post reports 1,848.353 ms for the same query and 14,917,958 DRAM fills, which comes out to about 954 MB of DRAM traffic.
On 16 cores, Pivot reports 171.773 ms for the query. The post says cache utilization is not the only way to hide DRAM latency; prefetching and algorithms that maximize memory throughput will be covered in a follow-up about JOIN probing.
What Hacker News commenters debated
The Hacker News submission received 254 points and 92 comments. The discussion split between appreciation for the cache-locality demonstration and skepticism about whether the technique or the product is novel.
One commenter described the broader cost of ignoring mechanical sympathy in production systems:
I work with another team at work that uses lots of message passing, C++ virtual methods in deeply nested class hierarchies, large DOMs and off-the-shelf C++ STL containers... on a STM32MP1, which has an in-order Cortex-A7 and a pittance of cache. On the other hand, in my team I wrote my custom C++ STL containers that allocate inline, SAX-style processing libraries and an object pool with links that use index+generations like 2000s video games... on a STM32H5 with less than a megabyte of RAM. Mechanical sympathy feels like a lost art to people I demonstrate it to... and I had to demonstrate to the first team with benchmark numbers that I would not be the bottleneck between us by orders of magnitudes.
Another commenter gave a direct example of the CPU-utilization trap:
I remember have a very long argument with a team I worked on, who were mostly convinced our service couldn't handle requests any faster because the CPUs were already at 100%. In the end we tripled the requests-per-second by cleaning up the service's memory access patterns...
Other commenters questioned the novelty. One wrote:
Uh, isn't this just radix-partitioned aggregation? Hierarchical (fixed two level) aggregation is old. What's novel here? Microcosm of Pivot itself I guess. I just don't get why this project exists when DuckDB and Clickhouse both exist.
Another described the approach as a clustered hash map:
I feel like the solution presented is just a clustered hashmap or 'locality sensitive' if you'd like it. Still not orders of magnitude better.
The post does not claim to invent radix partitioning. Its contribution is a measured demonstration of how much a database query can lose to memory stalls, plus a look at how Pivot applies cache-aware aggregation in its own engine. The comment thread reflects a broader disagreement about whether that demonstration is enough to justify a new database project.
A final comment framed the trade-off between clean code and fast code:
Clean code is beautiful, like a convenient lie enjoys us. Cache aware code is ugly, like a truth that hurts. Morality suggests to be honest from the beginning, there is no prematurity in aiming for cache locality.
The practical takeaway is narrower than the product debate: a CPU at 100% is not proof that the CPU is saturated. For data-intensive workloads, memory stalls and DRAM traffic are often the better explanation, and partitioning data to fit CPU caches can reduce runtime even when it increases the instruction count.
Sources
Related
- Dispatch
- Dispatch
- Dispatch
- Dispatch
- Dispatch