Joins

What a Join Physically Does

 SELECT r.name, t.fare_cents
 FROM riders r JOIN trips t ON t.rider_id = r.id
 WHERE t.created_at > now() - interval '1 day';

 logically: match rows across two tables on the key.
 physically: the PLANNER picks an ALGORITHM — three exist,
 and knowing which fires when is core performance literacy.

Algorithm 1: Nested Loop

 for each outer row:
     probe inner side via INDEX for matches

 riders(10) × trips(idx on rider_id):
   10 index probes → instant. PERFECT when one side is small.

 cost ≈ outer_rows × index_probe
 disaster zone: outer large + inner UNINDEXED → O(n×m) scan hell.
 the planner avoids this; your missing indexes force it.

Algorithm 2: Hash Join

 build phase:   hash the SMALLER table into memory (key → rows)
 probe phase:   stream larger table; probe hash per row

 trips_today(500k) JOIN cities(200):
   hash 200 cities → stream 500k trips probing → linear total.

 cost ≈ read_both_tables_once    ← scales beautifully
 constraint: hash must FIT memory (else it spills to disk, slow)
 best for: large×large joins without useful sort order.

Algorithm 3: Merge Join

 both sides sorted by key → merge like tape drives:

 if trips sorted by rider_id AND users sorted by id:
   walk both in lockstep, never rewinding.

 wins when: inputs already sorted (via index!) or output
 needs sorted order anyway; huge datasets beyond memory.

Reading the Planner’s Choice

 EXPLAIN the query; the plan names the algorithm:

 Hash Join  (cost=... rows=480000)
   -> Seq Scan on trips_today
   -> Hash
        -> Seq Scan on cities

 diagnosis patterns:
 - Nested Loop with Seq Scan inner = MISSING INDEX (fix!)
 - Hash join spilling to disk = stats/memory issue or bad estimate
 - planner chose loop over hash = STALE STATISTICS lying about sizes
 ANALYZE (refresh stats) fixes surprising planner choices constantly.

Join Design at Scale

Concern	Guidance
Join fan-out	One-to-many explodes row counts — watch aggregates after joins
Join depth	5+ table joins signal denormalization time
Cross-shard joins	Don’t — co-locate by shard key or denormalize
ORM N+1 queries	The app-level join disease; batch-load instead

 the scaling ladder for "join too slow":
 1. index the join columns        (usually the actual fix)
 2. refresh statistics            (planner was guessing)
 3. reduce joined width           (project fewer columns early)
 4. denormalize/materialize       (pre-compute the relationship)

Interview Framing

“Query joining orders+users is slow” expects: ask for EXPLAIN first, then map symptoms to algorithms — nested-loop-with-scan means missing index, hash-spill means memory/stat issues. Naming all three algorithms with their sweet spots (small×indexed / big×big / sorted) is baseline literacy; the statistics-refresh anecdote marks production experience.