JOINs

What is it: A JOIN combines rows from two or more tables based on a related column. The result is a new set of rows containing columns from both tables.

Types:

  • INNER JOIN: returns only rows that have a match in both tables. Non-matching rows are excluded.
  • LEFT JOIN (LEFT OUTER JOIN): returns all rows from the left table. For rows with no match in the right table, right-table columns are NULL.
  • RIGHT JOIN: mirror of LEFT JOIN — all rows from the right table.
  • FULL OUTER JOIN: all rows from both tables, NULLs on either side where there is no match.
  • CROSS JOIN: Cartesian product — every row from the left paired with every row from the right. O(n×m) rows. Almost always a mistake; use INNER JOIN with a condition.

Why JOINs are slow: JOINs are expensive because they combine large datasets. The cost depends on the join algorithm chosen by the planner:

graph TD subgraph nl["Nested Loop: O(n x m)"] nl1["for each row in outer table"] --> nl2["probe inner table (or its index)"] end subgraph hj["Hash Join: O(n+m)"] hj1["build hash table from smaller side"] --> hj2["scan larger side,<br/>look up each row in hash table"] end subgraph mj["Merge Join: O(n+m), needs sorted input"] mj1["both inputs sorted on join key"] --> mj2["scan both in lockstep,<br/>advance whichever side is behind"] end

Nested Loop Join: for each row in the outer table, scan the inner table (or probe its index) for matching rows. O(n×m) worst case; O(n log m) if the inner table has an index on the join key. Best when the outer table is small and the inner table has an index. A nested loop with no index on the inner table is the worst possible join — a full table scan per outer row.

Hash Join: build a hash table from the smaller table (the build side), then scan the larger table (probe side) and look up each row in the hash table. O(n+m) time, O(min(n,m)) memory. Best for large tables without useful indexes. Requires enough memory to hold the hash table; if it spills to disk (work_mem exceeded), performance degrades significantly.

Merge Join: requires both inputs sorted on the join key. Scans both inputs in parallel, merging matching rows. O(n+m) time after sorting. Best when both sides are already sorted (index scans on join key). Zero memory overhead for the merge itself, but sorting has O(n log n) cost if not pre-sorted.

When JOINs cause performance problems:

  • Missing index on the JOIN column: nested loop without index, or hash join spilling to disk
  • JOINing a huge table with another huge table: hash join requires memory proportional to the smaller table
  • Too many JOINs: each JOIN multiplies the row count before filtering; if WHERE is applied late, the intermediate result is enormous
  • Implicit Cartesian product: FROM a, b WHERE a.id = b.fk is equivalent to CROSS JOIN + WHERE, which the planner should optimize, but can be missed

Real-world usage: In Proxel's analytics queries: joining jobs with results with proxy_stats — adding indexes on foreign keys and re-ordering JOINs from smallest to largest table reduced query time from 8s to 200ms.

Common pitfall

Assuming the planner will always pick the "obviously" best join algorithm is a trap — the planner decides based on row-count estimates from table statistics, and stale statistics (a table that grew 100x since the last ANALYZE) can make it choose a nested loop where a hash join would be far cheaper, or vice versa. See Query Optimization for spotting this specific symptom — a large gap between rows= (estimate) and actual rows= in EXPLAIN ANALYZE output.