none
Nested Loop Join

    Question

  • Why inner table needs to be of smaller size than outer table for nested loop join ? What would happen if size of outer table is greater than inner table ?

    Thanks,

    Friday, July 15, 2011 4:07 AM

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
    Monday, July 18, 2011 2:35 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.


    Gert-Jan
    • Marked as answer by nadirsql Tuesday, July 19, 2011 2:56 PM
    Monday, July 18, 2011 10:05 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.

    Friday, July 15, 2011 4:13 AM
  • 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
    Friday, July 15, 2011 4:13 AM
  • How is the following formula derived? Is there any documentation ?

    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

    Thanks!!

    Friday, July 15, 2011 4:25 AM
  • 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
    Friday, July 15, 2011 4:28 AM
  • 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,

    Friday, July 15, 2011 1:24 PM
  • 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 563

    So 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
    


    Gert-Jan
    Friday, July 15, 2011 3:07 PM
  • 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).

    Friday, July 15, 2011 4:32 PM
  • Hmm. I just double checked to see if I posted the correct labels. I didn't. My apologies.

    I re-ran 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 563

    Sorry 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).


    Gert-Jan
    Friday, July 15, 2011 7:12 PM
  • 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!!!

    Saturday, July 16, 2011 3:31 PM
  • 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
    Monday, July 18, 2011 2:35 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.

    Monday, July 18, 2011 8:07 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.


    Gert-Jan
    • Marked as answer by nadirsql Tuesday, July 19, 2011 2:56 PM
    Monday, July 18, 2011 10:05 PM