Part 161: Join Physical Algorithms: Nested Loop vs Hash Join vs Merge Join

How relational database engines physically join tables together on disk and in memory.

1. The 3 Fundamental Join Algorithms

When you write FROM orders o JOIN customers c ON o.customer_id = c.id, the query optimizer chooses one of three physical algorithms based on statistics and indexes:

2. Nested Loop Join

Iterates through outer table row by row, looking up matching rows in the inner table. - Best For: Small outer table joined against an indexed inner table (Index Seek). - Time Complexity: $O(N \times \log M)$ with index, $O(N \times M)$ without.

-- Typical Nested Loop Plan:
-- -> Nested Loop (cost=0.43..12.50)
--    -> Index Scan using orders_date_idx on orders (outer)
--    -> Index Scan using customers_pkey on customers (inner lookup)

3. Hash Join

Builds an in-memory hash table of the smaller table on the join key, then streams the larger table to probe the hash table. - Best For: Large, unindexed tables with equality join conditions (=). - Memory Consumption: Uses work_mem (Postgres) or Hash Grant (SQL Server). If memory overflows, it spills to disk (TempDB/workfile), drastically slowing down.

4. Merge Join (Sort-Merge Join)

Sorts both tables by the join key (if not already sorted by an index), then scans both streams concurrently like a zipper. - Best For: Large tables where both inputs are already sorted by the join key or for inequality/range joins. - Time Complexity: $O(N + M)$ if already sorted.

Summary Comparison

Key Takeaways

• An unexpected Hash Join on an OLTP query usually signals a missing foreign key index.

In Part 162, we explore Index Access Paths: Index Seek, Index Scan & Index-Only Scan!