Joins

A join looks at every possible pairing of two tables and keeps the pairs you asked for: everything surprising about joins follows from that one sentence.

The idea

Imagine laying every row of the left table next to every row of the right table: all n × m combinations. The join condition is just a filter over that pile of pairings. INNER keeps only the pairings that pass. LEFT does the same, but before moving on it checks each left row: if nothing survived for it, the left row is kept anyway with the right-hand columns filled with NULL.

Two things follow. If a key appears twice on the right, one left row leaves as two rows: the join multiplied it. And on an outer join, a condition in ON filters pairings while the same condition in WHERE filters the finished result, which quietly deletes the NULL rows the join just went to the trouble of preserving.

Watch a join actually run

Nested-loop join, one pairing per step. Change a control to jump straight to the finished result, then press reset and walk it through.

kept pairing
discarded pairing
NULL fill (LEFT only)

SELECT u.name, o.o_id, o.region
FROM   users u
INNER JOIN orders o
  ON   u.id = o.user_id AND 
WHERE

spare predicate: drag it into ON or WHERE, or use the buttons below

join type

right table

predicate

result

u.name	o.o_id	o.region

How it works

Every join engine is an optimisation of this loop. The ordering matters: ON runs while pairings are being formed, the NULL fill happens at the end of each left row, and WHERE runs on whatever came out.

def join(left, right, on, kind="inner", where=None):
    """on(l, r) -> bool   decides which *pairings* survive
       where(row) -> bool decides which *result rows* survive"""
    right_cols = {k for r in right for k in r}
    nulls = {k: None for k in right_cols}      # the NULL fill

    out = []
    for l in left:                             # every pairing of left x right
        matched = False
        for r in right:
            if on(l, r):                       # ON filters pairings
                out.append({**l, **r})         # a duplicate key here
                matched = True                 # emits two rows for one l
        if kind == "left" and not matched:
            out.append({**l, **nulls})         # LEFT rescues the left row

    if where is None:
        return out
    return [row for row in out if where(row)]  # WHERE filters the result

# predicate in ON   -> keeps 4 rows, three of them NULL-filled
join(users, orders, lambda u, o: u["id"] == o["user_id"]
                                 and o["region"] == "west", "left")

# predicate in WHERE -> keeps 1 row; the NULL rows fail region == "west"
join(users, orders, lambda u, o: u["id"] == o["user_id"], "left",
     where=lambda row: row["region"] == "west")

In SQL, NULL = 'west' is not false: it is unknown, and WHERE only keeps rows that are definitely true. That is exactly why the rescued rows disappear.

Cost

strategy	time	extra space
nested loop (no index)	O(n · m)	O(1)
nested loop + index on right key	O(n · log m)	O(1)
hash join (equality only)	O(n + m) average	O(m)
sort-merge join	O(n log n + m log m)	O(1) beyond sorting
the output itself	up to O(n · m)	up to O(n · m)

The trade-off: hash join buys linear time with memory for the hash table, and needs an equality condition. Sort-merge needs no extra memory but pays for ordering, and handles range conditions. None of them changes the last row of the table: if the join keys are not unique, the result can be far larger than either input, and no algorithm can make that cheap.

Watch out for

A join is not a lookup. If the right key is not unique, row counts multiply. Check first: SELECT user_id, count(*) FROM orders GROUP BY user_id HAVING count(*) > 1. Sums and averages downstream will be inflated by exactly that factor.
A right-table filter in WHERE turns a LEFT JOIN into an INNER JOIN. LEFT JOIN orders o ON … WHERE o.region = 'west' deletes every NULL-filled row. If you meant "west orders, but keep customers with none", the condition belongs in ON.
NULL compares to nothing. o.region <> 'west' also drops the NULL rows, because unknown is not true. Write (o.region <> 'west' OR o.region IS NULL) or use coalesce.
COUNT(*) after a LEFT JOIN counts rows, not matches. A customer with no orders still contributes one row, so you get 1 instead of 0. Use COUNT(o.o_id), which ignores NULLs.
A left-table condition in ON does not filter the left table. LEFT JOIN … ON u.id = o.user_id AND u.active keeps inactive users: it just refuses to match them, so they arrive NULL-filled. That is almost never what people mean.

Worked example

You want a dashboard row per customer: name, plus how many west-region orders they placed. Four customers exist; ada has two west orders, cleo has one east order, brin and dev have none.

The first draft, LEFT JOIN orders o ON u.id = o.user_id WHERE o.region = 'west', produces one row. The join honestly built five rows (ada twice, plus three NULL-filled), and then WHERE tested NULL = 'west' on the rescued rows, got unknown, and threw them out along with cleo's east order. The dashboard now claims you have one customer.

Move the predicate up into ON and the join instead refuses to pair non-west orders: ada keeps both matches, cleo/brin/dev come through NULL-filled, four rows out. Then GROUP BY u.name with COUNT(o.o_id) gives ada 2 and everyone else 0, because COUNT of a column skips NULLs, while COUNT(*) would have said 1. Try it in the visual above: switch to left, add the duplicate key, then drag the predicate between ON and WHERE.

Check yourself

1. users has one row for user 1; orders has three rows for user 1. How many result rows does users INNER JOIN orders ON u.id = o.user_id produce for user 1?

2. You want only the customers who have never ordered. You write users u LEFT JOIN orders o ON u.id = o.user_id. Where does o.o_id IS NULL belong?