Nested Loop Join

A Nested Loop join iterates the outer input and, for every outer row, executes the inner side to find matches. With an indexed inner side this is a series of cheap index lookups.

When the outer side returns few rows and the inner side can be probed cheaply (typically via an index). It's the only join that streams results without first materializing either side.

Ideal for small driving sets with an indexed inner. It turns toxic when the outer side is large or under-estimated and the inner is rescanned thousands of times — often a row-estimate problem that should flip the plan to a hash or merge join.

How it works under the hood

A Nested Loop is the simplest join: for each row from the outer (left) input, it executes the inner (right) input to find matches. With an indexed inner side, "execute the inner" means a cheap index lookup, so the total cost is roughly outer rows × cost of one lookup.

That formula explains both its strength and its failure mode. A handful of outer rows × a fast index probe = the fastest join there is. Ten million outer rows × even a cheap probe = a disaster.

Reading the loops

The number that matters is loops on the inner side:

Nested Loop  (actual time=... rows=2388 loops=1)
  ->  Seq Scan on big2 t  (... rows=2388 loops=1)
        Filter: (amt < 5)
  ->  Materialize  (... rows=1000 loops=2388)
        ->  Seq Scan on dim d  (... rows=1000 loops=1)

loops=2388 means the inner side was driven 2,388 times. Here it's a Materialize over a 1,000-row table, so each rescan is in-memory and cheap — but if that inner were an un-indexed scan of a big table, this plan would read it 2,388 times over.

The usual root cause: a bad estimate

A nested loop turns pathological when the planner under-estimates the outer side. It thinks "only 3 outer rows, a nested loop is perfect," then 300,000 rows show up and the inner is hammered. The plan looks reasonable; the estimate was the lie.

Fixes, in order:

1. ANALYZE the tables — fresh stats often correct the estimate.

2. Extended statistics for correlated columns:

   CREATE STATISTICS s (dependencies) ON col_a, col_b FROM t;
   ANALYZE t;
   

3. Once the estimate is right, the planner usually switches to a Hash Join on its own.

Memoize: a nested loop that learns

Since PostgreSQL 14 the planner can place a Memoize node on the inner side. It caches inner results per lookup key, so repeated keys are served from cache instead of re-probing. For skewed, low-cardinality join keys this rescues an otherwise expensive nested loop — watch the cache hit ratio in EXPLAIN ANALYZE.

• Nested Loop rescans — the inner side is re-executed far too many times
• Bad row estimate — an under-estimated outer side is the usual root cause

Paste a plan into the analyzer →

effective_cache_sizerandom_page_cost

How we tune these →

Why is my nested loop so slow?

Usually the outer side returns many more rows than the planner expected, so the inner side is rescanned over and over. Fix the estimate (ANALYZE, extended statistics) and the planner will often switch to a hash join.

• Hash Join
• Merge Join
• Memoize
• Materialize