Union implemented with Hash Match operator

Question

I was reviewing the SQL Server physical operators listed on TechNet (don't judge, you know you've done it) and read that the Hash Match physical operator is sometimes used to implement the UNION logical operator.

I have never seen that done and would like to learn more. An example query would be great. When is it used and when is it better than the alternatives? (Those are usually the same, but not always.)

Answer 1

An example query would be great.

Using a numbers table (integers 1...n, where n needs to be at least 1000 for this example):

SELECT N.n % 10, SPACE(100) 
FROM dbo.Numbers AS N 
WHERE N.n BETWEEN 1 AND 1000
UNION
SELECT 999, SPACE(100);

Results:

999
6
4
8
3
1
0
7
5
9
2

When is it used and when is it better than the alternatives?

Hash union is not very common. It is preferred when one table is wide and has many duplicates, while the other is small (relatively few rows) and known to be distinct. A wide build side with lots of duplicates plays to the hash table's strengths because it is immediately only stored once per dupe.

How it works

The Hash Union operator builds a hash table on the upper (build) input eliminating duplicates as it goes (like a hash aggregate performing a distinct). It then reads rows from the lower (probe) input. If there is no match in the hash table, the row is returned. When the probe input is exhausted, the operator returns each row in the hash table.

Hash Union does not add rows from the probe side to the hash table, so it cannot eliminate duplicates from that input. The optimizer either has to have a guarantee of uniqueness, or add a grouping operator to the probe side.

Answer 2

I cannot recall seeing a hash match (union) operator in the wild so I can't speak authoritatively as to when they are better than the alternatives. It's possible to force one using the { CONCAT | HASH | MERGE } UNION query hint but let's try to create a real example. Quote from the documentation referenced in the question:

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.

So how can we create a query with a hash match (union) operator as the option with the lowest cost? Well, hash join tends to scale much better with parallelism than merge join so a query running in parallel could help tip the scales towards hash match. We need the second input to have no duplicates so a unique constraint on a table could help, but unique constraints are implemented as indexes so that will help a merge join as well. Perhaps giving the hash table lots of duplicates will favor the hash match over the concatenation option because we'll be doing a smaller effective sort?

After some trial and error, one approach that works on my machine is to insert one million rows with 10000 distinct values into one table and one million distinct values into another table. Sample code:

CREATE TABLE X_NUM_SMALL (ID INT NOT NULL);
GO
INSERT INTO X_NUM_SMALL WITH (TABLOCK)
SELECT TOP (10000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;
GO 100

CREATE TABLE X_NUM_1000000_UQ (ID INT NOT NULL);

INSERT INTO X_NUM_1000000_UQ WITH (TABLOCK)
SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

ALTER TABLE X_NUM_1000000_UQ 
ADD CONSTRAINT UC_X_NUM_1000000 UNIQUE (ID);  

SET STATISTICS IO, TIME ON;

The following query has a hash match (union) operator with a total estimated cost of 12.3812 units:

SELECT *
FROM X_NUM_SMALL

UNION

SELECT *
FROM X_NUM_1000000_UQ
OPTION (MAXDOP 4);

Adding a MERGE UNION hint to the query increases the cost just barely to 12.6551 optimizer units. Exchanging that hint for a CONCAT UNION hint increases the cost further to 17.2215 optimizer units.

I did a few test runs and usually the hash match (union) operator query was just barely faster than the others. Here are results from the most recent run:

╔════════════╦══════════╦══════════════╗
║ UNION TYPE ║ CPU TIME ║ ELAPSED TIME ║
╠════════════╬══════════╬══════════════╣
║ HASH       ║      657 ║         2279 ║
║ MERGE      ║      312 ║         2375 ║
║ CONCAT     ║      906 ║         2459 ║
╚════════════╩══════════╩══════════════╝

Answer 3

The UNION operator combines all the rows from one query with all the rows from another, eliminating duplicates, and forming a single list. The hash operator builds a hash table from the upper input and probes that table with the lower input. I can see how this would work to implement a UNION, given the row-at-a-time pull model the execution engine uses. I imagine it works something like this.

The Hash operator is asked for a row. It, in turn, pulls a row from the upper table, hashes it and compares it to its current list. If it is not found in the list it is a new value, it gets added to the hash list and also returned to the calling operator. This continues. Eventually a row is read that has a match in the hash table. That row is rejected (UNION eliminates duplicates) and the next row read. Eventually the upper input is exhausted. Processing continues with the lower input, reading rows, rejecting matches and passing on fresh values, until it, too, is exhausted.

Under what conditions would a hash match be used instead of another operator? The trivial answer is because the optimiser has determined that the cost of a hash operator, for the given datasets, is less than the cost of any other operator that could perform this task. More specifically (I'm extrapolating somewhat from joins) hash match typically occur for larger datasets without appropriate sorting.

Here's an example that shows the usage. I have a Numbers table, which I've copied to create dbo.Numbers and dbo.Numbers2.

The query

select * from dbo.Numbers

union

select * from dbo.Numbers2

uses a merge join. Unsurprising, since both tables are ordered appropriately for the query. By deleting the primary key on one table, however, and converting it to a heap, the optimiser no longer has a guarantee of ordering and it uses a hash operator:

Note the naming, however. This is Hash Match (Union). Changing the query to a join

select * from dbo.Numbers as n1
inner join dbo.Numbers2 as n2
    on n2.Number = n1.Number

Also uses a hash match

This time it is Hash Match (Inner Join). The properties for the Hash match in each query differ.

As for table size, with 10,000 rows in dbo.Numbers a hash match is still used. With 5,000 a sort and Merge Join (Union) are used instead.