Nested Loop Join

Think of this as the database’s simplest but most honest join strategy: it checks one row against another until it finds a match. Interviewers love it because it reveals whether you understand that a SQL join is not just syntax — it is an execution plan choice.

Question: What is a nested loop join?

Answer: A nested loop join is a way to combine two tables by taking one row from the first table and comparing it to rows in the second table. If the join condition matches, the database outputs the combined row. It is simple, works for many kinds of join conditions, and becomes fast when the outer table is small or the inner table has a useful index.

Interview-Ready Answer: I think of a nested loop join as a row-by-row matching strategy. The database picks one input as the outer table, reads one row, and then searches the inner table for matching rows; if there is an index on the join key, that search can be very fast. It is often a great choice for small result sets, selective filters, or non-equality joins, but without an index it can degrade to a very expensive O(N×M) scan.

What it is

A nested loop join is the most direct join algorithm: for each row on the outer side, the database checks rows on the inner side until it finds matches. The word outer here means the driving input for the algorithm, not the SQL keyword OUTER JOIN.

How it works under the hood

1. The optimizer chooses a join order and labels one side as outer and the other as inner.
2. The engine reads one row from the outer input.
3. For that row, it scans the inner input or probes an index on the join key.
4. It evaluates the ON predicate; if the condition is true, it emits the combined row.
5. It repeats until the outer input is exhausted.
6. For a LEFT JOIN, if no inner row matches, the outer row is still returned with NULLs for the inner columns.

When and why to use it

Nested loop joins shine when the outer side is small, when the inner side has an index on the join key, or when the join condition is not a simple equality. A classic example is a query that starts with a few filtered customer rows and then looks up matching orders by indexed customer_id. They are also strong for EXISTS and semi-join style checks because the engine can stop after the first match.

Comparison with other join strategies

Performance and complexity

Without an index, the cost is roughly O(N×M). For example, 1,000 outer rows and 100,000 inner rows can mean up to 100 million comparisons, which is why a badly chosen nested loop can be slow. With an index on the inner join key, the engine often turns each inner lookup into a B-tree probe, which is closer to O(N log M) and usually much cheaper in practice. On cached data, that may be only a handful of memory accesses per lookup; on cold storage, random I/O is what hurts.

Important edge cases

• NULL does not equal NULL under =, so rows with null join keys usually do not match.
• Duplicate matches on the inner side produce duplicate output rows; the algorithm does not deduplicate for you.
• Join order matters a lot: the same SQL can be fast or slow depending on which table becomes the outer input.
• Nested loop is not the same as a nested subquery, although the optimizer may transform one into the other.

Memory rule: if you can picture one person walking down a list and asking, “Do you match?” for every row, you understand nested loop join.

Real-world story: In an e-commerce checkout service, a query may join a small set of cart items to an indexed product table and an indexed pricing table. When the cart has 5 to 20 rows, a nested loop join is often the best choice because each lookup is cheap and predictable. The database can walk the few cart rows and quickly fetch the matching product and price data.

What goes wrong is usually an indexing or join-order mistake. Suppose a deployment drops the index on product_id, or a query rewrite accidentally makes a 50,000-row enrichment job drive the join. Suddenly the database starts scanning millions of product rows for every batch record. Symptoms look like this: CPU jumps to 100%, the slow-query log shows execution time rising from milliseconds to tens of seconds, and application logs fill with timeout errors. Users feel it as a checkout spinner, retries, and abandoned carts.

The key lesson is that nested loop joins are not inherently bad; they are excellent when the data shape matches the algorithm. The outage happens when the assumption breaks and the inner lookup stops being cheap.

Follow-up & Tricky Questions:

• How is nested loop join different from hash join? A nested loop compares rows one outer row at a time, while a hash join builds a hash table on one side and probes it. Hash join is usually better for large equality joins; nested loop is often better when the outer side is small or the inner side is indexed.
• Why does an index make nested loop join faster? Because the inner lookup becomes a targeted search instead of a full scan. The database can jump directly to candidate rows for each outer row instead of reading every inner row.
• When would you pick nested loop on purpose? When the driving input is small, when the join is selective, or when you need a non-equality condition that hash join cannot handle well. It is also a common choice for EXISTS checks because the search can stop at the first match.
• What does the optimizer care about most? Join order, row counts, and available indexes. A good plan makes the smallest or most selective table drive the join so the repeated inner work stays cheap.
• Can nested loop join be used for outer joins? Yes. The algorithm can still drive from one side and preserve unmatched outer rows, filling the missing inner columns with NULL.
• Tricky: do NULL join keys match each other? No, not with =. Two NULLs are not considered equal in normal SQL comparisons, so you need special logic such as IS NOT DISTINCT FROM if you want null-safe equality.
• Tricky: is nested loop always the slowest join? No. With a small outer input and a good index on the inner side, it can beat hash join because it avoids building a hash table and touches far less data.
• Tricky: does the SQL text force nested loop join? Usually no. The optimizer chooses the physical plan, and the same SQL can use nested loop, hash join, or merge join depending on data statistics and indexes.

Common Mistakes:

• Thinking nested loop is always bad. Correction: it is often the best plan for small or highly selective joins.
• Forgetting the outer/inner roles. Correction: the outer side drives the loop; the inner side is checked repeatedly.
• Ignoring indexes. Correction: a good inner index can turn a painful full scan into a fast lookup.
• Assuming NULL matches NULL. Correction: normal = comparisons do not match nulls.

Memory Hook: One row walks into the shop, asks every shelf the same question, and stops early if it finds a labeled drawer.

Cheat Sheet:

• Nested loop = row-by-row comparison.
• Best for small outer inputs or indexed inner inputs.
• Can handle many join predicates, including non-equality.
• Worst case is O(N×M) without an index.
• Great for EXISTS and selective lookups.
• Join order and indexes decide whether it is fast or painful.

Practice Tasks:

• Write a simple inner join between customers and orders and identify the outer and inner sides.
• Change the query to a LEFT JOIN and observe which rows survive when there is no match.
• Add and remove an index on the inner join key in your database, then compare the execution plans and timing.