Nested Loop Join: The Brute-Force Database Join

Why it exists

Databases need a fundamental, always-available method to combine data from two tables based on a join condition. The nested loop join provides this baseline implementation. It's the simplest possible algorithm to write and understand, serving as a fallback when more advanced strategies like hash or merge joins aren't applicable or efficient.

The mental model

Think of finding matching socks in two different drawers. You pick one sock from the first drawer (the outer table) and then rummage through every single sock in the second drawer (the inner table) looking for its pair. You repeat this process for every sock in the first drawer. It's exhaustive and guaranteed to find all matches, but it's very slow if you have lots of socks in both drawers.

How it works

The algorithm designates one table as the "outer" relation and the other as the "inner" relation. It then iterates through each row of the outer table. For every single outer row, it performs a full scan of the entire inner table, checking if the join condition is met between the current outer row and each inner row. If a match is found, the combined row is added to the result set. The total number of comparisons is the number of rows in the outer table multiplied by the number of rows in the inner table.

When to use it

A nested loop join is efficient in specific scenarios. First, when one of the tables is very small, making it the outer table results in very few scans of the larger inner table. Second, it can be effective if the inner table is indexed on the join key, which turns the full inner table scan into a much faster index lookup for each outer row. This variant is often called an "index nested loop join".

When not to use it

Avoid this join for two large tables. Its computational complexity is O(M * N), where M and N are the number of rows in the tables. This quadratic scaling means performance degrades catastrophically as tables grow. For example, joining two tables with one million rows each would theoretically require a trillion comparisons, which is computationally infeasible. In these cases, hash joins or sort-merge joins are vastly superior.

One canonical example

A query joins a users table (1 million rows) with a user_roles table (5 rows: 'admin', 'editor', 'viewer'). The database optimizer might choose a nested loop join, making the tiny user_roles table the outer loop. It would read 'admin' and scan users for matches, then read 'editor' and scan users, and so on. This requires only five full scans of the users table, which is often more efficient than other join strategies in this lopsided case.