INNER JOIN

An INNER JOIN pairs each row of one table with every row of another that satisfies a boolean predicate (the ON condition), emitting the concatenated row only when the predicate is true — so the result is the filtered Cartesian product of the two inputs, never the inputs themselves.

That one sentence hides three different physical strategies the planner can pick — nested-loop, hash, or merge — and the choice is the entire difference between a join that returns in 2 ms and one that hangs your service. The logical answer is identical for all three; the cost is not.

The inputs we will trace

Two tiny tables. department_id is a foreign key in employees pointing at the primary key of departments. Note the deliberate edge cases: employee 104 has department_id = NULL (not yet assigned), and department 30 (Legal) has no employees.

SELECT e.employee_id, e.employee_name, d.department_name
FROM   employees AS e
INNER JOIN departments AS d
  ON   e.department_id = d.department_id;

Mechanism: the nested-loop trace

The simplest physical plan is a nested-loop join: for every outer row, scan the inner table and test the predicate. Walk it row by row — this is literally what the engine does when there is no useful index:

1. e=101 (dept 10): compare to d=10 �match → emit (101, Asha, Engineering); d=20 ✗; d=30 ✗.
2. e=102 (dept 20): d=10 ✗; d=20 ✓match → emit (102, Bilal, Sales); d=30 ✗.
3. e=103 (dept 10): d=10 ✓match → emit (103, Chen, Engineering); d=20 ✗; d=30 ✗.
4. e=104 (dept NULL): NULL = 10, NULL = 20, NULL = 30 each evaluate to UNKNOWN, never TRUE → no row emitted. Devi vanishes.

Department 30 (Legal) is also absent: nothing on the employee side ever matched it. That is the defining behaviour of INNER — a row survives only if it has a partner on the other side. The full pairing space was 4 × 3 = 12 candidate comparisons; exactly 3 passed.

The three physical join algorithms

The planner never runs the naive O(N×M) loop on real data if it can avoid it. It chooses among three implementations based on table sizes, available indexes, and whether inputs are already sorted:

Critical constraint: hash and merge joins only work for equality predicates (=). A join on a.x < b.y or a range falls back to nested loop — which is why an accidental non-equi join can quietly turn O(N+M) into O(N×M).

Cardinality and fan-out

The output row count is not bounded by either input. For each distinct join-key value v, the join emits count_left(v) × count_right(v) rows. When both sides have many rows per key, this fans out multiplicatively.

In our trace department_id is unique in departments (it is the PK), so the right multiplier is always 0 or 1 and the result can never exceed the employee count. But join two tables on a non-unique column — say 5 orders and 5 shipments that all share order_id = 42 — and you get 5 × 5 = 25 rows for that key alone. This is the classic source of inflated SUM() and COUNT() after a join: you aggregated a fanned-out intermediate, not the real rows.

Pitfalls

• NULLs silently disappear. NULL = NULL is UNKNOWN, not TRUE. Any row whose join key is NULL is dropped by an INNER JOIN — Devi above is gone with no warning. If you need her, you want a LEFT JOIN, not INNER.
• Putting the filter in WHERE vs ON is identical for INNER but a trap you carry into outer joins. For INNER, ON a=b WHERE d.active and ON a=b AND d.active return the same rows. Convert that same query to a LEFT JOIN and the WHERE d.active version silently turns it back into an inner join (it filters out the NULL-extended rows). Build the habit now: join conditions go in ON, row filters go in WHERE.
• Fan-out wrecks aggregates. Joining on a non-unique key multiplies rows; a later SUM(amount) then double-counts. Pre-aggregate in a subquery before joining, or join on a key you have verified is unique on at least one side.
• Missing index on the join column → hash/merge or a slow scan. Without an index on employees.department_id, an indexed nested loop is impossible; on big tables the planner falls back to a hash join that needs enough work_mem, or it spills to disk. Index foreign-key columns you join on.
• Accidental non-equi or missing predicate → Cartesian explosion. A typo that drops the ON clause (or a range predicate) forces nested loop and produces N×M rows. On two 100k-row tables that is 10 billion rows.
• Ambiguous column names. SELECT department_id when both tables have it raises an ambiguity error. Always alias tables and qualify columns (e., d.).

Takeaways

• INNER JOIN = filtered Cartesian product: a row survives only if it finds at least one partner satisfying ON; unmatched rows and NULL-keyed rows are dropped.
• The same logical result is produced by nested-loop, hash, or merge join — the planner picks by sizes/indexes/sort order, and that choice is where performance lives. Hash and merge need equality keys.
• Result cardinality is per-key left × right, so non-unique join keys fan out and corrupt downstream aggregates — pre-aggregate or join on a unique side.
• Index the join columns, keep join logic in ON and filters in WHERE, and reach for LEFT JOIN the moment you need to keep unmatched or NULL-keyed rows.

Sources: ISO/IEC 9075 (SQL standard) join semantics and three-valued logic; PostgreSQL documentation — "Joins Between Tables" and Chapter 14 "Performance Tips" (nested-loop, hash, and merge join executors); Garcia-Molina, Ullman & Widom, Database Systems: The Complete Book (join algorithms and cost); use.index.de / Markus Winand, SQL Performance Explained (join indexing). Re-authored and deepened for this guide: replaced image-only tables/result with a row-by-row nested-loop trace, added hash/merge mechanism, cardinality and fan-out, ON-vs-WHERE and NULL pitfalls, and corrected the code block previously mislabeled "java".

🎯 STRICT STANDOUT: Why / worked / when-not / failure / drills — INNER JOIN

Why this concept exists (judgment chain)

INNER JOIN is the filtered Cartesian product: rows survive only with a TRUE ON match. NULL keys never match. Physical plans (nested loop / hash / merge) share semantics but not cost; fan-out on non-unique keys corrupts aggregates.

Worked example with numbers or traced steps

employees: 101→10, 102→20, 103→10, 104→NULL; depts 10,20,30
Nested loop: 12 comparisons, 3 emits (Asha,Bilal,Chen); Devi & Legal drop.
Hash join: build on depts (3 keys), probe 4 employees — same 3 rows, O(N+M).
Fan-out: 5 orders × 5 shipments on order_id=42 → 25 rows; SUM(amount) 5× inflated.
Fix: pre-aggregate or join on unique side.

When NOT to use / named alternative

Use LEFT/RIGHT/FULL when unmatched rows must appear. Prefer EXISTS semi-join when you only need existence without multiplying rows. Avoid non-equi joins on large tables without indexes (forces nested loop). Do not put outer-join filters in WHERE if you meant to keep NULLs.

Failure / ops fingerprint

Fingerprint: headcount reports missing unassigned employees; revenue after join 5× high; hash join spill when work_mem low. Ops: EXPLAIN join type; index FK columns; assert COUNT after join ≤ expected bound in tests.

Hostile-panel drills (defend the decision)

Q1. Why does NULL department_id drop on INNER?
Model answer: NULL = k is UNKNOWN, never TRUE; INNER keeps only TRUE matches.

Q2. When is hash join preferred?
Model answer: Large equi-joins without useful order/index; build smaller side in memory, probe larger — O(N+M) if no spill.

Q3. How does fan-out break SUM?
Model answer: Per key, left_count×right_count rows; each amount repeated; pre-aggregate one side first.