Hash-Based Aggregation: Grouping Data Without Sorting

Why it exists

Grouping and aggregating large datasets, like in a SQL GROUP BY query, is a fundamental but expensive operation. The classic approach, sorting the data by the grouping key first, becomes a major bottleneck with large data volumes, consuming significant CPU and I/O. Hash-based aggregation was developed as a faster alternative that avoids the sorting step entirely, trading predictable sort performance for potentially faster, memory-based lookups.

The mental model

Think of it like sorting mail into cubbyholes. Instead of sorting a giant pile of letters alphabetically by city (the sort-based approach), you give each city a specific cubbyhole (a hash bucket). As each letter arrives, you instantly place it in the correct city's cubbyhole. At the end, you just count the letters in each cubbyhole. This is much faster than sorting the whole pile, provided you have enough cubbyholes (memory) and they don't overflow.

How it works

When a database executes a GROUP BY query using this strategy, it creates an in-memory hash table. For each row of data it processes, it computes a hash value from the grouping key's columns. This hash value points to a bucket in the table. If an entry for that group already exists, the aggregate function is applied (e.g., a counter is incremented). If not, a new entry for that group is created. This process repeats for every row, building the final aggregates directly in the hash table.

When to use it

Query optimizers favor hash aggregation when the number of distinct groups (the cardinality of the grouping key) is expected to be low. It excels when the entire hash table, holding one entry per group, can comfortably fit in available RAM. This makes it ideal for smaller datasets or queries that group by columns with few unique values, like 'country_code' or 'product_category'.

When not to use it

The primary limitation is memory. If the number of unique groups is very large, the hash table can exceed available RAM, forcing the system to spill parts of it to disk. This "spilling" causes a dramatic performance drop, often making it slower than a sort-based approach. It's also less suitable for data with high skew, where many different keys hash to the same bucket, creating long collision chains that degrade lookup speed. If subsequent query steps require sorted data, a sort-based aggregation is more efficient.

One canonical example

A query like SELECT product_id, SUM(sales) FROM transactions GROUP BY product_id on a table with millions of transactions but only a few thousand unique products. The database can create a hash table with a few thousand entries. For each transaction row, it hashes the product_id, finds the corresponding entry, and adds the sale amount to that product's running total. This avoids sorting millions of rows.