Join strategies: nested loop, hash and merge

However you write a join (JOIN … ON, WHERE a.x = b.x, EXISTS, IN), the executor has three algorithms to choose from. Each joins two inputs: the outer (first child in the plan) and the inner (second child).

Nested Loop. For each outer row, look up the matching inner rows. If the inner side has an index on the join column, each lookup is a quick index probe. Cost ≈ outer rows × cost of one lookup. Excellent when the outer side is small (a filtered handful of rows); terrible when it is large and the inner side has no index, because then every outer row triggers a scan.

Hash Join. Read the inner input once and build an in-memory hash table keyed on the join column (the Hash node), then read the outer input once and probe the hash table for each row. Cost ≈ one pass over each input. The workhorse for large, unsorted inputs and equality joins. It needs memory: if the hash table doesn't fit in work_mem, it is split into batches written to temporary files.

Merge Join. Sort both inputs on the join key (or read them already sorted from indexes), then walk them side by side like a zipper. Good when both inputs are large and already sorted, or when the result must be sorted on the join key anyway.