Execution Plans – Nested Loop

The nested loop is a physical operator used to join 2 or more sets of data when the query optimizer believes this is the best plan for the query.

The following query can be run against the AdventureWorks database:

SELECT cust.CustomerID, soh.SalesOrderID
    FROM Sales.Customer cust
        INNER JOIN Sales.SalesOrderHeader soh
            ON soh.CustomerID = cust.CustomerID
    WHERE cust.CustomerID = 11091

The query joins the Customer table with the Sales Order Header by the CustomerID column (ON soh.CustomerID = cust.CustomerID). This is a Transaction table (Sales Order Header) joined to a lookup table (Customer). You get a Query Plan like the following:

The Clustered Index Seek on the Customer table retrieves the data for a customer based on the WHERE clause looking for CustomerID 11091. Since the rows retrieved from the customer table is smaller than the Sales Order Header, the customer becomes the outer loop of the Nested Join. The inner part of the loop looks for Sales Order Header rows based on the CustomerID 11091.

The Index Seek happens because there is an Index (Non-Clustered) on CustomerID for the SalesOrderHeader table. The SELECT part of the query only needs the SalesOrderID which is part of the Non-Clustered index. The clustered index on the Sales Order Header table includes the SalesOrderID column. All clustered index columns are included in the leaf level of the non-clustered index (idxSalesOrderHeader_CustomerID).

By hovering your mouse over the nested loop, a tool tip gives you more info, including a description of the Nested Loop, Physical and Logical Operation, and much more.

The Actual Number of Rows shows that the Sales Order Header had 28 rows for this customer.

By adding more columns to the SELECT for data from Sales Order Header, like AccountNumber and OrderDate, we get a second Nested Loop.

SELECT cust.CustomerID, soh.SalesOrderID, soh.AccountNumber, soh.OrderDate
    FROM Sales.Customer cust
        INNER JOIN Sales.SalesOrderHeader soh
            ON soh.CustomerID = cust.CustomerID
    WHERE cust.CustomerID = 11091

What happens now, is a second Nested Loop is needed to get the AccountNumber and OrderDate from the Clustered Index of the SalesOrderHeader tables. This is because the Non-clustered index on the CustomerID does not “cover” the columns needed for the SELECT but can be used to Seek the SalesOrderID values needed to satisfy the WHERE on CustomerID 11091. The Key Lookup (Clustered) is OK because it is not a scan.

The query can be improved by adding a Covering Index. The following index will use the INCLUDE clause of the CREATE INDEX statement to include the AccountNumber and OrderDate in the leaf level of the index and not the tree level.

    CREATE NONCLUSTERED INDEX idxSalesOrderHeader_CustomerID_IncludeAccountNumberOrderDate
        ON [Sales].[SalesOrderHeader] ([CustomerID])
        INCLUDE (AccountNumber, OrderDate)
GO

The second Nested Loop (Cost 93%) of the query will be removed.

 

The Index Seek is now covering the SELECT for SalesOrderHeader data.

We have shown here a basic explanation and example of a Nested Loop along with some information on Cluster and Non-Cluster index Seeks as well as a Key Lookup.

Thomas