Business Intelligence Blogs

View blogs by industry experts on topics such as SSAS, SSIS, SSRS, Power BI, Performance Tuning, Azure, Big Data and much more! You can also sign up to post your own business intelligence blog.

How Does the Nested Loop Operator Work?

  • 12 March 2014
  • Author: Kathi Kellenberger
  • Number of views: 6279
  • 0 Comments

 

 

 

 

Last week I posted a blog that explained when each type of join operator will be used with an INNER JOIN. This week, I would like to describe how one of the join operators, Nested Loop, works. 

In programming, you can create loops that iterate through a collection or while a condition is true. You can also nest one loop inside another. When this happens, the inner loop will complete one time for every iteration of the outer loop. This is how a nested loop operation works as well.

For the nested loop operator, the outer loop is always the smallest input. The values from the other input, the inner loop, will be searched for each value from the outer loop. Here is a simulation using T-SQL:

SET NOCOUNT ON;
GO

DECLARE @tblOuter TABLE(keycol1 INT);
DECLARE @tblInner TABLE(keycol2 INT);
DECLARE @keycol1 INT;
DECLARE @keycol2 INT;
DECLARE @oCount INT = 1;
DECLARE @iCount INT = 1;
DECLARE @iMax INT;
DECLARE @oMax INT;

INSERT INTO @tblOuter(keycol1)
VALUES(10),(1),(8);

INSERT INTO @tblInner(keycol2)
VALUES(1),(5),(10),(3),(2),(7),(11),(1),(0);

SELECT @iMax = COUNT(*)
FROM @tblInner;
SELECT @oMax = COUNT(*)
FROM @tblOuter;

WHILE @oCount <= @oMax BEGIN
;WITH [outer] AS (
SELECT keycol1,
ROW_NUMBER() OVER(ORDER BY keycol1) AS rowNum
FROM @tblOuter
)
SELECT @keycol1 = keycol1
FROM [outer] WHERE rownum = @oCount;

PRINT 'OUTER ' + CAST(@keycol1 AS VARCHAR);

SET @iCount = 1;

WHILE @iCount <= @iMax BEGIN
;WITH [inner] AS (
SELECT keycol2,
ROW_NUMBER() OVER(ORDER BY keycol2) AS rowNum
FROM @tblinner
)
SELECT @keycol2 = keycol2
FROM [inner] WHERE rownum = @iCount;
IF @keycol1 = @keycol2 BEGIN
PRINT ' **INNER ' + CAST(@keycol2 AS VARCHAR);
END
ELSE BEGIN
PRINT ' INNER ' + CAST(@keycol2 AS VARCHAR);
END;
SET @iCount += 1;
END;
SET @oCount += 1;
END;


This code uses table variables to hold arrays of integers. To loop through the table variables, either a cursor or filtering on a count can be used. Inside the inner loop, the key values are compared. If they are a match, then it is indicated in the results as shown below. When the database engine chooses the nested loop operator, it doesn’t matter if the inputs are sorted by the key, the amount of work done is the same.

The nested loop operator is the simplest of the three and would not be efficient if both inputs were large. Since the optimizer decides to use this operator when it is estimated that one side has less than 10 rows, this is another reason why statistics must be up to date.

Print
Categories: SQL Server
Tags:
Rate this article:
No rating

Please login or register to post comments.