How Does the Nested Loop Join Algorithm Work?
Learn how the nested loop join algorithm works, why an inner index matters, and when the optimizer picks it over hash join.
Expected Interview Answer
A nested loop join works by iterating over every row of an outer table and, for each one, scanning or probing an inner table to find matching rows, making it the simplest join algorithm and the optimizer's typical choice when the outer input is small or the inner side has a usable index.
The algorithm has two nested loops: the outer loop reads each row of the first (outer) table, and for every such row, the inner loop searches the second (inner) table for rows satisfying the join condition. If the inner table has an index on the join column, each inner search is a fast index lookup rather than a full scan, which keeps total cost proportional to the outer row count times the cost of one index lookup rather than the full product of both table sizes. Without a usable index, nested loop join degrades badly because it rescans the entire inner table once per outer row, which is why the optimizer switches to hash join or merge join when both tables are large and unindexed.
- Simple and effective when the outer side is small
- Very fast per outer row when the inner side has a matching index
- Low memory overhead compared to hash join
- Can start returning rows immediately without building an intermediate structure
AI Mentor Explanation
Think of a scorer cross-referencing every batter in today's lineup against a season records book: for each of the eleven batters (the outer loop), the scorer flips to that player's page in the records book (the inner loop) to pull their season average. If the records book has a name index at the front, each lookup is instant; without it, the scorer would have to flip through the whole book for every single batter. A nested loop join works exactly this way, iterating the outer rows and probing the inner table once per row.
How Nested Loop Join Pairs Outer Rows With Inner Matches
Outer: Orders (scanned once)
- order_id
- customer_id
Inner: Customers (index probe per outer row)
- customer_id
- name
Output: joined rows
- order_id
- customer_id
- name
Step-by-Step Explanation
Step 1
Read the next outer row
The outer loop fetches one row at a time from the outer (typically smaller) table.
Step 2
Probe the inner table
For that outer row, the inner loop searches the inner table for matches on the join column, via index if available.
Step 3
Emit matched pairs
Any inner rows satisfying the join condition are combined with the current outer row and output.
Step 4
Repeat until the outer table is exhausted
The process continues for every outer row until all have been probed against the inner table.
What Interviewer Expects
- Clear explanation of the outer-loop/inner-loop structure
- Awareness that an index on the inner join column is what makes it fast
- Knowledge of when the optimizer prefers nested loop over hash or merge join
- Understanding of the cost degrading without an inner index on large tables
Common Mistakes
- Describing nested loop join without mentioning the inner-side index dependency
- Assuming nested loop join is always the worst choice
- Confusing nested loop join with a Cartesian product
- Not recognizing when the optimizer would switch to hash join instead
Best Answer (HR Friendly)
“A nested loop join works by taking each row from one table and, for every single row, searching the other table for a match. It is simple and very fast when the table being searched has a good index on the join column and the other table is relatively small, but it gets slow if there is no index and both tables are large, since every row triggers a full search of the other table.”
Code Example
-- Small outer table (Orders filtered to one day) joined against
-- a large but indexed Customers table on customer_id.
EXPLAIN
SELECT o.order_id, c.name
FROM Orders o
JOIN Customers c ON o.customer_id = c.customer_id
WHERE o.order_date = '2026-07-17';
-- Likely plan: Nested Loop
-- -> Index Scan on Orders using idx_order_date
-- -> Index Scan on Customers using customers_pkey (per outer row)Follow-up Questions
- How does nested loop join differ from hash join?
- What happens to nested loop join performance without an index on the inner table?
- How does the optimizer decide which table becomes the outer table?
- What is an index nested loop join specifically?
MCQ Practice
1. In a nested loop join, what happens for each row of the outer table?
For every outer row, the inner loop searches (scans or probes) the inner table for rows matching the join condition.
2. What makes a nested loop join especially efficient?
An index on the inner join column turns each inner search into a fast lookup instead of a full table scan.
3. Nested loop join tends to perform worst when?
Without an inner index, each outer row triggers a full scan of a large inner table, making cost grow with both table sizes.
Flash Cards
What is a nested loop join? — A join algorithm that, for each outer row, searches the inner table for matches.
What makes nested loop join fast? — An index on the inner table's join column, turning each search into a quick lookup.
When does nested loop join perform poorly? — When the inner table is large and lacks an index, forcing a full scan per outer row.
What join algorithm might replace it on large unindexed tables? — Hash join or merge join, which the optimizer picks when nested loop would be too costly.