Sql-server – Why does nested loops join only support left joins

database-internalsjoin;sql server

In Craig Freedman's blog, Nested Loops Join, he explains why the nested loops join cannot support a right outer join:

The problem is that we scan the inner table multiple times – once for
each row of the outer join. We may encounter the same inner rows
multiple times during these multiple scans.
At what point can we conclude that a particular inner row has not or will not join?

Can someone please explain this in a really simple and educational way?

Does it mean that the loop starts with the outer table (R1) and the scans the inner (R2)?

I understand that for a R1 value that doesn't join with R2, it should be replaced with a NULL so the result set becomes (NULL, R2). For me it seems impossible to return an R2 value when R1 does not join, for the reason that it cannot know which R2 value to return. But that's not the way it's explained. Or is it?

SQL Server does in fact optimize (and often replaces) RIGHT JOIN with LEFT JOIN, but the question is to explain why it's technically impossible for a NESTED LOOPS JOIN to use/support RIGHT JOIN logic.

Best Answer

The main issue here is the implementation of an outer join, using nested loops, in a technical way which is opposite to the logical way, where the inner table is accessed through the outer loop and the outer table is accessed through the inner loop.

Given tables A and B, let's implement A LEFT JOIN B.

A
--
1
2

B
_
1
3

First, let's do it in the "natural" way.

We iterate through A.
We access record 1.
We iterate through B.
We find record 1 in B and output 1-1.

We keep iterating through A.
We access record 2.
We iterate through B.
We don't find any match in B.
We output 2-null.

Now, let's do it in the "opposite" way.

We iterate through B.
We access record 1.
We iterate through A.
We find record 1 in A and output 1-1.

We keep iterating through B.
We access record 3.
We iterate through A.
We don't find any match in A.

Now remember that it was A LEFT JOIN B, which means that in addition to 1-1 we should output 2-null.
The problem is that at that point, we have no idea for which records id A we already have a match (1) and for which records we don't (2).

This can actually be solved in various ways e.g. by holding a bit array for table A.
When an A record is being found as a match we mark it in the bit array.
At the end of the nested loops we are going through the bit array and output and output any record that was not marked.
This is obviously more complicated than the "natural" nested loop.

Related Solutions

Db2 – Table orders regarding Nested loop join in DB2

You are right that for Nested Loop Join, the choice of which table is the inner and which the outer table matters for perforamnce.

However, there is nothing in the documentation, in the link you provided, that implies that for a query that has a INNER JOIN b, the table a will be used as inner and b as outer table when the Nested Loop Join algorithm is selected.

Any decent optimizer evaluates many different combinations of algorithms, placing of tables and order of execution, so I don't think there is any difference if you write a INNER JOIN b or b INNER JOIN a, the chosen execution plans should be the same in both cases. If there are exceptions to this, I would expect them to be for very complex queries with tens of joined tables and/or multiple groupings.

Testing and checking the actual execution plans is one way to confirm this. Another would be to analyze the source code of the query optimizer.

The general guidance when writing SQL (in whatever DBMS), is not to care at all about the table join orders. SQL code describes what you want as result, it doesn't tell the DBMS how to get it. And many optimizers now are really smarter and faster than most of us in choosing the best execution plan most of the time.

Unless documentation shows that the optimizer is naive or in a very early version and the way the queries are written, really affects the chosen execution plan.

Or testing/running of a specific query shows that it's slow and some obviously good plan was not chosen. Then you can experiment with hints (if the DBMS has such feature), try rewriting the query in different ways, check if statistics are updated, etc.

Sql-server – How to optimize a query that’s running slow on Nested Loops (Inner Join)

The problem appears to be in this part of the code:

JOIN category_link l on l.sku_id IN (SELECT value FROM #Ids) AND
(
    l.category_id = c4.category_id OR
    l.category_id = c5.category_id
)

or in join conditions is always suspicious. One suggestion is to split this into two joins:

JOIN category_link l1 on l1.sku_id in (SELECT value FROM #Ids) and l1.category_id = cr.category_id
left outer join
category_link l1 on l2.sku_id in (SELECT value FROM #Ids) and l2.category_id = cr.category_id

You then have to modify the rest of the query to handle this . . . coalesce(l1.sku_id, l2.sku_id) for instance in the select clause.

Best Answer

Related Solutions

Db2 – Table orders regarding Nested loop join in DB2

Sql-server – How to optimize a query that’s running slow on Nested Loops (Inner Join)

Related Question