通过

Nested Loops Join

  • 项目

SQL Server supports three physical join operators: nested loops join, merge join, and hash join.  In this post, I’ll describe nested loops join (or NL join for short).

The basic algorithm

In its simplest form, a nested loops join compares each row from one table (known as the outer table) to each row from the other table (known as the inner table) looking for rows that satisfy the join predicate.  (Note that the terms “inner” and “outer” are overloaded; their meaning must be inferred from context.  “Inner table” and “outer table” refer to the inputs to the join.  “Inner join” and “outer join” refer to the logical operations.)

We can express the algorithm in pseudo-code as:

for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)

It’s the nesting of the for loops in this algorithm that gives nested loops join its name.

The total number of rows compared and, thus, the cost of this algorithm is proportional to the size of the outer table multiplied by the size of the inner table.  Since this cost grows quickly as the size of the input tables grow, in practice we try to minimize the cost by reducing the number of inner rows that we must consider for each outer row.

Update 7/18/2011: The cost that I describe above refers to a naive nested loops join in which we have no indexes and in which every outer row is compared to every inner row.  Below, I describe how SQL Server can use an index on the inner table to reduce this cost so that it is proportional to the size of the outer table multiplied by the log of the size of the inner table.  A more precise statement is that for any nested loops join, the cost is proportional to the cost of producing the outer rows multipled by the cost of producing the inner rows for each outer row.

For example, using the same schema from my prior post:

create table Customers (Cust_Id int, Cust_Name varchar(10))

insert Customers values (1, 'Craig')

insert Customers values (2, 'John Doe')

insert Customers values (3, 'Jane Doe')

create table Sales (Cust_Id int, Item varchar(10))

insert Sales values (2, 'Camera')

insert Sales values (3, 'Computer')

insert Sales values (3, 'Monitor')

insert Sales values (4, 'Printer')

Consider this query:

select *

from Sales S inner join Customers C

on S.Cust_Id = C.Cust_Id

option(loop join)

I’ve added a “loop join” hint to force the optimizer to use a nested loops join.  We get this plan which I captured by running the query with “set statistics profile on”:

Rows

Executes

3

1

  |--Nested Loops(Inner Join, WHERE:([C].[Cust_Id]=[S].[Cust_Id]))

3

1

       |--Table Scan(OBJECT:([Customers] AS [C]))

12

3

       |--Table Scan(OBJECT:([Sales] AS [S]))

The outer table in this plan is Customers while the inner table is Sales.  Thus, we begin by scanning the Customers table.  We take one customer at a time and, for each customer, we scan the Sales table.  Since there are 3 customers, we execute the scan of the Sales table 3 times.  Each scan of the Sales table returns 4 rows.  We compare each sale to the current customer and evaluate whether the two rows have the same Cust_Id.  If they do, we return the pair of rows.  We have 3 customers and 4 sales so we perform this comparison a total of 3*4 or 12 times.  Only 3 of these comparisons result in a match.

Now consider what happens if we create an index on Sales:

create clustered index CI on Sales(Cust_Id)

Now we get this plan:

Rows

Executes

3

1

  |--Nested Loops(Inner Join, OUTER REFERENCES:([C].[Cust_Id]))

3

1

    |--Table Scan(OBJECT:([Customers] AS [C]))

3

3

       |--Clustered Index Seek(OBJECT:([Sales].[CI] AS [S]), SEEK:([S].[Cust_Id]=[C].[Cust_Id]) ORDERED FORWARD)

This time, instead of doing a table scan of Sales, we do an index seek.  We still do the index seek 3 times – once for each customer, but each index seek returns only those rows that match the current Cust_Id and qualify for the join predicate.  Thus, the seek returns a total of only 3 rows as compared to the 12 rows returned by the table scan.

Notice that the index seek depends on C.CustId which comes from the outer table of the join – the table scan of Customers.  Each time we execute the index seek (recall that we execute it 3 times – once for each customer), C.CustId has a different value.  We refer to C.CustId as a “correlated parameter.”  If a nested loops join has correlated parameters, we output them in the showplan as “OUTER REFERENCES.”  We often refer to this type of nested loops join where we have an index seek that depends on a correlated parameter as an “index join.”  This is a common scenario.

What types of join predicates does the nested loops join support?

The nested loops join supports all join predicate including equijoin (equality) predicates and inequality predicates.

Which logical join operators does the nested loops join support?

The nested loops join supports the following logical join operators:

  • Inner join
  • Left outer join
  • Cross join
  • Cross apply and outer apply
  • Left semi-join and left anti-semi-join

The nested loops join does not support the following logical join operators:

  • Right and full outer join
  • Right semi-join and right anti-semi-join

Why does the nested loops join only support left joins?

We can easily extend the nested loops join algorithm to support left outer and semi-joins.  For instance, here is pseudo-code for left outer join.  We can write similar pseudo-code for left semi-join and left anti-semi-join.

for each row R1 in the outer table
begin
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
if R1 did not join
return (R1, NULL)
end

This algorithm keeps track of whether we joined a particular outer row.  If after exhausting all inner rows, we find that a particular inner row did not join, we output it as a NULL extended row.
 
Now consider how we might support right outer join.  In this case, we want to return pairs (R1, R2) for rows that join and pairs (NULL, R2) for rows of the inner table that do not 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?  Moreover, if we are using an index join, we might not encounter some inner rows at all.  Yet these rows should also be returned for an outer join.

Fortunately, since right outer join commutes into left outer join and right semi-join commutes into left semi-join, we can use the nested loops join for right outer and semi-joins.  However, while these transformations are valid, they may affect performance.   For example, the join “Customer left outer join Sales” using the above schema with the clustered index on Sales, could use an index seek on Sales just as in the inner join example.  On the other hand, the join “Customer right outer join Sales” can be transformed into “Sales left outer join Customer,” but now we need an index on Customer.

What about full outer joins?

The nested loops join cannot directly support full outer join.  However, we can transform “T1 full outer join T2” into “T1 left outer join T2 UNION T2 left anti-semi-join T1.”  Basically, this transforms the full outer join into a left outer join – which includes all pairs of rows from T1 and T2 that join and all rows of T1 that do not join – then adds back the rows of T2 that do not join using an anti-semi-join.  Here is the transformation in action:

select *

from Customers C full outer join Sales S

on C.Cust_Id = S.Cust_Id

Rows

Executes

5

1

  |--Concatenation

4

1

       |--Nested Loops(Left Outer Join, WHERE:([C].[Cust_Id]=[S].[Cust_Id]))

3

1

       | |--Table Scan(OBJECT:([Customers] AS [C]))

12

3

       | |--Clustered Index Scan(OBJECT:([Sales].[Sales_ci] AS [S]))

0

0

       |--Compute Scalar(DEFINE:([C].[Cust_Id]=NULL, [C].[Cust_Name]=NULL))

1

1

            |--Nested Loops(Left Anti Semi Join, OUTER REFERENCES:([S].[Cust_Id]))

4

1

                 |--Clustered Index Scan(OBJECT:([Sales].[Sales_ci] AS [S]))

3

4

                 |--Top(TOP EXPRESSION:((1)))

3

4

                      |--Table Scan(OBJECT:([Customers] AS [C]), WHERE:([C].[Cust_Id]=[S].[Cust_Id]))

Note:  In the above example, the optimizer chooses a clustered index scan even though it could use a seek.  This is merely a costing decision.  The table is so small (its fits on one
page) that there is really no difference between the scan and seek performance.

Is NL join good or bad?

Neither actually.  There is no “best” join algorithm and no join algorithm is inherently good or bad.  Each join algorithm performs well in the right circumstances and poorly in the wrong circumstances.  Because the complexity of a nested loops join is proportional to the size of the outer input multiplied by the size of the inner input, a nested loops join generally performs best for relatively small input sets.  The inner input need not be small, but, if it is large, it helps to include an index on a highly selective join key.

In some cases, a nested loops join is the only join algorithm that SQL Server can use.  SQL Server must use a nested loops join for cross join as well as some complex cross applies and outer applies.  Moreover, with one exception (for full outer join), a nested loops join is the only join algorithm that SQL Server can use without at least one equijoin predicate.

Coming up next …

In my next post, I’ll continue this discussion of physical join operators by describing how merge join works.

Comments

  • Anonymous
    August 09, 2006
    Great info, Craig -- I don't think I've seen this common operator dissected so thoroughly anywhere else.  Thanks!

  • Anonymous
    August 13, 2006
    The section 'What about full outer joins' was fascinating. Can you expand on what that query plan is showing. I presume the Concatenation operator implements the Union with lines 2-4 being the first query and lines 5-9 being the second query. What's the Compute Scalar for? and the TOP(Expression)?

    Also you mention in the note about the query plan using a clustered index scan instead of a seek. There are 2 clustered index scans in the plan and I presume you mean the first one - it wouldn't make sense to have an index seek for the outer table (or set) of an NL join.

  • Anonymous
    August 14, 2006
    Your analysis is correct.  The concatenation is the union, the red lines (2-4) are the left outer join, and the green lines (5-9) are the semi-join to complete the full outer join.

    Compute scalar simply computes an expression.  In this case it computes NULL constants for the customer columns.  This is needed since semi-joins do not produce output values for the inner table (the customer table in this case).  Recall that the semi-join is just checking for existence; it does not actually match any particular row.

    The top is an unnecessary optimization to stop the table scan from producing more than one row.  Again, the semi-join is just checking for existence so a single match is all that we need.  I say "unnecessary" because the semi-join would stop after a single match even without the top.

    You are also correct, that the clustered index scan that I referenced is the inner one.  Sorry for the ambiguity.

  • Anonymous
    August 16, 2006
    CraigFr has a great series of posts in his blog describing the difference between the various logical...

  • Anonymous
    August 16, 2006
    The comment has been removed

  • Anonymous
    September 12, 2006
    Every once in awhile, I get an opportunity to look around for new and interesting things to read. ...

  • Anonymous
    September 25, 2006
    Here’s an example of the classic scenario that is usually used to introduce the concept of a deadlock:...

  • Anonymous
    November 03, 2006
    Here’s an example of the classic scenario that is usually used to introduce the concept of a deadlock

  • Anonymous
    November 08, 2006
    SQL Server parallelizes a nested loops join by distributing the outer rows (i.e., the rows from the first

  • Anonymous
    May 02, 2007
    Last week I looked at how concurrent updates may cause a scan running at read committed isolation level

  • Anonymous
    June 14, 2007
    The comment has been removed

  • Anonymous
    July 03, 2007
    I'm not sure I understand your question.  I would suggest posting your question if possible along with an example repro and query plan to the SQL Server Database Engine forum at: http://forums.microsoft.com/MSDN/ShowForum.aspx?ForumID=93&SiteID=1.

  • Anonymous
    August 07, 2007
    Since the beginning of learning SQL Server I'm pretty much confused with JOIN conditions that defines

  • Anonymous
    December 30, 2007
    The comment has been removed

  • Anonymous
    March 31, 2008
    In my previous post , I discussed the ROW_NUMBER ranking function which was introduced in SQL Server

  • Anonymous
    April 28, 2008
    Let's take a look at a simple query: CREATE TABLE T1 (A INT, B CHAR(8)) INSERT T1 VALUES (0, '0') INSERT

  • Anonymous
    October 07, 2008
    In my last post , I explained the importance of asynchronous I/O and described how SQL Server uses sequential

  • Anonymous
    October 30, 2008
    SQL Server includes two DMVs - sys.dm_db_index_usage_stats and sys.dm_db_index_operational_stats - that

  • Anonymous
    February 06, 2011
    Hi, if we have  in top input a simple index seek, and the bottom input we have seeks,other joins, etc... means that all this wiil be executed row per row from top input ?

  • Anonymous
    February 06, 2011
    Yes, in showplan, the "top" input is the outer input and the "bottom" input is the inner input and, thus, the bottom input is executed once for every row from the top input.  In some cases, the optimizer may add a spool operator to the inner input to reduce the cost. HTH Craig

  • Anonymous
    February 20, 2012
    I want C# code to handle nested loop join with sql server database

  • Anonymous
    February 21, 2012
    Hi Vaishali, I'm not sure I understand your question.  You can use C# and ADO.NET to access SQL Server.  Whether a particular query uses a nested loops join depends on the plan chosen by the optimizer and is not affected by the particular language or client API used to access to the server.  See msdn.microsoft.com/.../dw70f090.aspx for some examples of how to access SQL Server using C# and ADO.NET. HTH Craig

  • Anonymous
    October 05, 2012
    I have (and re-read!) blog posts, articles, MSDN entries and many many forum discussions on Joins and I must say yours is by far the best I've read! Thanks for taking the time to do this.

  • Anonymous
    June 13, 2014
    "Why does the nested loops join only support left joins? We can easily extend the nested loops join algorithm to support left outer and semi-joins.  For instance, here is pseudo-code for left outer join.  We can write similar pseudo-code for left semi-join and left anti-semi-join. for each row R1 in the outer table    begin        for each row R2 in the inner table            if R1 joins with R2                return (R1, R2)        if R1 did not join            return (R1, NULL)    end" The part in Red is not correct. If this is a Left Join and R2 is the inner table, then If R1 did not join, it should return (R2, NULL).. Is'nt it??

  • Anonymous
    June 16, 2014
    The pseudo-code is correct as written.  It implements "R1 left outer join R2".  Since a left outer join preserves the rows from the left or outer input (in this case R1), if a row R1 does not join with any row of R2, it is returned as (R1, NULL). You may find the outer join examples from this post helpful: blogs.msdn.com/.../671712.aspx Thanks, Craig

  • Anonymous
    June 18, 2014
    Thank you Craig for the explanation. From what I was reading, I understood the pseudo code to be implemented as  " R2 left outer join R1" and so I got confused. I was under the impression that when you use the term "Inner table" you are referring to the table on the Left Hand Side of any Join and when you use the term "Outer table" , you are referring to the table on the Right Hand Side of any Join... So just to clarify one last time, in case of   -- "R1 Left Outer Join R2" ...Would R1 be the inner table or outer table?... Per my understanding its the Inner Table?

  • Anonymous
    June 18, 2014
    Or is it that there is no hard and fast rule about which is outer Vs which is inner...but just that... the table with lesser number of records is considered as Outer  (like in the eg of Customers and Sales) ...because lesser the number of records, lesser the number of iterations?... If you could kindly clarify this, I would really appreciate it. I'd like to also add that I absolutely enjoy reading your blogs and careful explanations. I have been learning a lot. So, Thank you.

  • Anonymous
    June 19, 2014
    To avoid confusion, I try to avoid using the terms outer and inner except when referring to a physical nested loops join operator.  For a nested loops join operator, the outer table is the left input and the inner table is the right input.  The terms derive from the algorithm -- the outer loop and the inner loop. Given "R1 left outer join R2" or "R2 right outer join R1" implemented with a nested loops join, R1 would be the outer table and R2 would be the inner table. Thanks, Craig

  • Anonymous
    June 19, 2014
    Great!... Thank you very much for your time