What is an index nested loop join, and how does its cost model differ from a nested loop join over an inner table with no usable index?

## The variant An index nested loop join keeps the outer loop and deletes the inner one. For each outer row, the engine takes the join key value and uses it as a lookup key into an index on the inner table's join column. Only the matching inner entries are visited. The join predicate stops being a filter applied to every inner row and becomes an access condition that navigates directly to the matches. ## Cost model Unindexed nested loop: n_outer * P_inner page reads, growing with the size of both inputs. Index nested loop: one scan of the outer input, plus n_outer probes. Each probe costs a descent through the index (a handful of page accesses, logarithmic in inner table size and usually shallow because index fan-out is high), plus reading the matching index entries, plus one base-table fetch per matching row when the index does not contain all required columns. Total is roughly n_outer * (descent + matches * fetch). The size of the inner table appears only inside a logarithm and in cache behaviour — that is the whole point: the join now scales with the outer side. ## Why the constant is not small Each base-row fetch follows index order, not physical order, so it behaves like random I/O. Upper index levels are usually cached, but leaf pages and heap pages for a large inner table often are not. This is why the operator's advantage collapses as the outer count rises: at a million outer rows, even a few random reads each dwarfs the cost of scanning the inner table once sequentially and hashing it. Engines mitigate this with batched or prefetching lookup strategies that gather keys and fetch in a more sequential pattern, but the shape of the tradeoff stands. ## Requirements The inner index must be usable for the join predicate: the join column must be a leading column of the index, and the comparison must be one the index can navigate. Type mismatches or an expression wrapped around the inner column can silently prevent index use, turning the plan back into a full scan per outer row — a classic cause of a query that is suddenly thousands of times slower. A covering index that includes the other columns the query needs removes the base-row fetch and makes the probe dramatically cheaper. ## Where it shines Highly selective queries: fetch a handful of orders, then look up their customers by primary key. Point queries and small result sets in transactional workloads are almost always index nested loops, and that is usually right there — a hash join would read whole tables to answer a question about ten rows. It also pipelines, returning the first joined row after one probe, so queries that stop early benefit enormously. ## Where it fails When the outer input is large, when the inner index is not selective so each probe matches many rows, or when the inner table is far bigger than cache so every probe is a physical read. Those are the conditions under which hash join or merge join over sequential scans wins, and the optimizer's job here is estimating the outer row count well enough to tell the two regimes apart. ## Practical reading In a plan, this operator appears as a loop node whose inner child is an index access parameterised by a value from the outer side, executed once per outer row. The two numbers to look at are how many times the inner side executed and how many rows each execution returned; multiplied, they tell you what the join really cost.