Join Algorithms: Nested Loop, Hash, Merge
How each join is executed and when each is the right choice.
Joins Are Algorithms, Not Just Syntax
You already know INNER JOIN as syntax. At senior level interviewers ask how the database physically executes a join. There are three algorithms:
- Nested Loop Join
- Hash Join
- Merge Join (sort-merge)
The logical join type (INNER, LEFT) is independent of the algorithm. The planner picks the algorithm based on table sizes, indexes, and sort order. Knowing when each wins is the heart of this lesson.
Nested Loop Join
The Nested Loop is the simplest: for each row of the outer table, scan the inner table for matches. In pseudocode, two loops, one inside the other.
Naively this is O(outer * inner), terrible for big tables. But it becomes excellent when the inner side has an index on the join key: each outer row triggers a cheap index lookup instead of a full inner scan.
It is the planner's favorite when the outer table is small and the inner join column is indexed.
Nested Loop (cost=0.42..120.5 rows=15 width=72)
-> Seq Scan on customers c (rows=3)
-> Index Scan using idx_orders_cust on orders o
Index Cond: (o.customer_id = c.id)
(loops=3)All lessons in this course
- Reading an EXPLAIN Plan
- Seq Scan vs Index Scan vs Index-Only
- Join Algorithms: Nested Loop, Hash, Merge
- Spotting and Fixing Slow Queries