Hash Join vs Nested Loop Join vs Merge Join

When you write a SQL JOIN, you’re describing what result you want, not how to compute it. The query planner picks from a small set of physical join algorithms — nested loop join, hash join, and merge join — based on table sizes, available indexes, and whether the inputs are already sorted. Knowing what each one actually does makes an EXPLAIN ANALYZE output legible instead of mysterious.

This is a layer below the SQL you write, covered conceptually in how SQL joins work: that’s the logical operation (inner, left, full); this article is about the physical strategy the engine uses to actually produce it.

Nested loop join

The simplest strategy: for every row in the outer table, scan the inner table looking for matches.

for each row R in outer_table:
  for each row S in inner_table:
    if R.key == S.key: emit(R, S)

Without an index, this is O(n × m) — brutal for large tables. With an index on the inner table’s join key, it becomes an indexed nested loop: for each outer row, do an index lookup instead of a full scan, which is much closer to O(n log m).

Nested loop joins win when one side is small. Joining a 50-row lookup table against a 10-million-row fact table, with an index on the fact table’s foreign key, is a textbook case — the planner drives the loop from the small table and does cheap indexed lookups into the large one. A well-chosen B-tree index is what makes the inner lookup fast; without one, this strategy degrades badly as both tables grow.

Hash join

Build a hash table from the smaller input (keyed on the join column), then scan the larger input, probing the hash table for each row.

build_phase:  hash_table = { row.key: row for row in smaller_table }
probe_phase:  for each row R in larger_table:
                if R.key in hash_table: emit(R, hash_table[R.key])

This is the default workhorse for joining two large, unsorted tables with no useful index — the hash table turns an O(n × m) comparison into roughly O(n + m). The cost is memory: the build side has to fit in working memory, or the database spills partitions to disk (a “hybrid hash join”), which is slower but still generally better than a nested loop over unindexed large tables.

Hash joins only work for equality conditions (ON a.id = b.id), since a hash table can’t efficiently answer range queries. For <, >, or BETWEEN join conditions, the planner falls back to nested loop or merge join.

Merge join

If both inputs are already sorted on the join key — or can be cheaply sorted, or come from an index scan that returns rows in sorted order — a merge join walks both sorted lists with two pointers, advancing whichever side has the smaller current key, emitting matches as it goes. It’s essentially the merge step of merge sort, applied to two tables instead of two arrays.

Merge join is attractive when the sort is “free” — for example, both tables already have an index on the join column that produces sorted output, or the query also has an ORDER BY on that same column, so the sort pays for itself twice over. If the inputs aren’t already sorted, the database has to sort them first, which costs O(n log n) — often not worth it compared to a hash join, unless the result also needs to come out sorted.

Comparing the three

	Nested loop	Hash join	Merge join
Best for	One small table, indexed inner side	Two large, unsorted tables, equality join	Two pre-sorted (or cheaply sortable) tables
Typical complexity	O(n log m) indexed, O(n × m) unindexed	O(n + m)	O(n + m) once sorted, O(n log n) to sort
Memory use	Minimal	Build-side hash table (or disk spill)	Minimal, unless a sort is needed first
Join condition	Any (=, <, >, BETWEEN)	Equality only	Any, but only equality benefits from a pure merge
Output order	Follows outer table’s scan order	Unordered	Sorted on the join key

How the planner chooses

The query planner uses table statistics — row counts, distinct-value estimates, index availability — to estimate the cost of each strategy and picks the cheapest. This is the same cost-based reasoning covered in how database query optimizers work: the planner isn’t following a fixed rule, it’s comparing estimated costs for the specific tables and predicates in your query.

Stale statistics are a common reason the planner picks badly — if the optimizer thinks a table has 100 rows when it actually has 10 million, it may choose a nested loop join that should have been a hash join. Running ANALYZE (or your database’s equivalent) after large data changes keeps those estimates honest.

Indexing strategy also shapes which join gets chosen. The right index — see B-tree, GIN, and GiST index types for how index choice depends on data type and query pattern — can turn a hash join into a much cheaper indexed nested loop, particularly in OLTP workloads where queries touch a small slice of a large table. Wide analytical scans over most of a table, more typical of OLAP workloads, tend to favor hash joins instead, since indexed lookups stop paying off once you’re touching most of the rows anyway.

Reading it in an execution plan

EXPLAIN ANALYZE will name the strategy directly — Nested Loop, Hash Join, or Merge Join — along with estimated vs. actual row counts and timing for each step. A large gap between estimated and actual rows is the first thing worth checking when a plan looks wrong; it usually points back to stale statistics rather than a fundamentally bad plan shape. This matters whether you’re on PostgreSQL or MySQL — both expose the same three physical join strategies, even though the exact plan syntax differs.

The takeaway

Nested loop, hash, and merge join are the three physical strategies behind every logical JOIN. Nested loop wins when one side is small and indexed; hash join is the default for large, unsorted equality joins; merge join wins when both sides are already sorted on the join key. The planner picks based on cost estimates from table statistics, so accurate statistics and well-chosen indexes matter more than manually forcing a join strategy — read the EXPLAIN output before assuming the planner got it wrong.