In the previous post in this series, we looked at the nested loop operator which we saw was useful when there is a small set data and a second set of sorted data. In this post, we’ll look at what is often considered the workhorse of physical join operators – the hash join. The hash join is a physical join implemented by the query optimizer to satisfy a logical join we have specified in our declarative SQL query.

The Algorithm

Like last time, let’s say we have some index cards with numbers on and we have two piles – Pile A has 3 cards, Pile B has 100,000 cards and we want to pick out all of the numbers that are in both piles (in database terms – an inner join) how might we do this?

Below is a simple representation of the cards:

The way a hash join works is that it looks through the data in the smallest set (in terms of row count) and places the distinct values into “hash buckets” and then works through the larger set, and for each value where a bucket has been created writes the matches into the corresponding bucket.

Due to the fact values are placed into buckets and a bucket represents one value, a hash join only supports equality predicates – range and inequality must use one of the other join types.

Working through the card example, we want to return the cards that have numeric values that are in both piles, to achieve this, using hash join, we first implement the “build phase” of the algorithm. In this build phase, we read the cards in the smaller of the two sets and create a new pile for each distinct value

So after the build phase we end up with this:

We then execute the “probe phase” which is where we run through each card in Pile B and if we have created a bucket for the value on the card, we throw the card from Pile B in that bucket and that gives us our matches.

This is a simplified “humanised” description of how the join is implemented, there are other things at play such as hashing functions and hash collisions but the aim here is a simplified overview of the difference between this join and the others.

There are some costs to hash joins – whereas in my simple card example we are actually moving the cards into buckets, in a database, nothing is physically moved but the buckets are created in memory, it would be like us using a notepad to solve the problem above. In some cases, the hash join can spill to disk (tempdb in SQL Server’s case) if sufficient memory isn’t available. The hashing of values also carries a CPU cost.

Hash Join vs Nested Loop

So now we know how hash joins work, let’s compare them to nested loops, why would we use hash joins?

  • If the data is unsorted, it is usually more efficient to use a hash join vs a nested loop join
  • If both sets are large, a nested loop join would be extremely inefficient compared to a hash join

Hash Join in Action

Let’s create some tables. I’ll create a small table with three rows and a large table with 100,000 rows, both are unsorted (no indexes)

CREATE DATABASE JoinTest;
GO

ALTER DATABASE JoinTest SET COMPATIBILITY_LEVEL = 160;
GO

USE JoinTest;

CREATE TABLE dbo.TableA_Small
(
	Id INT
);

INSERT INTO dbo.TableA_Small
VALUES
	(17),
	(1),
	(10);

CREATE TABLE dbo.TableB_Large
(
	Id INT
);

INSERT INTO dbo.TableB_Large
SELECT	ABS(CHECKSUM(NewId())) % 100000
FROM	GENERATE_SERIES(1,100000);

INSERT INTO dbo.TableB_Large VALUES (1); /* ensure we have a least one row returned! */

Now lets join the two and view the execution plan, the STATISTICS IO, TIME output and see what the cost of the query from the SELECT tooltip is

SELECT	*
FROM	dbo.TableA_Small a
		JOIN dbo.TableB_Large b
			ON a.Id = b.Id;
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'. 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'. 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.

 SQL Server Execution Times:
   CPU time = 16 ms,  elapsed time = 23 ms.

We can see that the hash join is used (known as a hash match in the execution plan) and that TableB was read in its entirety.

Now if we sort TableB by creating a clustered index:

CREATE CLUSTERED INDEX IX_Id ON dbo.TableB_Large
(
	Id
);

and run the same query again

SELECT	*
FROM	dbo.TableA_Small a
		JOIN dbo.TableB_Large b
			ON a.Id = b.Id;
Execution plan showing a Nested Loop join between the two tables
Execution plan showing a Nested Loop join between the two tables
Table 'TableB_Large'. Scan count 3, logical reads 6, 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'. 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.

 SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 1 ms.

We can see SQL Server favours the nested loop as it is much cheaper to look up the 3 values from TableA in TableB using an index seek and the CPU and logical reads reflects this. To contrast this, we can see why SQL Server chose the nested loop on the now indexed table by using a join hint to force the hash join. This is purely for demonstration purposes, such a join hint should only be used in production in specific, appropriate cases

SELECT	*
FROM	dbo.TableA_Small a
		INNER HASH JOIN dbo.TableB_Large b
			ON a.Id = b.Id;
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'. Scan count 1, logical reads 202, 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'. 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.

 SQL Server Execution Times:
   CPU time = 15 ms,  elapsed time = 18 ms.

We can see that the hash join is more expensive in terms of its estimated cost and so the optimizer chose the cheaper, nested loop.

Let’s look at another example, this time we’ll use two large, sorted tables. Firstly, I’ll create another table

CREATE TABLE dbo.TableC_Large
(
	Id INT
);

INSERT INTO dbo.TableC_Large
SELECT	ABS(CHECKSUM(NewId())) % 100000
FROM	GENERATE_SERIES(1,100000);

INSERT INTO dbo.TableC_Large VALUES (1); /* ensure we have a least one row returned! */

CREATE CLUSTERED INDEX IX_Id ON dbo.TableC_Large
(
	Id
);

And run an inner join between the two large tables:

SELECT	*
FROM	dbo.TableB_Large b
		JOIN dbo.TableC_Large c
			ON b.Id = c.Id;
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 'TableC_Large'. Scan count 1, logical reads 202, 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'. Scan count 1, logical reads 202, 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.

 SQL Server Execution Times:
   CPU time = 94 ms,  elapsed time = 147 ms.

SQL Server has chosen a hash join, meaning it has scanned both tables in full, despite them being sorted. Again, I’ll force the loop join to show why that wasn’t chosen

SELECT	*
FROM	dbo.TableB_Large b
		INNER LOOP JOIN dbo.TableC_Large c
			ON b.Id = c.Id;
Table 'TableC_Large'. Scan count 100001, logical reads 213010, physical reads 0, page server reads 0, read-ahead reads 56, 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'. Scan count 9, logical reads 601, 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.

 SQL Server Execution Times:
   CPU time = 204 ms,  elapsed time = 106 ms.

Once again, we can see a hash join was more efficient than a nested loop join in this instance.

Finally, I mentioned earlier that due to the nature of values being sorted into buckets which are created per distinct value, we can’t use this type of join for predicates that return anything other than an equality match. For completeness, I’ll demonstrate this, here’s a query that uses a range predicate

SELECT	*
FROM	dbo.TableB_Large b
		JOIN dbo.TableC_Large c
			ON b.Id > c.Id AND 
			   b.Id > 99995;
Table 'TableC_Large'. Scan count 1, logical reads 202, 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 1, logical reads 201819, 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'. Scan count 1, logical reads 2, 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.

 SQL Server Execution Times:
   CPU time = 187 ms,  elapsed time = 525 ms.

As expected, by nature of the predicate, this returns a lot of rows, the plan shows us that a nested loop join was chosen by SQL Server.

If I try to force the use of a hash join, SQL Server just flat out refuses because as we said above, this is not possible

SELECT	*
FROM	dbo.TableB_Large b
		INNER HASH JOIN dbo.TableC_Large c
			ON b.Id > c.Id AND 
			   b.Id > 99995;
Msg 8622, Level 16, State 1, Line 1
Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN.

Note that when we have an equality predicate as well as the range predicate, we are able to force the hash join:

SELECT	*
FROM	dbo.TableB_Large b
		INNER HASH JOIN dbo.TableC_Large c
			ON b.Id = c.Id AND 
			   b.Id > 99995;

The reason being that the range predicate gets pushed down into the index seek operators and the hash join deals with the equality predicate

So we can see here how the cost based optimizer chooses between the two physical join operators depending on the particular scenario – size of the sets, sorted / unsorted sets, equality or inequality predicates etc. Whilst we don’t know exactly how SQL Server comes up with its costs and they don’t really equate to a real world metric, we can see the part they play in choice of join operator.

Conclusion

In this post, we continued our look into physical join operators within SQL Server, specifically focussing on the hash join – the build phase creates hash buckets from the smaller input, and the probe phase works through the larger input matching rows against those buckets. We’ve also seen the practical implications of this:

  • Hash joins shine when joining large, unsorted datasets where a nested loop would be impractical
  • They require memory to store the hash table, and can spill to tempdb when that memory isn’t available
  • They only support equality predicates – if your join condition uses a range or inequality, the optimizer can’t use a hash join to satisfy that, though it could push it to another operator

We’ve also seen the optimizer doing its job well – naturally gravitating toward a nested loop once an index was available, and only choosing the hash join when it was genuinely the cheaper option. The estimated costs, while not representing any real-world unit of measurement, are doing meaningful work behind the scenes.

In the next post in this series we’ll look at the third and final physical join operator – the merge join


References / Further Reading

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

Bert Wagner – Visualizing Hash Match

dualcoredba – Physical Joins – Merge Join

dualcoredba – Physical Joins – Nested Loop

Use the Index Luke – Hash Join

Posted in