{"id":1471,"date":"2012-12-21T10:00:02","date_gmt":"2012-12-21T15:00:02","guid":{"rendered":"http:\/\/sqlity.net\/en\/?p=1471"},"modified":"2014-11-13T13:50:34","modified_gmt":"2014-11-13T18:50:34","slug":"a-join-a-day-the-nested-loops-join","status":"publish","type":"post","link":"https:\/\/sqlity.net\/en\/1471\/a-join-a-day-the-nested-loops-join\/","title":{"rendered":"A Join A Day \u2013 The Nested Loops Join"},"content":{"rendered":"
\n

Introduction<\/h3>\n

\nThis is the twenty-first post in my A Join A Day<\/a> series about SQL Server Joins. Make sure to let me know how I am doing or ask your burning join related questions by leaving a comment below.\n<\/p>\n

\nOver the next few days we are going to look at the join algorithms in a little more detail. There are three join algorithms that are commonly implemented by modern database management systems. They are: Nested Loops Join, Hash Join and Sort Merge Join. Unsurprisingly, SQL Server also implements those three algorithms.\n<\/p>\n

\nToday's topic is the Loop Join – probably the simplest of them all.\n<\/p>\n

The Nested Loops Join<\/h3>\n

\n\"nested<\/a>\n<\/p>\n

\nThe Nested Loop Algorithm gets its name from the fact that it literally executes two nested loops. The outer loop steps through the rows of the left side. For each row the inner loop then steps through all rows of the right side to find all matches. That means the entire right side input is accessed as many times as there are rows on the left. To demonstrate that, let's create these two tables:\n<\/p>\n

\n[sql]\nIF OBJECT_ID('dbo.Tbl10') IS NOT NULL DROP TABLE dbo.Tbl10;
\nCREATE TABLE dbo.Tbl10(
\n Id INT IDENTITY(1,1),
\n Val INT,
\n Fill CHAR(7000) NOT NULL DEFAULT REPLICATE('Fill',1750)
\n);<\/p>\n

IF OBJECT_ID('dbo.Tbl100') IS NOT NULL DROP TABLE dbo.Tbl100;
\nCREATE TABLE dbo.Tbl100(
\n Id INT IDENTITY(1,1),
\n Val INT,
\n Fill CHAR(7000) NOT NULL DEFAULT REPLICATE('Fill',1750)
\n);<\/p>\n

INSERT INTO dbo.Tbl10(Val)
\nSELECT TOP(10) 1+ROW_NUMBER()OVER(ORDER BY (SELECT 1))%100
\nFROM sys.all_columns A, sys.all_columns B, sys.all_columns C;<\/p>\n

SELECT index_type_desc, alloc_unit_type_desc, index_depth, page_count, record_count
\nFROM sys.dm_db_index_physical_stats(DB_ID(),OBJECT_ID('dbo.Tbl10'),NULL,NULL,'SAMPLED');<\/p>\n

INSERT INTO dbo.Tbl100(Val)
\nSELECT TOP(100) ROW_NUMBER()OVER(ORDER BY (SELECT 1))
\nFROM sys.all_columns A, sys.all_columns B, sys.all_columns C;<\/p>\n

SELECT index_type_desc, alloc_unit_type_desc, index_depth, page_count, record_count
\nFROM sys.dm_db_index_physical_stats(DB_ID(),OBJECT_ID('dbo.Tbl100'),NULL,NULL,'SAMPLED');
\n[\/sql]\n<\/p><\/div>\n

\nAfter executing this, the dbo.Tbl100<\/span> table contains 100 records. The dbo.Tbl10<\/span> contains 10 records. Both tables are designed so that each record takes up an entire storage page of 8192 bytes. The two selects against the sys.dm_db_index_physical_stats<\/span> show the amount of pages used by and the amount of records stored in each table:\n<\/p>\n

\n\"create<\/a>\n<\/p>\n

\nThe query also shows that both tables do not have a clustered index. Now let's run the following query:\n<\/p>\n

\n[sql]\nSET STATISTICS IO ON;
\nGO
\nSELECT *
\nFROM dbo.Tbl100 A
\nINNER LOOP JOIN dbo.Tbl10 B
\nON A.Val = B.Val;
\nGO
\nSET STATISTICS IO OFF;
\n[\/sql]\n<\/div>\n

\nThe query returns ten records. Because we used the LOOP<\/span> hint, the Nested Loops Join algorithm was used:\n<\/p>\n

\n\"execution<\/a>\n<\/p>\n

\nYou can see in the tooltip that the table scan of dbo.Tbl10<\/span> was executed 100 times, once for each row in dbo.Tbl100<\/span>. Looking at the output of SET STATISTICS IO ON;<\/span> confirms that:\n<\/p>\n

\n[sourcecode]\nTable 'Tbl10'. Scan count 1, logical reads 1000, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
\nTable 'Tbl100'. Scan count 1, logical reads 100, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
\n[\/sourcecode]\n<\/div>\n

\nThe query executed 1,000 reads against the 10 page table, so the entire table was read 100 times.\n<\/p>\n

\nThis sounds pretty bad. So why would you ever want to use the Nested Loops Join algorithm? There are a quite a few advantages. See the Strengths and Weaknesses section at the end of this article for a detailed list.\n<\/p>\n

\nThe biggest advantage is probably that there is no setup work required. If the tables are small enough, the nested join can be done processing, before the other algorithms would have even started returning results.\n<\/p>\n

\nYou also need to keep in mind that the above example was the worst case scenario of joining two heaps with no usable indexes. So, let's see what happens if we add a clustered index:\n<\/p>\n

\n[sql]\nCREATE UNIQUE CLUSTERED INDEX [dbo.Tbl10(Val, Id) CL] ON dbo.Tbl10(Val, Id);
\n[\/sql]\n<\/div>\n

\nNow sys.dm_db_index_physical_stats<\/span> shows an index depth of two:\n<\/p>\n

\n\"create<\/a>\n<\/p>\n

\nThe index depth is what determines how many reads are required to do a seek in that index. If we rerun the above join query again the execution plan will, as expected, contain a seek of dbo.Tbl10<\/span>:\n<\/p>\n

\n\"nested<\/a>\n<\/p>\n

\nThis execution plan now is not quite a nested loop anymore. SQL Server still loops through the left input one row at a time. But it does not loop through the second input anymore. Instead it executes a direct seek to read just the row requested. However, the seek operation is still executed 100 times. So we can expect 200 reads to happen against that table. Let's check the SET STATISTICS IO ON;<\/span> output:\n<\/p>\n

\n[sourcecode]\nTable 'Tbl10'. Scan count 100, logical reads 227, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
\nTable 'Tbl100'. Scan count 1, logical reads 100, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
\n[\/sourcecode]\n<\/div>\n

\nIt shows 227 reads. There are just a few reads more than we expected. Those additional reads happen because of additional meta-data pages like the IAM page that need to be accessed.\n<\/p>\n

\nWith an appropriate index the Nested Loops Join algorithm is not that bad anymore. While the savings in this case weren't great, you need to keep in mind, that the index depth growth very slowly as new rows are added to the table. Even in this badly designed example table you can store several million rows before a seek takes more than four reads.\n<\/p>\n

\nThis example showed another advantage of the Nested Loops Join operator: It can make use of an index on the right side input. With the exception of a few edge cases, the other two algorithms cannot utilize such an index.\n<\/p>\n

\nIf you are following along with the examples, use this statement to remove the index when you are done:\n<\/p>\n

\n[sql]\nDROP INDEX dbo.Tbl10.[dbo.Tbl10(Val, Id) CL];
\n[\/sql]\n<\/div>\n

Loop Join Strengths and Weaknesses<\/h3>\n

\nThe Loop Join operator has the following strength and weaknesses:<\/p>\n