GROUP BY is a hash map

The last lesson ended with a scan: a loop that reads every row once. GROUP BY adds one thing to that loop. A dictionary.

That is the whole lesson. The rest is detail.

Build it by hand first

Say you want the number of units sold per category. Without SQL, you would walk the line items and keep a running total per category in a dict:

items = [
  ("Books", 2), ("Stickers", 5), ("Books", 1),
  ("Hardware", 1), ("Stickers", 3), ("Books", 4),
]

totals = {}                      # the hash map: key -> running sum
for category, qty in items:      # one pass over the rows
  totals[category] = totals.get(category, 0) + qty

for category, units in totals.items():
  print(category, units)

Look at what this costs:

• Time: one pass. Each row does one hash lookup and one addition. Six rows, six lookups. Six million rows, six million lookups.
• Memory: one entry per group, not per row. Three categories means three entries, however many rows go past.

That second point is why GROUP BY is cheap when there are few groups and expensive when there are many. Grouping 2 million rows into 5 categories needs a 5-entry table. Grouping 2 million rows by order_id needs a table with up to 2 million entries.

Now the SQL

Here is the same question against the real bitshop data:

SELECT p.category,
     count(*)         AS line_items,
     sum(oi.quantity) AS units
FROM order_items oi
JOIN products p ON p.product_id = oi.product_id
GROUP BY p.category
ORDER BY units DESC;

Five rows, built from 2,423 line items. Read it as the Python loop:

• GROUP BY p.category is the dict key.
• sum(oi.quantity) is the running value, totals.get(k, 0) + qty.
• count(*) is a second running value in the same entry: add 1 per row.

Every aggregate you know works this way. Each one is a small state plus a rule for updating it:

The last row is the expensive one. count(DISTINCT x) keeps every distinct value it has seen, per group. That is a hash map whose values are hash sets. If you only need a rough number, most engines have an approximate version, such as approx_count_distinct in DuckDB, that uses a few kilobytes no matter how many values there are.

Where WHERE and HAVING fit

There are two filters, and they run at different times.

• WHERE runs before the dict. It decides which rows get added at all.
• HAVING runs after the dict is full. It decides which groups to keep.

In Python terms, WHERE is an if inside the loop. HAVING is a filter over totals.items() once the loop is done.

So a question like “which customers placed 10 or more orders?” needs HAVING, because you cannot know a customer’s count until every row has been seen:

SELECT customer_id, count(*) AS orders
FROM orders
GROUP BY customer_id
HAVING count(*) >= 10
ORDER BY orders DESC, customer_id;

13 customers out of 176 who ever ordered. Now change the question: “count only delivered orders”. That is a row filter, so it goes in WHERE. Put a row filter in HAVING and most engines will reject it, because the row columns no longer exist once the rows have been folded into groups.

What can go in SELECT

After grouping, each output row is one dict entry. So SELECT can only use:

1. The group keys, because they are the dict key.
2. Aggregates, because they are the dict value.

That is the rule behind the classic error “column must appear in the GROUP BY clause or be used in an aggregate function”. If you group by category and select product_id, which of the 8 product ids in that category should the engine print? There is no single answer, so it refuses.

When the dict does not fit

A hash map lives in memory. When there are too many groups for RAM, engines split the work. DuckDB partitions the groups by hash into chunks, spills the chunks to disk, and finishes them one at a time. You will not see it in the SQL, but you will see it in the run time: a group-by that spills can be 10x slower than one that fits.

The fix is usually to reduce the number of groups before grouping. Filter first with WHERE, or group by a coarser key, like month instead of timestamp.

Ship it

Finance wants delivered revenue per category. That is the problem below. You now have every piece:

1. Join line items to orders (for status) and to products (for category).
2. Filter to delivered orders in WHERE, before the dict.
3. Group by category and sum(quantity * unit_price).

Use unit_price from order_items, not the list price from products: the line item is what the customer actually paid. The hidden tests add a new category and change some data, so a hard-coded answer will fail.