The Three Join Algorithms Every Query Planner Picks Between

When a query touches two tables, the planner has to pick a join algorithm. There are basically three to know, and each one wins in a different shape of data. Reading an EXPLAIN plan and understanding which one was chosen is the difference between a 5ms query and a 5 minute query on the same schema.

Nested loop is the brute force version. For every row in the outer table, scan the inner table looking for a match. If the inner side has an index on the join key, every probe is a cheap lookup and the algorithm behaves well. If the inner side has no index, you are paying O(N times M) and a join on two million-row tables turns into a trillion row comparisons. Nested loop is the right choice when the outer side is small, say a hundred rows, and the inner side is indexed on the join column. It is the wrong choice the moment the outer side grows.

Hash join is the workhorse for medium-to-large equality joins. The planner picks the smaller side as the build input, scans it once, and constructs a hash table in memory keyed on the join column. Then it streams the larger side through, hashing each row's join key and looking it up. Each probe is O(1) on average. The catch is that the hash table has to fit in memory. If it does not, the engine spills to disk in batches, and the join slows down significantly. Postgres calls this a batched hash join. Watching work_mem and seeing batches greater than one in the plan is a clear signal to either increase memory or push the join down to fewer rows.

Merge join wins when both inputs are already sorted on the join key. You walk both sides in lockstep, advancing whichever pointer is behind. It is O(N plus M) with no hashing and no memory pressure. The two cases where you see it are when both sides are reads from a B-tree index in key order, and when a previous step already sorted the data, for example after a GROUP BY on the same column. If neither is true, paying to sort both sides usually loses to hash join.

The mental model fits on three lines. Nested loop: index the inner side or keep the outer side tiny. Hash: equality joins with enough memory. Merge: free if the data is already sorted. When a query feels slow, the first thing I do is run EXPLAIN ANALYZE and check which join the planner picked and why. The answer is almost always there.