This post is the first in a short series about physical join types. What do I mean by physical join types? What we normally consider to be a join – INNER / [LEFT|RIGHT] OUTER / FULL join are logical join types, they are the joins we use to describe the query results in our declarative T-SQL queries. A physical join is the type of join that will actually be executed by the query execution engine and SQL Server exposes these to us in execution plans. Let’s have a look at them and understand a bit more about them.

We’ll look at some abstract examples showing how a human may perform such a task and then we’ll look at it in action in SQL Server.

The Algorithm

Nested Loops are in my opinion, the simplest physical join type to understand. Let’s forget about database management systems for a second and consider how we would tackle some joining tasks as human beings.

Let’s say we have some index cards with a single number written on each and we have two piles – Pile A has 3 cards, Pile B has 100,000 cards and we want to find all of the cards where the number on the card is in both piles (in database terms – an inner join) how might we do this?

Below is a representation of the cards:

The way a nested loop join works is for each item in one set, we check the value against every value in the other set and return the matches (though note if the sets are sorted we don’t need to compare against every value – more on that later) In nested loop terminology, the set we iterate over (Pile A) is called the outer input and the set we probe (Pile B) is called the inner input.

In our card example, a person has passed us the cards and informed us that both sets are unsorted, to find the matching cards, we’d start with the card 17 – the first card in Pile A which is the smaller of the two piles and start checking one by one against each card in Pile B to see if the values match, when we have checked every card in Pile B against the first card in Pile A, we move to the next card in Pile A and repeat, the table below visualises this

There are a number of factors that can affect how much work this is:

• Are the sets sorted?
• What size are the sets?
• Are the values duplicated or unique?

Let’s consider how these variables affect the amount of work required to perform the nested loops join

If we were to sort Pile B, it would look like this

Now if we were to repeat the search process, we start with the first card in Pile A again (17) and once we find card 17 in Pile B we know that there are no further matches due to being sorted. We look at the next card and see it is not 17 and so we have found all the matches for 17 so we move onto the next card in Pile A. We see that the first card is 8 and so there can’t be any number 1s in pile B so we move to the next card in Pile A. Below shows this process tabulated

Because we have sorted Pile B, the task is much easier.

What if we went back to the unsorted Pile B but we sorted Pile A?

This doesn’t actually help us much – we will still have to scan the entirety of Pile B to find the cards with a number 1.

Now what if Pile B had unsorted cards numbered 1-100,000 but each number was not unique (and therefore we actually have more than 100,000 cards)

Whilst we have slightly more cards than before, the process is still the same – for each card in Pile A, we need to look through every card in Pile B to see if it has the same number.

If we were to now sort Pile B with the duplicates

Again, not much changes from when we had Pile B sorted but without duplicates – the sorting means we know once we have read all of a particular number that we are looking for in Pile B , that there will be no more.

One other case for using a nested loop join is when we want to use a range predicate – rather than us just looking for cards in Pile B that are also in Pile A, if we wanted to find all cards in Pile B with a value higher than each card in Pile A, we can use a nested loop for that too.

So now we know how a nested loop join works, when is it efficient to use one?

If we were to have two large Piles, a nested loop join would be a lot of work. if we have one small pile, a nested loop join may be efficient if a larger pile is sorted but if the larger pile is not sorted, it may not be efficient.

Nested Loop – In Action

Let’s see nested loops in action in SQL Server, to do this I’ll setup some test tables. I am using SQL Server 2022 so can leverage GENERATE_SERIES for this.

CREATE DATABASE JoinTest;
GO

ALTER DATABASE JoinTest SET COMPATIBILITY_LEVEL = 160;
GO

USE JoinTest;

CREATE TABLE dbo.TableA_Small_Unsorted_NonUnique
(
	Id INT
);
INSERT INTO dbo.TableA_Small_Unsorted_NonUnique
VALUES
	(17),
	(1),
	(10);

CREATE TABLE dbo.TableB_Large_Unsorted_NonUnique
(
	Id INT
);

INSERT INTO dbo.TableB_Large_Unsorted_NonUnique
SELECT * FROM GENERATE_SERIES(1,100000) ORDER BY NEWID();

Here we have something that represents our card example above – a small table with three values and a large table with 100,000 values.

Now let’s write the SQL to get the results we want, this is the search we were doing above

SELECT	*
FROM	dbo.TableA_Small_Unsorted_NonUnique a
		JOIN dbo.TableB_Large_Unsorted_NonUnique b
			ON a.id = b.id;

If we look at the execution plan, we can see SQL Server did not perform a nested loop join at all – it chose a hash match (we’ll talk about what that is in a later post)

The statistics IO output shows

Table 'Workfile'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table 'TableB_Large_Unsorted_NonUnique'. Scan count 1, logical reads 161, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table 'TableA_Small_Unsorted_NonUnique'. Scan count 1, logical reads 1, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

I can force the optimiser to do a nested loop, purely to understand why it chose not to do one. I am only doing this to understand why the optimiser didn’t choose to do a nested loop join – forcing physical joins by disabling optimiser features is not something you would generally want to do in production unless you have tested some specific use case for it.

SELECT	*
FROM	dbo.TableA_Small_Unsorted_NonUnique a
		INNER LOOP JOIN dbo.TableB_Large_Unsorted_NonUnique b
			ON a.id = b.id
OPTION (NO_PERFORMANCE_SPOOL);

Table 'TableB_Large_Unsorted_NonUnique'. Scan count 1, logical reads 483, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table 'TableA_Small_Unsorted_NonUnique'. Scan count 1, logical reads 1, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

The cost that the optimiser estimated for the hash match plan and nested loop plans respectively are below. This tooltip is seen when you hover over the root node of the execution plan and we can see that Estimated subtree cost of the nested loop plan is higher than the hash match. As SQL Server uses a cost based optimiser, it chooses the cheaper option, hence why it chose the hash match over the nested loop

What if TableB was sorted? Creating a clustered index physically stores the table in order of the key

CREATE TABLE dbo.TableB_Large_Sorted_NonUnique
(
	Id INT
);
CREATE CLUSTERED INDEX IX_Id ON dbo.TableB_Large_Sorted_NonUnique (Id);

INSERT INTO dbo.TableB_Large_Sorted_NonUnique
SELECT * FROM GENERATE_SERIES(1,100000) ORDER BY NEWID();

Now SQL Server decides to do the nested loop and we can see the index seek on TableB in action.

What if we had an unsorted Table B again but forced uniqueness

CREATE TABLE dbo.TableB_Large_Unsorted_Unique
(
	Id INT UNIQUE
);

INSERT INTO dbo.TableB_Large_Unsorted_Unique
SELECT * FROM GENERATE_SERIES(1,100000) ORDER BY NEWID();

SELECT	*
FROM	dbo.TableA_Small_Unsorted_NonUnique a
		JOIN dbo.TableB_Large_UnSorted_Unique b
			ON a.id = b.id;

This time, SQL Server decides it is efficient to use the nested loop join

Conclusion

We have looked at what physical join operators are vs logical joins and understood the way the nested loop join works, we also looked at some examples.

Nested loop joins are most efficient when the outer input is small and the inner input is indexed. When SQL Server can seek into the inner table for each outer row, the number of reads is proportional to the size of the outer input multiplied by the seek cost, which can be very low. When the inner table must be fully scanned for each outer row, the cost scales greatly and a hash match or merge join is likely to be cheaper.

In the upcoming posts, we’ll look at the other physical join types – hash match and merge join.

References / Further Reading

Bert Wagner – Visualizing Nested Loop Joins

David J. DeWitt – SQL Query Optimization: Why is it so Hard to Get Right?

dualcoredba – Physical Joins – Hash Match

dualcoredba – Physical Joins – Merge Join

Hugo Kornelis – Nested Loops