Today I’ll talk about the main physical JOIN operator types in SQL Server (Nested Loops, Hash and Merge Joins), their differences, best practices, and complexity (which determines when the SQL Server optimizer would use them in execution plans).
For the samples in this post, we’ll use the free AdventureWorks database sample available here.
Introduction: What are Physical Join Operators?
A physical join operator is a type of an algorithm which the SQL Server Optimizer chooses in order to implement logical joins between two sets of data.
The SQL Server Optimizer may choose a different algorithm for different scenarios based on the requested query, available indexes, statistics and number of estimated rows in each data set.
It’s possible to find the operator which was used by looking at the execution plan that SQL Server has prepared for your query.
For more information on execution plans and how to read them, I recommend checking out the first chapter out of Grant Fritchey’s excellent book on Execution Plans.
NESTED LOOPS
“Nested Loops” is the simplest operator of the bunch.
We’ll take the following query as an example, which gets some order detail columns for orders placed during July 2001 (assuming the OrderDate column only includes dates without time):
SELECT OH.OrderDate, OD.OrderQty, OD.ProductID, OD.UnitPrice
FROM Sales.SalesOrderHeader AS OH
JOIN Sales.SalesOrderDetail AS OD
ON OH.SalesOrderID = OD.SalesOrderID
WHERE OH.OrderDate BETWEEN '2001-07-01' AND '2001-07-31'
The resulting execution plan looks like this:
What the “Nested Loops” operator basically does is: For each record from the outer input – find matching rows from the inner input.
Technically, this means that the clustered index scan you see as the outer input is executed once to get all the relevant records, and the clustered index seek you see below it is executed for each record from the outer input.
We’ll verify this information by placing the cursor over the Clustered Index Scan operator and looking at the tooltip:
We’ll look at the tooltip of the Clustered Index Seek:
In terms of complexity (assume N is the number of rows from the outer output and M is the total number of rows in the SalesOrderDetail table): The complexity of this query is: O(NlogM) where “logM” is the logarithmic complexity of each seek in the inner input.
The SQL Server Optimizer will prefer to choose this operator type when the outer input is small and the inner input has an index on the column(s) by which the two data sets are joined. The bigger the difference in number of rows between the outer and inner inputs, the more benefit this operator will provide over the other operator types.
Having indexes and up-to-date statistics is crucial for this join type, because you don’t want SQL Server to accidentally think there’s a small number of rows in one of the inputs when in fact there are a whole lot. For example: Performing 10 times index seek is nothing like performing 100,000 times index seek, especially if the table size of the inner input is around 120,000 and you’d be better off doing one table scan instead.
(spoiler alert: this particular problem is partly solved using “Adaptive Joins” in SQL Server 2017)
MERGE Join
The “Merge” algorithm is the most efficient way to join between two very large sets of data which are both sorted on the join key.
We’ll use the following query as an example (which returns a list of customers and their sale order identifiers):
SELECT OC.CustomerID, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Sales.Customer AS OC
ON OH.CustomerID = OC.CustomerID
The execution plan for this query is:
- First, we’ll notice that both of the data sets are sorted on the CustomerID column: The Customer table because that’s the clustered primary key, and the SalesOrderHeader table because there’s a nonclustered index on the CustomerID column.
- By the width of the arrows between the operators (and by placing the cursor over them), we can see that the number of rows returned from each set is rather large.
- In addition, we used the equality operator (=) in the ON clause (the Merge join requires at least one equality operator).
These three factors cause SQL Server Optimizer to choose the Merge Join for this query.
The biggest performance gain from this join type is that both input operators are executed only once. We can verify this by placing the cursor over them and see that the number of executions is 1 for both of the operators. Also, the algorithm itself is very efficient:
The Merge Join simultaneously reads a row from each input and compares them using the join key. If there’s a match, they are returned. Otherwise, the row with the smaller value can be discarded because, since both inputs are sorted, the discarded row will not match any other row on the other set of data.
This repeats until one of the tables is completed. Even if there are still rows on the other table, they will clearly not match any rows on the fully-scanned table (due to the sorting on the join key), so there is no need to continue. Since both tables can potentially be fully scanned (in the worst case scenario), the maximum cost of a Merge Join is the sum of both inputs. Or in terms of complexity: O(N+M)
If the inputs are not both sorted on the join key, the SQL Server Optimizer will most likely not choose the Merge join type and instead prefer the Hash join (will be explained next). However if it does anyway (whether it’s because it was forced to due to a join hint, or because it was still deemed the most efficient), then SQL will need to sort the table which is not already sorted on the join key.
HASH Match
The “Hash” join type is what I call “the go-to guy” of the join operators. It’s the one operator chosen when the scenario doesn’t favor in any of the other join types. This happens when the tables are not properly sorted, and/or there are no indexes. When SQL Server Optimizer chooses the Hash join type, it’s usually a bad sign because something probably could’ve been done better (for example, adding an index). However, in some cases (complex queries mostly), there’s simply no other way (other than restructuring the data, for example using a temporary table to store and index intermediate results).
We’ll use the following query as an example (which gets the first and last names of contacts starting with “John” and their sales order identifiers):
SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Person.Contact AS OC
ON OH.ContactID = OC.ContactID
WHERE OC.FirstName LIKE 'John%'
The execution plan looks like this:
Because there’s no index on the ContactID column in the SalesOrderHeader table, SQL Server chooses the Hash join type.
Before diving into the example, I’ll first explain two important concepts: A ”Hashing” function and a “Hash Table”.
“Hashing” is a programmatic function which takes one or more values and converts them to a single symbolic value (usually numeric). The function is usually one-way meaning you can’t convert the symbolic value back to its original value(s), but it’s deterministic meaning if you provide the same value as input you will always get the same symbolic value as output. Also, it’s possible for several different inputs to result in the same output hash value (meaning, the function isn’t necessarily unique). The mathematical “modulus” operator, and functions such as CHECKSUM, are examples of possible hash functions.
A “Hash Table” is a data structure that divides all rows into equal-sized “buckets”, where each “bucket” is represented by a hash value. This means that when you activate the hash function on some row, using the result you’ll know immediately to which bucket it belongs.
As with the Merge join, the two input operators are executed only once. We can verify this by looking at the tooltips of the input operators. However, unlike with the Merge join, a Hash join causes BOTH of the inputs to be SCANNED FULLY.
Using available statistics, SQL Server will choose the smaller of the two inputs to serve as the build input and it will be the one used to build the hash table in memory (hash value is calculated per each row, and saved in a “bucket”). If there’s not enough memory for the hash table, SQL Server will use physical disk space in TEMPDB (which could mean a HUGE performance hit). After the hash table is built, SQL Server will get the data from the larger table, called the probe input, compare it to the hash table using a hash match function (for each row), and return any matched rows. In graphical execution plans, the build input will always be the one on top, and the probe input will be the one below.
As long as the smaller table is very small, this algorithm can be very efficient. But if both tables are very large, this can be a very costly execution plan.
SQL Server Optimizer uses statistics to figure out the cardinality of the values. Using that information, it dynamically creates a hash function which will divide the data into as many buckets with sizes as equal as possible.
Because it’s so dynamic, it’s difficult to estimate the complexity of the creation of the hash table and the complexity of each hash match. Because SQL Server Optimizer performs this dynamic operation during execution time and not during compilation time, sometimes the estimated values you see in the execution plan are incorrect. In some cases, you could compare a hash join and a nested loops join, see that according to the execution plans the nested loop is more expensive (in terms of logical reads etc.), when in fact the hash join executes much slower (because its cost estimation is incorrect).
For our complexity terms, we’ll assume hc is the complexity of the hash table creation, and hm is the complexity of the hash match function. Therefore, the complexity of the Hash join will be O(N*hc + M*hm + J) where N is the smaller data set, M is the larger data set and J is a “joker” complexity addition for the dynamic calculation and creation of the hash function. Generally, the complexity of hc, hm and J are relatively insignificant, so the actual time complexity estimation of the Hash join operator would be O(N+M).
Moreover, the worst thing about the Hash join is actually not its complexity, but the dangers it poses in terms of resource consumption. The hash table it has to build can potentially eat up a lot of memory, and as mentioned before, even spill the operation to Temp DB and physical disk. This also means that an execution plan that uses a Hash join will potentially require very high memory grants.
Microsoft has an interesting page in their documentation that describes further Hash Join “sub-types” and additional aspects about them. I strongly recommend you read it:
Understanding Hash Joins | Microsoft Docs
Query Hints
Using Query Hints, it’s possible to force SQL Server to use specific join types. However, it’s highly not recommended to do so especially in production environments, because the same join type may not be the best choice forever (because data can change), and SQL Server Optimizer usually has it right (assuming statistics are up-to-date).
I’ll talk about them just so you can experiment with the different join types on your test environment and see the differences in the execution plans.
To force SQL Server to use specific join types using query hints, you add the OPTION clause at the end of the query, and use the keywords LOOP JOIN, MERGE JOIN or HASH JOIN.
Try executing the various queries mentioned earlier with different join hints and see what happens. For example:
SELECT OC.CustomerID, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Sales.Customer AS OC
ON OH.CustomerID = OC.CustomerID
OPTION (HASH JOIN)
SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Person.Contact AS OC
ON OH.ContactID = OC.ContactID
WHERE OC.FirstName LIKE 'John%'
OPTION (LOOP JOIN)
SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Person.Contact AS OC
ON OH.ContactID = OC.ContactID
WHERE OC.FirstName LIKE 'John%'
OPTION (MERGE JOIN)
Adaptive Joins (since SQL Server 2017)
A fancy new feature in SQL Server 2017, called “Adaptive Joins“, was introduced as part of the new feature set of “Adaptive Query Processing”.
What this basically does, is it enables the choice of a Hash Join or Nested Loops Join method to be deferred until after the first input has been scanned (as opposed to during compilation time, before the query is actually executed), which should solve possible problems caused by outdated or skewed statistics. The way it works is by starting out with the Hash Join operation, and unless the number of processed rows exceeds a certain threshold, the execution plan “switches over” to a Nested Loops operation instead. For example:
In this execution plan we see:
- This branch represents the index seek that would be used by the Nested Loop operation.
- This branch represents the probe phase of a standard Hash Join operation.
There are a couple of problems with it, though.
One problem (resolved in SQL Server 2019) is that this new feature is currently supported in Batch mode only. Which means that you must have a columnstore index defined on the tables that are being joined. There are ways to circumvent this limitation in pre-SQL Server 2019 versions, even though it’s not very pretty.
Another problem is that this feature has an expensive overhead: It requires much higher memory grants than normal. More specifically, it requests for additional memory as if the Nested Loops operator was actually a Hash Join operator. So, on the one hand, in certain scenarios you’ll see a relative benefit in performance, while on the other hand, you’ll still have to pay the same expensive price you’d pay for a Hash Join (in terms of memory resource consumption).
For more information on Adaptive Joins specifically, and Adaptive Query Processing in general, read more here.
And also be sure to watch this cool presentation by Fabiano Amorim.
Summary
Hopefully you’re now familiar with SQL Server’s physical join operator types, and how their complexity is calculated – and consequently, how SQL Server chooses which to use (based on their respective complexity costs).
Nested Loops
- Complexity: O(NlogM)
- Used usually when one table is significantly small
- The larger table has an index which allows seeking it using the join key
Merge Join
- Complexity: O(N+M)
- Both inputs are sorted on the join key
- An equality operator is used
- Excellent for very large tables
Hash Match
- Complexity: O(N*hc+M*hm+J) or O(N+M) if you ignore resource consumption costs
- Last-resort join type
- Uses a hash table and a dynamic hash match function to match rows
- Higher cost in terms of memory consumption and disk IO utilization.
Resources
The following resources were used for the making of this post:
- Inside the SQL Server Query Optimizer by Benjamin Nevarez
- SQL Server Execution Plans by Grant Fritchey
- Advanced Query Tuning Concepts at Microsoft’s SQL Server Books Online
- Blog post about Hash Joins by Craig Freedman
- Adaptive Query Processing by Fabiano Amorim
This article was originally published by Eitan Blumin on January, 2012 in www.madeiradata.com