It's the memory latency, stupid

When you observe your database's CPU reaching 100%, it's not necessarily performing at maximum capacity. CPUs are intricate devices capable of executing various instructions simultaneously, or sometimes none at all. Consequently, a CPU displaying 100% utilization might be underperforming compared to another at the same level. A CPU is deemed idle solely when no task necessitates CPU time, which does not imply the CPU is fully occupied.

This brings us to the question: why wouldn't a CPU be fully utilized, even if it appears to be at 100%? Memory accesses are significantly slower than internal CPU operations. To comprehend the extent of this disparity, a modern CPU may execute between 4 and 8 instructions per nanosecond. Conversely, a memory access to RAM can take anywhere between 50 and 100 nanoseconds.

To put this into perspective, a modern CPU can execute approximately 400-800 instructions for each memory access from RAM. To circumvent this issue, CPUs are engineered with CPU caches. CPU caches hold memory closer to the CPU than RAM, thereby enhancing speed. The closest cache, the L1 cache, operates around 1ns per memory operation, which is 50-100 times faster than RAM!

However, CPU caches are relatively small; the L1 cache of a modern CPU is typically around 64KB, while the larger caches cap at a few hundred MB for top-tier processors. An efficient database employs tactics like manipulating data in small chunks to optimize cache usage, with cache utilization often being a primary concern for performance engineering.

To illustrate this concept, consider GROUP BY aggregations. The objective is to transform a dataset into groups based on a specified column, followed by executing certain aggregations such as counting or summing another column. One straightforward approach involves creating a HashTable using the group key as the key, with each key mapping to its corresponding aggregation.

As each new row is processed, the algorithm checks if the key exists in the HashTable. If present, the aggregation is updated; otherwise, a new entry is created. While this method is uncomplicated, it falls short when dealing with millions of unique groups, as nearly every HashTable access results in a cold hit, meaning the data is fetched from RAM.

This scenario leads to constant waiting for memory accesses, even if the CPU seems to be at 100% utilization. To demonstrate this phenomenon, a state-of-the-art Pivot engine is employed. The engine is configured with complex logic replaced by simplicity, and a query is executed on the ClickBench dataset containing 99 million rows.

The query calculates the count per UserID, resulting in a HashMap entry for each UserID. In this scenario, the group by operation is performed on a single core using a bare metal server from CherryServers (AMD EPYC 9124 Genoa, 16 cores, 128 GB DDR5). The query takes 3.9 seconds to complete. When rerun without restarting the server, the query takes 3.6 seconds.

During both runs, the CPU stalls 50.1% of the time due to memory, and only 16.1% of the time does it execute operations. Moreover, a substantial amount of data, totaling 4.5GB, is pulled from DRAM during the query, emphasizing the importance of cache utilization for optimal performance. To enhance cache usage, radix partitioning is utilized.

The process is divided into two phases: Phase 1 involves dividing the data into 4096 partitions using a hash function that considers the top 12 bits of the key. Phase 2 entails aggregating data within each partition using a HashMap. By distributing the workload into smaller partitions, the resulting HashMaps are more likely to fit within the CPU caches, thereby improving performance.