Joins are loops and hash tables

A join answers one question: for each row on the left, which rows on the right match? There are only a few ways to compute that, and you already know the parts. A loop from lesson 2. A hash map from lesson 3.

The nested loop

The most direct way is two loops, one inside the other:

for o in orders:                       # 1,000 rows
    for c in customers:                # 200 rows, every time
        if o.customer_id == c.customer_id:
            emit(o, c)

That is 1,000 × 200 = 200,000 comparisons to produce 1,000 output rows. It is correct, and it is how engines handle joins with conditions like a.x < b.y, where there is nothing to look up. But the cost is the product of the two sizes. Two tables of 1 million rows each means 1 trillion comparisons.

The hash join

The trick from the last lesson fixes this. Build a hash map from one side, then walk the other side once and look each row up:

customers = [(1, "US"), (2, "GB"), (3, "IN")]
orders = [(101, 1), (102, 3), (103, 1), (104, 9)]   # (order_id, customer_id)

# Build: one pass over the smaller side.
by_id = {}
for customer_id, country in customers:
  by_id[customer_id] = country

# Probe: one pass over the bigger side, one lookup per row.
lookups = 0
for order_id, customer_id in orders:
  lookups += 1
  if customer_id in by_id:
      print(order_id, by_id[customer_id])

print("lookups:", lookups, "vs nested loop:", len(orders) * len(customers))

Two phases:

1. Build. Put the smaller table in a hash map, keyed by the join column.
2. Probe. Stream the bigger table past it. Each row costs one lookup.

The cost is now the sum of the sizes, not the product. For bitshop that is 200 + 1,000 = 1,200 row touches instead of 200,000. This is the plan DuckDB, PostgreSQL and every analytics engine pick for an equality join (=) most of the time. In a DuckDB plan, look for HASH_JOIN.

Order 104 points at customer 9, who does not exist, so it never prints. That is an inner join: rows with no match on the other side disappear.

customers (200 rows) ──build──▶ [ hash table: customer_id → row ]
                                          ▲
orders (1,000 rows) ──probe, one lookup per row──┘ ──▶ joined rows

There is a third classic, the merge join: sort both sides by the key, then walk them together like a zipper. It shines when both inputs are already sorted, for example by an index. You will meet it in plans, but the hash join is the one to understand first.

Here is the join in SQL

Orders per customer country:

SELECT c.country, count(*) AS orders
FROM orders o
JOIN customers c ON c.customer_id = o.customer_id
GROUP BY c.country
ORDER BY orders DESC;

Read it from the inside out. A hash table is built on customers. Each of the 1,000 orders probes it. The joined rows flow straight into the GROUP BY hash map from the last lesson. Two hash tables, one pass over orders.

LEFT JOIN keeps the misses

An inner join drops rows with no match. Sometimes the misses are the answer. 24 of the 200 bitshop customers never placed an order. To find them, keep every customer and look for the ones where the right side came back empty:

SELECT c.customer_id, c.name, c.signup_date
FROM customers c
LEFT JOIN orders o ON o.customer_id = c.customer_id
WHERE o.order_id IS NULL
ORDER BY c.customer_id;

24 rows. In the probe loop, a LEFT JOIN emits the left row even when the lookup misses, and fills the right columns with NULL. The WHERE o.order_id IS NULL then keeps only those misses. This pattern is called an anti-join. WHERE NOT EXISTS (...) says the same thing, and engines usually run both the same way.

Fan-out: the join that is silently wrong

A join emits one row for every match. If a key appears 3 times on the right, each left row comes out 3 times. That is fine when you mean it, and a bug when you do not.

bitshop has a price_changes table: one row per list-price change, 98 rows across 40 products. Join it to line items by product and count:

SELECT (SELECT count(*) FROM order_items) AS line_items,
     count(*) AS rows_after_join
FROM order_items oi
JOIN price_changes pc ON pc.product_id = oi.product_id;

2,423 line items become 5,940 rows. No error, no warning. Sum quantity over that result and every product with 3 price changes counts its units 3 times. Your revenue report is now roughly 2.5x too high.

The habit that catches this: count rows before and after every join. If a join should be one-to-one or many-to-one, the count must not go up. If it does, the key you joined on is not unique on one side. For price history, the fix is to pick the one price in effect on the order date, which is a job for the next lesson.

Ship it

Build a customer report with one row per customer, including the ones who never ordered:

1. LEFT JOIN customers to orders.
2. Group by customer, and use count(o.order_id), not count(*), so customers with no orders show 0 instead of 1.
3. Before you trust it, check the row count. It must be exactly 200, the number of customers.

Then practise a three-table join on a real brief. Revenue by category joins line items to both orders and products. Count rows after each join and confirm they stay at the line-item count.