Answered by:
Nested Loop Join
Question
Answers

The "controversial" statement in my post refers to the basic nested loops join algorithm which naively tries to join every outer row to every inner row without using any indexes. In this case, one will find that the cost is indeed proportional to the number of outer rows multiplied by the number of inner rows. A simple experiment involves joining two tables without any indexes using "t1 inner loop join t2" and "t2 inner loop join t1". The join order will make little difference.
Later in the same post, I refer to an "index join" which is a common optimization of nested loops join that uses an index to filter the inner table. In this case, the cost is indeed proportional to the size of the outer table multiplied by the log of the size of the inner table.
More precisely, 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 the inner table, using an index changes the cost from that of a table scan (which is proportional to the size of the table) to that of an index seek (which is proportional to the log of the size of the table).
Perhaps I was a little unclear in my original post. I apologize for any confusion and will attempt to clarify it.
Craig
 Marked as answer by nadirsql Tuesday, July 19, 2011 2:56 PM

> From this I am understanding that if both of the tables are not indexed then cost will be same no matter which of the tables is bigger in size.
Correct. The performance difference will be trivial.
The join order will make little difference.
In other words: in that situation it doesn't matter which table is the outer table.
For the inner table, using an index changes the cost from that of a table scan (which is proportional to the size of the table) to that of an index seek (which is proportional to the log of the size of the table).
>From this I am understanding that it doesnt matter which of the tables should be bigger but one with the index will reduce the cost by log with base 2(size of table). So, if this is the case it will be best if both of those are indexed on the column being joined. Index is seeked using the binary tree,because of that the cost of search will be log of base 2 for the index.
In a Nested Loops join, only the inner table can be seeked (assuming there is a usable index in place). Because the engine needs to know which keys to look up. That is the purpose of the outer table.
So because of that, it does matter which is the inner table. Putting the biggest table as inner table will reduce the cost the most, because of the logarithmic behavior of the index seek that then becomes available. In other words, the outer table should be the smallest table. Craig confirmed what's been discussed so far.
GertJan Marked as answer by nadirsql Tuesday, July 19, 2011 2:56 PM
All replies

It dont have to be smaller.
But the cost of such nested join, if all rows are scanned and indexes are in place is (log (size of outer table)) * (size of inner table) * const
i.e. outer table has 100 and inner table has 10000 rows, cost is:
a) (log 10000) * 100 * x = 100 * 100 * x = 10 000 *x
b) (log 100) * 10000 * x = 100 000 * x
So it will be 10 times slower.

Hi,
Your both questions are contradictory. The reason why inner table has to be smaller is because for each row in the outer table , the inner table is scanned for
the matching rows. Therefore the cost may increase as the number of rows in inner table is increased.
Thanks and regards, Rishabh , Microsoft Community Contributor 

Hi,
Have a look at
http://blogs.msdn.com/b/craigfr/archive/2006/07/26/679319.aspx
Thanks and regards, Rishabh , Microsoft Community Contributor Proposed as answer by Naomi NModerator Friday, July 15, 2011 4:36 AM
 Unproposed as answer by nadirsql Friday, July 15, 2011 1:19 PM

The link says:
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.
He has mentioned that cost is propotional to the multiplication of size of outer table by size of inner table and not what you have mentioned. You have mentioned that the cost is propotional to log(size of outer table)*(size of inner table).
Clarification would be highly appreciated.
Thanks,

I think Piotr's example was right, but the formula wrong.
Assuming proper indexes, each row in the outer table has to be seeked in the inner table. Seeking through an index probably has a cost of LOG(size) * Const, because that is the rate at which the depth of the index grows with the number of rows.
So the formula is probably more along the lines of:
(Size Outer Table) * (LOG(Size Inner Table)) * Const
Here is a table, based on the test script (see all the way down) with the (sampled) run time in milliseconds when joining the indicated number of rows in that particular order.
Inner Table > 1K 10K 100K 1M 10M Outer Table 1K 123 413 3636
10K 153 496 4116
100K 3 20 170 540 3700 1M 3 20 186 560 5680 10M 3 30 60 563So one table has 10 million rows and the other 1 million, then the table above shows that if the 1M table is the inner table it takes 563ms. Otherwise it takes 5680ms.
The test script I used was this:
create table n1(id int primary key,val int) insert into n1 values (1,1) declare @i int set @i=1 while @i<10000000 begin insert into n1 select id+@i,@i from n1 set @i=@i*2 end delete from n1 where id>10000000 dbcc dbreindex (n1,'',100) create table n2(id int primary key,val int) insert into n2 select top 1000 id,val from n1 order by NEWID() dbcc dbreindex (n2,'',100) go declare @dummy int declare @t datetime set @t=CURRENT_TIMESTAMP select @dummy=MIN(n2.val) from n1 inner loop join n2 on n2.id=n1.id option (force order) select DATEDIFF(MS,@t,CURRENT_TIMESTAMP) AS Priming set @t=CURRENT_TIMESTAMP select @dummy=MIN(n1.val) from n2 inner loop join n1 on n1.id=n2.id option (force order) select DATEDIFF(MS,@t,CURRENT_TIMESTAMP) AS SmallOuter set @t=CURRENT_TIMESTAMP select @dummy=MIN(n2.val) from n1 inner loop join n2 on n2.id=n1.id option (force order) select DATEDIFF(MS,@t,CURRENT_TIMESTAMP) AS BigOuter go drop table n2 drop table n1
GertJan 
Thanks for the test!!! Your test proves that if the size of inner table is higher than query will take more time to execute.
But, the formula that is provided by Piotr's make more sense because
Log(OuterTableSize)*InnerTableSize < Log(InnerTableSize)*OuterTableSize if OuterTable is greater than InnerTable.
I am confused on how this formula has been derived.
Craig Freedman's Blog mentions this as a pseudo code for nested loop join:
for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)I think this will result in
Cost = SizeofOuterTable * SizeofInnerTable (But this formula gets failed as per your test).

Hmm. I just double checked to see if I posted the correct labels. I didn't. My apologies.
I reran one test: 1,000,000 rows versus 1,000 rows. The test query returned:
SmallOuter

0
(1 row(s) affected)
BigOuter

410
(1 row(s) affected)
So here is the corrected table.Outer Table > 1K 10K 100K 1M 10M
Inner Table
1K 123 413 3636
10K 153 496 4116
100K 3 20 170 540 3700
1M 3 20 186 560 5680
10M 3 30 60 563Sorry about the confusion. This matches both the theory and the corrected formula. I don't want to blame you, but maybe I got confused by your claim that the inner table should be smallest. That is definitely not the case. The outer table should be smallest. And that is also exactly what the optimizer does (when it is free to choose).
GertJan 
Thanks alot for your double check!!! I am still confused because http://blogs.msdn.com/b/craigfr/archive/2006/07/26/679319.aspx who is also SQL expert is saying "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."
and you are saying:
The outer table should be smallest.
and you have proven your test as well.
I doubt if it depends on case by case basic. Any thoughts on how Craig's blog might have gone wrong. It is hard for me to believe that his blog contains wrong information.
Thanks again!!!

The "controversial" statement in my post refers to the basic nested loops join algorithm which naively tries to join every outer row to every inner row without using any indexes. In this case, one will find that the cost is indeed proportional to the number of outer rows multiplied by the number of inner rows. A simple experiment involves joining two tables without any indexes using "t1 inner loop join t2" and "t2 inner loop join t1". The join order will make little difference.
Later in the same post, I refer to an "index join" which is a common optimization of nested loops join that uses an index to filter the inner table. In this case, the cost is indeed proportional to the size of the outer table multiplied by the log of the size of the inner table.
More precisely, 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 the inner table, using an index changes the cost from that of a table scan (which is proportional to the size of the table) to that of an index seek (which is proportional to the log of the size of the table).
Perhaps I was a little unclear in my original post. I apologize for any confusion and will attempt to clarify it.
Craig
 Marked as answer by nadirsql Tuesday, July 19, 2011 2:56 PM

Thanks alot!!! This helps alot!!!
The "controversial" statement in my post refers to the basic nested loops join algorithm which naively tries to join every outer row to every inner row without using any indexes. In this case, one will find that the cost is indeed proportional to the number of outer rows multiplied by the number of inner rows. A simple experiment involves joining two tables without any indexes using "t1 inner loop join t2" and "t2 inner loop join t1".
> From this I am understanding that if both of the tables are not indexed then cost will be same no matter which of the tables is bigger in size.
The join order will make little difference.
>Why is this? I thought if the cost is propotional to multiplication of both of the tables then join order shouldnt make any difference in the case when both of the tables are not indexed.
Later in the same post, I refer to an "index join" which is a common optimization of nested loops join that uses an index to filter the inner table. In this case, the cost is indeed proportional to the size of the outer table multiplied by the log of the size of the inner table.
More precisely, 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 the inner table, using an index changes the cost from that of a table scan (which is proportional to the size of the table) to that of an index seek (which is proportional to the log of the size of the table).
>From this I am understanding that it doesnt matter which of the tables should be bigger but one with the index will reduce the cost by log with base 2(size of table). So, if this is the case it will be best if both of those are indexed on the column being joined. Index is seeked using the binary tree,because of that the cost of search will be log of base 2 for the index.
Perhaps I was a little unclear in my original post. I apologize for any confusion and will attempt to clarify it.
> I think you are always clear on your post. It is quite new topic for me to understand.
Have I understood it correctly ?
Thanks again!! I really appreciate you response.

> From this I am understanding that if both of the tables are not indexed then cost will be same no matter which of the tables is bigger in size.
Correct. The performance difference will be trivial.
The join order will make little difference.
In other words: in that situation it doesn't matter which table is the outer table.
For the inner table, using an index changes the cost from that of a table scan (which is proportional to the size of the table) to that of an index seek (which is proportional to the log of the size of the table).
>From this I am understanding that it doesnt matter which of the tables should be bigger but one with the index will reduce the cost by log with base 2(size of table). So, if this is the case it will be best if both of those are indexed on the column being joined. Index is seeked using the binary tree,because of that the cost of search will be log of base 2 for the index.
In a Nested Loops join, only the inner table can be seeked (assuming there is a usable index in place). Because the engine needs to know which keys to look up. That is the purpose of the outer table.
So because of that, it does matter which is the inner table. Putting the biggest table as inner table will reduce the cost the most, because of the logarithmic behavior of the index seek that then becomes available. In other words, the outer table should be the smallest table. Craig confirmed what's been discussed so far.
GertJan Marked as answer by nadirsql Tuesday, July 19, 2011 2:56 PM