Skip to main content
databases

Query planners and join algorithms

11 min read
Fully authored

How Postgres picks nested-loop vs hash vs merge join — and why one query is 1000x faster than another.

Same SQL query. Different plans. Different performance. The query planner picks the plan based on statistics (row counts, distinctness, correlation) and cost model (I/O, CPU, memory). Understanding this is the difference between a query that runs in 5ms and one that runs in 5 seconds.

Nested Loop

Cost: O(N × M)

Best for: Small outer (<100 rows), index on inner. Postgres default for small correlated queries.

SELECT * FROM users u JOIN orders o ON o.user_id = u.id WHERE u.email = 'x@y.com'

EXPLAIN — the debugging tool

Every DB has one. Postgres's EXPLAIN (ANALYZE, BUFFERS) is the gold standard. Reads:

Nested Loop (cost=0.29..12.44 rows=1 width=64)
-> Index Scan using idx_users_email on users u
Index Cond: (email = 'x@y.com'::text)
-> Index Scan using idx_orders_uid on orders o
Index Cond: (user_id = u.id)

Two things to look for: (1) Sequential scans on big tables → missing index. (2) Wrong row estimates → run ANALYZE to update statistics.

The 5 planner behaviors every senior knows

  1. Stale statistics → wrong plans. Auto-vacuum handles this; disable at your peril.
  2. Parameterized queries with skew (WHERE status = ?) may pick wrong plan for uncommon values. Use plan_cache_mode.
  3. LIMIT + ORDER BY changes plans dramatically — planner assumes rows can be returned early.
  4. Joining 3+ tables: planner reorders. Postgres considers up to geqo_threshold=12 tables exhaustively.
  5. work_mem too small = hash spills to disk = 100× slowdown. Tune per session for big analytical queries.

Applied in these systems

URL Sh Ch 5.5 — why Postgres over MongoDBSlack Ch 4 — indexed message queries

Practice what you just read

Every foundation concept has a companion quiz to close the loop.

Take the URL Shortener quizOpen the flagship problem

More in databases

Database Types — SQL, NoSQL, NewSQLIndexes — the promise and the costB-treesLSM treesIsolation levels