Visualizing Hash Match Join Internals And Understanding Their Implications

This post is part 3 in a series about physical join operators (be sure to check out part 1 - nested loops joins, and part 2 - merge joins).

Watch this week's video on YouTube

Hash Match joins are the dependable workhorses of physical join operators.

While Nested Loops joins will fail if the data is too large to fit into memory, and Merge Joins require that the input data are sorted, a Hash Match will join any two data inputs you throw at it (as long as the join has an equality predicate and you have enough space in tempdb). 

The base hash match algorithm has two phases that work like this:


During the first "Build" phase, SQL Server builds an in-memory hash table from one of the inputs (typically the smaller of the two).  The hashes are calculated based on the join keys of the input data and then stored along with the row in the hash table under that hash bucket.  Most of the time there is only 1 row of data per hash bucket except when:

  1. There are rows with duplicate join keys.
  2. The hashing function produces a collision and totally different join keys receive the same hash (uncommon but possible).

Once the hash table is built, SQL Server begins the "Probe" phase.  During this second phase, SQL Server calculates the join key hash for each row in the second input, and checks to see if it exists in the hash table created in the first build phase.  If it finds a match for that hash, it then verifies if the join keys between the row(s) in the hash table and the row from the second table actually match (it needs to perform this verification due to potential hash collisions).

A common variation on this hash match algorithm occurs when the build phase cannot create a hash table that can be fully stored in memory:


This happens when the data is larger than what can be stored in memory or when SQL Server grants an inadequate amount of memory required for the hash match join.

When SQL Server runs doesn't have enough memory to store the build phase hash table, it proceeds by keeping some of the buckets in memory, while spilling the other buckets to tempdb. 

During the probe phase, SQL Server joins the rows of data from the second input to buckets from the build phase that are in memory. If the bucket that the row potentially matches isn't currently in memory, SQL Server writes that row to tempdb for later comparison. 

Once the matches for one bucket are complete, SQL Server clears that data from memory and loads the next bucket(s) into memory. It then compares the second input's rows (currently residing in tempdb) with the new in-memory buckets.

As with every physical join operator in this series, there are way more details about the hash match operator on Hugo Kornelis's reference on hash matches.

What Do Hash Match Joins Reveal?

Knowing the internals of how a hash match join works allows us to infer what the optimizer thinks about our data and the join's upstream operators, helping us focus our performance tuning efforts. 

Here are a few scenarios to consider the next time you see a hash match join being used in your execution plan:

  • While hash match joins are able to join huge sets of data, building the hash table from the first input is a blocking operation that will prevent downstream operators from executing. Due to this, I always check to see if there is an easy way to convert a hash match to either a nested loops or merge join.  Sometimes that won't be possible (too many rows for nested loops or unsorted data for merge joins) but it's always worth checking if a simple index change or improved estimates from a statistics update would cause SQL Server to pick a non-blocking hash match join operator.

  • Hash match joins are great for large joins - since they can spill to tempdb, it allows them to perform joins on large datasets that would fail an in-memory join with either the nested loops or merge join operators.

    • Seeing a hash match join operator means SQL Server thinks the upstream inputs are big.  If we know our inputs shouldn't be that big, then it's worth checking if we have a stats/estimation problem that is causing SQL Server to choose a hash match join incorrectly.
  • When executed in memory, hash match joins are fairly efficient. Problems arise when the build phase spills to tempdb.

    • If I notice the little yellow triangle indicating that the join is spilling to tempdb, I take a look to see why: if the data is larger than the server's available memory, there's not much that can be done there, but if the memory grant seems unusually small that means we probably have another statistics problem that is providing the SQL Server optimizer estimates that are too low.

Visualizing Nested Loops Joins And Understanding Their Implications

This post is the first in a series about physical join operators (be sure to check out part 2 - merge joins, and part 3 - hash match joins).

Watch this week's video on YouTube

What Physical Join Operators Tell Us

Everyone has their own method of reading an execution plan when performance tuning a slow SQL query.  One of the first things I like to look at are what kind of join operators are being used:


These three little icons may not seem like the most obvious place to begin troubleshooting a slow query, but with larger plans especially I like starting with a quick glance at the join operators because they allow you to infer a lot about what SQL Server thinks about your data.

This will be a three part series where we'll learn how each join algorithm works and what they can reveal about our upstream execution plan operators.

Nested Loops Join


Nested loops joins work like this: SQL Server takes the first value from our first table (our "outer" table - by default SQL Server decides for us which table of the two this will be), and compares it to every value in our second "inner" table to see if they match. 

Once every inner value has been checked, SQL Server moves to the next value in the outer table and the process repeats until every value from our outer table has been compared to every value in our inner table.

This description is a worst case example of the performance of a nested loop join.  Several optimizations exist that can make the join more efficient.  For example, if the inner table join values are sorted (because of an index you created or a spool that SQL Server created), SQL Server can process the rows much faster:


In the above animation, the inner input is a index sorted on the join key, allowing SQL Server to seek directly to the rows it needs, reducing the total number of comparisons that need to be made

For more in-depth explanations of the internals and optimizations of nested loops joins, I recommend reading this post by Craig Freedman as well as Hugo Kornelis's reference on nested loops.

What Do Nested Loops Joins Reveal?

Knowing the internals of how a nested loops join works allows us to infer what the optimizer thinks about our data and the join's upstream operators, helping us focus our performance tuning efforts. 

Here are a few scenarios to consider the next time you see a nested loops join being used in your execution plan:

  • Nested loops joins are CPU intensive; at worst, every row needs to be compared to every other row and this can take some time.  This means when you see a nested loops join, SQL Server probably thinks that one of the two inputs is relatively small.
  • ... and if one of the inputs is relatively small, great!  If instead you see upstream operators that are moving large amounts of data, you may have a estimation problem going on in this area of the plan and may need to update stats/add indexes/refactor the query to have SQL Server provide better estimates (and maybe a more appropriate join).

  • Nested loops sometimes accompany RID or key lookups.  I always check for one of these because they often leave room for some performance improvements:

    • If a RID lookup exists, it's usually easy enough to add a clustered index to that underlying table to squeeze out some extra performance.
  • If either RID or key lookup exist, I always check what columns are being returned to see if a smaller index could be used instead (by including a column in a key/column of an existing index) or if the query can be refactored to not bring back those columns (eg. get rid of the SELECT *).

  • Nested loops joins do not require data to be sorted on input.  However, performance can improve with an indexed inner data source (see animation above), and SQL Server might choose a more efficient operator if the inputs are both sorted. 

    • At the very least, nested loops joins make me think to check whether the input data isn't sorted because of some upstream transformations, or because of missing indexes.

So while nested loops in your plans will always require more investigation, looking at them and the operators around them can provide some good insight into what SQL Server thinks about your data.