Relationships amoung multiple sets can always be interpreted into multiple relationships of 2 sets – joins. Conceptually, you can have 2 types of joins, Inner Join and Outer Join. Inner joining returns the conjunction of two sets, such as Inner Join, Cross Apply, and Intersect in SQL Server. Outer join will return full set from one or both of the inputs with or without relations between each other such as Left Outer join, Right Outer Join, Full Outer Join, Cross Join, and Outer Apply. In SQL Server, if rows are only returned from one set not the other, it’s called Semi Join, such as Exists, IN (subset). If returning rows do not exist in another set, it’s called Anti Semi Join, such as NOT Exists, Except, Not In (subset). They are all conceptual. Nested loop is a PHYSICAL operator, it supports any of types of joins described above.

use AdventureWorks2008R2

select c.PersonID, o.SalesOrderID
from Sales.Customer c
	inner join Sales.SalesOrderHeader o on o.CustomerID = c.CustomerID
where c.CustomerID = 12345

The plan shows 2 index seeks and one Nested Loop. What happens beind is that Nested Loop asks for a record from the outer input, which is from the customer table in this case. After the record arrives, it asks Index Seek operator over SalesOrderHeader to give it records to inner input with relationship the CustomerID equals to the CustomerID from outer record. Then it performs logical operations. If it’s an Inner join and there is no record returned from the inner input, then nothing will be returned (no return at all); if there is anything in the inner input and it’s also a Inner logic, then combine ( or not cmbine if it’s an semi-join) both inputs to output. The Nested Loop starts over and ask the operator connected to the outer input to give a record, goes through the same process, output, and repeat this again and again, until no more record can be retrieved from the outer input.

Memory consumption for Nested Loop is very low. Conceptually it only need memory for one record in the outer input, one in the inner input, and one record for one output record. If you think memory for both inputs should belong to the memory consumption of two Index Seek operator, then Nested Loop only use memory to host output row. The cost of Nest Loop is linear. The fomular is below (again, These are inferred from the cost of the Query Plan and imagination. No referencing official document. If you know where are the official docs, please share.).

Cost = 4.2 microseconds = 0.0042 milliseconds = 0.0000042 seconds

This means, SQL Server can perform 238,095 Nested Loop per second. The real execution might be faster. Do you think that’s still too low? I cannot tell exactly but I can give you a set of comparative numbers from C# code. I run this code from the same machine that SQL Server runs

DateTime d;
for (int j = 0; j < 20; j++)
{
    d = DateTime.Now;
    for (int i = 0; i < 238095; i++)
    {
    }
    Console.WriteLine((DateTime.Now - d).TotalMilliseconds);
}
Console.WriteLine("done");
Console.ReadKey();

Wow, the code I am using in C# code does simpler things but takes twice of the time of NestedLoop. (I failed to use C++ to write the same code and give you the result since I’ve lost that kind of skills. It will be appreciated if you can post the result from native code.) Please trust the people in SQL Team. They are done very good work. 🙂

In this case, estimated number of rows the Nested Loop will execute is 2.80488. The total cost will be 2.80488 * 0.0000042 = 0.000011780496, which is almost the same as the number showing on Estimated Operator Cost: 0.0000117. We have talked about the cost of Scan and Seek as well as Nested Loop. If we know number of records for each operator, we should be able to calculate the total cost of the query by hand. The fact is that we don’t know the number of the rows. However, how does SQL Server know? How come it picks up a number with fraction, 2.80488, why not 2 or 2.5. I would like to keep this question open and give you the answer on Friday (I asked the same question on one of my presentation, some answered “It’s a bug”. Do you thinks so?). Feel Free to post your comments with answer.