It's Memory Latency That's Killing Your GROUP BY Queries

Modern CPUs can execute hundreds of instructions while waiting for a single RAM access, yet most CPU performance problems actually stem from memory latency rather than raw processing power. When databases implement GROUP BY aggregations with a single HashMap that grows to accommodate millions of unique keys, each lookup has a high probability of missing the CPU cache and stalling the processor while waiting for data from main memory—creating a situation where the CPU appears 100% utilized despite doing very little actual work.

A detailed benchmark of a GROUP BY query on 99 million rows with 17 million distinct groups revealed the severity of this bottleneck. The CPU spent 50% of its cycles stalled waiting for memory operations while only retiring useful instructions 16% of the time. The query transferred 4.5GB from DRAM during execution despite being computationally simple, demonstrating how cache misses can completely dominate performance.

The solution is radix partitioning: divide the input data into thousands of smaller partitions in a first pass using a hash function, then process each partition independently with its own HashMap in a second pass. Because each partition is sized to fit within CPU cache, the memory access pattern becomes highly localized, dramatically reducing DRAM traffic. This technique trades additional CPU work for dramatically improved cache efficiency—a worthwhile exchange when memory latency is the actual constraint.