The Truth About JOIN: Cartesian Product First, Then Filter

The previous post made clear that “the order you write isn’t the order it runs”. This post uses the same key to open up JOIN. Many people picture JOIN as “gluing two tables together” and then rote-learn what INNER/LEFT/RIGHT/FULL each do. But they all share one model: list every combination of rows from both tables (the Cartesian product), then filter with ON. Understand that sentence and even the most common LEFT JOIN trap is seen through at once.

Every JOIN is one model

Conceptually, A JOIN B ON condition does two things: ① pair every row of A with every row of B (the Cartesian product); ② keep only the combinations where the “condition” holds. The only difference is “after filtering, do we pad a row for the ones that matched nothing”:

Pair every left row with every right row (9 cells), then keep the ones where the keys are equal with ON (green). INNER = green cells only (3 rows); LEFT = green cells + one padded NULL row for the unmatched C (4 rows). Note in passing: A matches two rows, so A appears twice in the result — that's the join's "amplification" side effect

With this model the four JOINs need no memorising; they differ only in “which side is kept after filtering”:

INNER: only the green cells (matched on both sides).
LEFT: guarantees every left row appears at least once; pad NULL where the right side matched nothing.
RIGHT: the reverse — every right row is guaranteed.
FULL: both sides guaranteed; whoever didn’t match gets NULL padding.
CROSS: no filtering at all — the complete Cartesian product (all 9 cells).

And one side effect you must remember: one-to-many multiplies the row count (fan-out). In the diagram A matches 2 orders, so A appears as 2 rows. When you SUM after a join, this double counts — the classic culprit behind report totals that mysteriously grow.

Doesn’t the Cartesian product blow up memory?

This is the scariest part of “Cartesian product then filter”: two tables of a million rows each multiply to 10^12 rows — if that were actually computed, what machine could take it? The good news: the product is a “logical model”, there to help you reason about the answer; the engine never actually materialises it. The optimizer picks a join algorithm that discards non-matches as it pairs, so the product never lands anywhere:

That N×M table on the left exists only in your head, to help you derive the answer; the engine actually picks an algorithm (Hash Join here) and discards as it pairs, so the product never lands. A single join therefore doesn't use N×M memory

So does a join use memory or not? It does, but the cost isn’t in “the product” — it’s in these two places.

One: the join algorithm itself. The optimizer picks an approach based on table sizes, indexes and existing sort order, and their memory appetites differ a lot:

Nested Loop: for each outer row, search the inner table one by one. Almost no extra memory, but slow without an index — suited to small tables, or when the inner table happens to have an index to look up.
Hash Join: build the smaller side into a hash table in memory, stream the big table past it to probe. Memory ∝ the small table’s size — the most common place a join eats memory.
Merge Join: requires both sides already sorted; if not, they have to be sorted first, and the sort buffer costs memory too.

(How to recognise these three in EXPLAIN, and what the optimizer bases its choice on, gets its own post later in this series. For now grab one sentence: a join’s memory comes mainly from hash tables and sorts, not from the product.)

Two: fan-out inflates the result. The join itself doesn’t materialise the product, but one-to-many inflating the output row count is very real: A matches 100 rows, the result has 100 rows. That inflated result genuinely exists, and when you then ORDER BY or GROUP BY it, sorting and aggregation have more data to handle. So a join’s memory pain is often not in the join step itself, but in the step downstream that receives the inflated output.

In PostgreSQL, how much memory hash tables and sorts may use is governed by the work_mem parameter. Exceed the cap and it spills to disk (writing temp files) — the result is slowdown, not an outright OOM; that’s its safety valve. The thing to watch is the other end: set work_mem too high, with many nodes running in parallel, and the sum can genuinely exhaust the whole machine’s memory.

You’ve actually seen the extreme version of this in the Spark post: a broadcast join copies the small table to every executor, which is essentially “the build side of a Hash Join” moved to a distributed setting — if the small table is too big, every node’s memory blows together. A single machine’s work_mem spill and a distributed broadcast limit are the same principle at two scales.

The LEFT JOIN trap nearly everyone has fallen into

You want to “list all users, along with their paid orders, keeping users with no orders too”. The natural way to write it:

SELECT u.id, o.amount
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
WHERE o.status = 'paid';   -- ❌ users with no orders get cut right here

Run it and you’ll find all the users with no orders have vanished, as if the LEFT JOIN did nothing. The reason is exactly the processing-order diagram from the previous post — WHERE runs after JOIN:

LEFT JOIN first pads NULL for C, who has no orders. With the condition in WHERE it runs after the join, NULL = 'paid' doesn't hold, C is cut → it quietly becomes INNER. Put it in ON, the filter happens during the join, and C stays

The fix is to move “the condition on the right table” into ON, so it takes part in filtering during the join rather than being cut by WHERE afterwards:

SELECT u.id, o.amount
FROM users u
LEFT JOIN orders o
  ON o.user_id = u.id AND o.status = 'paid';  -- ✅ every user stays

One rule of thumb to remember: filters on the side you “want to keep in full” (the left table of a LEFT) are fine in WHERE; filters on the “optional” side (the right table) go in ON, or you knock the LEFT back to INNER.

Reflections

JOIN isn’t “gluing tables”, it’s “combine, then filter”

When I first learned SQL, INNER/LEFT/RIGHT/FULL were four separate rules to memorise, and I regularly mixed up which side LEFT kept. What finally stopped me memorising was switching to the single model “Cartesian product, then filter” — the four JOINs are just four choices of “which side to keep after filtering”. It’s the same kind of gain as the previous post: reduce a pile of rote rules to one mechanism you can derive from. Once the model is right, you don’t merely “remember” how LEFT works, you can “compute” what any join will emit — including the weird edge cases.

LEFT JOIN degrading to INNER is the bug I catch most often in code review

What makes this trap insidious: it runs, it doesn’t error, the numbers even “look right” — it’s just quietly missing a batch of data. When I review someone’s report SQL, the moment I see “LEFT JOIN + a WHERE filter on a right-table column” I almost always stop and ask “are you sure you don’t want to keep the unmatched ones?” Seven or eight times out of ten it’s a bug. And its root is the processing order: WHERE runs after the join. That’s why the processing-order post matters so much — many SQL bugs aren’t syntax errors, they’re your intuition about “when it happens” being wrong.

Count the rows before you SUM after a join

Fan-out (one-to-many multiplying the row count) is another classic “runs but computes wrong”. I’ve built a habit: before any join, ask “is this key unique in the right table?” If not, the left side’s rows will be duplicated after the join, and a direct SUM double counts. The fix is usually “aggregate the right table to one row first, then join”, or switch to a window function. This habit of “confirm cardinality before joining” has caught too many mysteriously mismatched totals for me — in the world of data, producing a number has never meant the number is right.