Microsoft has provided three Join operations for use in SQL Server. These operations are the Nested Loops, Hash Match and Merge Join. Each of these provides different benefits, and depending on the workload, one can be a better choice than the other two for a given query. The optimizer will choose the most efficient of these based on the conditions of the query and the underlying schema and indexes involved in the query. This article is the second of three in a series to explore these three Join Operations.
The first article in the series, on Nested Loops, can be found here.
The Hash Match represents the building of a hash table of computed hash values from each row in the input. From this MSDN article, this is the behavior of how that hash table is built. With a Hash match, you can expect to see the HASH:() and RESIDUAL:() predicates in an execution plan and potentially a probe row. This process works as follows:
- For any joins, use the first (top) input to build the hash table and the second (bottom) input to probe the hash table. Output matches (or non-matches) as dictated by the join type. If multiple joins use the same join column, these operations are grouped into a hash team.
- For the distinct or aggregate operators, use the input to build the hash table (removing duplicates and computing any aggregate expressions). When the hash table is built, scan the table and output all entries.
- For the union operator, use the first input to build the hash table (removing duplicates). Use the second input (which must have no duplicates) to probe the hash table, returning all rows that have no matches, then scan the hash table and return all entries.
In a Graphical Execution Plan, the Hash Match Operator looks like the following image.
When using the “set statistics profile” option, you will notice that the Hash Match will appear in your results, as shown in the following image.
How can we see the Hash Match in action? Let’s do a little setup to demonstrate the Hash Match. First let’s create some tables and then populate those tables with the following scripts.
-- Create Tables SELECT TOP 25 CustID = IDENTITY( INT,1,1 ), FirstName = 'George' + CHAR(ABS(CHECKSUM(NEWID())) % 26 + 65) + CHAR(ABS(CHECKSUM(NEWID())) % 26 + 65) , LastName = 'Randcust' + CHAR(ABS(CHECKSUM(NEWID())) % 26 + 65) + CHAR(ABS(CHECKSUM(NEWID())) % 26 + 65) + CHAR(ABS(CHECKSUM(NEWID())) % 26 + 65) INTO dbo.Customer FROM Master.dbo.SysColumns t1 , Master.dbo.SysColumns t2 GO SELECT TOP 1000000 OrderID = IDENTITY( INT,1,1 ), CustID = ABS(CHECKSUM(NEWID())) % 25 + 1 , OrderAmt = CAST(ABS(CHECKSUM(NEWID())) % 10000 / 100.0 AS MONEY) , OrderDate = CAST(RAND(CHECKSUM(NEWID())) * 3653.0 + 36524.0 AS DATETIME) INTO dbo.Orders FROM Master.dbo.SysColumns t1 , Master.dbo.SysColumns t2 GO CREATE TABLE [dbo].[OrderDetail] ( [OrderID] [int] NOT NULL , [OrderDetailID] [int] NOT NULL , [PartAmt] [money] NULL , [PartID] [int] NULL ); INSERT INTO OrderDetail ( OrderID , OrderDetailID , PartAmt , PartID ) SELECT OrderID , OrderDetailID = 1 , PartAmt = OrderAmt / 2 , PartID = ABS(CHECKSUM(NEWID())) % 1000 + 1 FROM Orders;
As you can see, I have created three tables for this simple example. None of these tables has an Index or a Primary Key at this point. Let’s run a query against two of these tables and see the results.
SELECT O.OrderId , OD.OrderDetailID , O.OrderAmt , OD.PartAmt , OD.PartID , O.OrderDate FROM Orders O INNER JOIN OrderDetail OD ON O.OrderID = OD.OrderID
The execution plan for this query looks like the following image:
Here, we see that the query results in a Hash Match at this point. I could force a Nested Loops or Merge Join to occur if I were to use a query option, such as shown in the following queries.
SELECT O.OrderId , OD.OrderDetailID , O.OrderAmt , OD.PartAmt , OD.PartID , O.OrderDate FROM Orders O INNER JOIN OrderDetail OD ON O.OrderID = OD.OrderID -- This is a hash match for this example OPTION ( LOOP JOIN ) --force a loop join SELECT O.OrderId , OD.OrderDetailID , O.OrderAmt , OD.PartAmt , OD.PartID , O.OrderDate FROM Orders O INNER JOIN OrderDetail OD ON O.OrderID = OD.OrderID -- This is a hash match for this example OPTION ( MERGE JOIN ) --force a merge join
That is a simple enough change, and we have effectively been able to force a Hash Match into a different Join Operator. Is that really a wise thing to do? Keep in mind that we are querying a table that is without indexes. To see the impact of these Hints on this query, let’s examine some execution statistics.
This illustrates the cost of this simple query using what the optimizer has determined to be the best Join Operator (Hash match) versus the effect of forcing a different Join Operator. The results are pretty telling on this query. It is no contest between the three operators that that Hash match is the best choice.
In the previous article about Nested Loops, I proceeded at this point to add indexes and so forth. For this article, I want to show what will happen by adding a third table to this query. After that, we will explore the effects of adding conditions to the predicate. Before proceeding, we will create a Clustered Index on each of the tables already created.
CREATE CLUSTERED INDEX CX_CustID ON Customer(CustID) CREATE CLUSTERED INDEX CX_OrderDetailID ON OrderDetail(OrderId,OrderDetailID) CREATE CLUSTERED INDEX CX_OrderID ON dbo.Orders(OrderID)
We will then execute the following query and retrieve the execution plan for it.
Select C.FirstName,C.LastName ,O.OrderId, OD.OrderDetailID, O.OrderAmt , OD.PartAmt, OD.PartID, O.OrderDate From Orders O Inner Join OrderDetail OD On O.OrderID = OD.OrderID INNER JOIN Customer C ON O.CustID = C.CustID;
Here is the complete execution plan:
Notice that the query optimizer in this case continues to choose the Hash Match as the best Join Operator for this query. In this example, we see that the Hash Match is chosen for both Join Operators.
My next step is to filter the data. Finding a good predicate is essential when tuning a query. Depending on the predicate that is chosen, you could find a better or worse performing query. For the sake of this article, I have chosen two predicates to demonstrate and to compare to the use of the Join hints previously shown.
SELECT C.FirstName , C.LastName , O.OrderId , OD.OrderDetailID , O.OrderAmt , OD.PartAmt , OD.PartID , O.OrderDate FROM Orders O INNER JOIN OrderDetail OD ON O.OrderID = OD.OrderID INNER JOIN Customer C ON O.CustID = C.CustID WHERE O.OrderID < 1000;
And second version of the query is:
SELECT C.FirstName , C.LastName , O.OrderId , OD.OrderDetailID , O.OrderAmt , OD.PartAmt , OD.PartID , O.OrderDate FROM Orders O INNER JOIN OrderDetail OD ON O.OrderID = OD.OrderID INNER JOIN Customer C ON O.CustID = C.CustID WHERE C.CustID < 25;
In this section I introduce a couple of terms that could use some clarification. Those terms are right-deep and left-deep. These terms are in reference to how a hash join is performed. When discussing left-deep vs. right-deep hashes, I find it useful to imagine a binary tree with a left leg and a right leg. A third term that I do not discuss is the bushy hash. Picture a bushy hash as a balanced binary tree where the left leg and the right leg are the same length. Then a right-deep and a left-deep can be easy to picture as either the right leg or the left leg being longer than the other leg. The length of that leg depends on the size of the inputs from the hash joins. The size from those inputs will impact when SQL server begins the probe phase. In a left-deep the probe all hash joins must complete before beginning the probe. With a right-deep hash, the probe can begin after the completion of the first hash build since that hash serves as an input to the next hash join.
The change in predicate is enough to sway performance of this query a considerable amount. The predicate of O.OrderID causes the Hash Match to be a right deep hash which happens to also eliminate the parallelism in this particular query. The predicate of C.CustID causes the query to utilize a left deep hash. What this means is that the O.OrderID causes the Hash Match to build the hash table on the two smaller tables (Customer and Orders) and then to probe against OrderDetails. This changes the memory requirements and changes the performance of the query. The following table helps to illustrate this performance shift.
For this particular query, the right deep version using the predicate of O.OrderID is the best plan to choose. That is, of course, if it meets the requirements. Also notice that for this example, the hash match query did outperform the Nested loops and the Merge Join operators within the respective predicates. It is also worth noting that continued tweaking of these predicates would eventually yield a less costly query that utilizes either the Merge Join or the Nested Loops operators.
The Hash Match join is a physical operator that the optimizer employs based on query conditions. The Hash Match can be seen in a graphical execution plan and can be employed with any join type yet does require an equijoin be present. The Hash Match Join is most likely to be the choice of the optimizer when one table has a large number of records.