Sql-server – Finding distinct rows across two tables: Full Outer Join more efficient than Union

performancequery-performancesql server

When finding distinct rows across two tables where we can't necessarily ensure are pre-sorted, is it a good idea to use a FULL OUTER JOIN rather than a UNION? Are there any downsides to this approach? If it is consistently faster, why does the query optimizer not choose the same plan for UNION that the FULL OUTER JOIN would use?

We were able to bring a specific production query from ~10 minutes to ~3 minutes by re-writing a UNION as a FULL OUTER JOIN. A UNION seems like the more intuitive way to write the logic, but upon exploring both options, I have observed that the FULL OUTER JOIN is more efficient in terms of both memory and CPU usage.

See the following scripts if you'd like to run a simplified and anonymized version of our production query:

Setup script

-- Create a 500K row table
SELECT TOP 500000 ROW_NUMBER() OVER (ORDER BY NEWID()) AS id, v1.number % 5 AS val
INTO #t1
FROM master..spt_values v1
CROSS JOIN master..spt_values v2

-- Create a 5MM row table that will match some, but not all, of the 500K row table
SELECT TOP 5000000 ROW_NUMBER() OVER (ORDER BY NEWID()) AS id, v1.number % 5 AS val
INTO #t2
FROM master..spt_values v1
CROSS JOIN master..spt_values v2

-- Optionally, key both tables to see the impact it has on query plans and performance
-- Both queries end up with essentially the same plan and performance in this case
-- So that means that at least there is not a downside to using the FULL OUTER JOIN when the data is sorted
--ALTER TABLE #t1
--ADD UNIQUE CLUSTERED (id)
--ALTER TABLE #t2
--ADD UNIQUE CLUSTERED (id)

FULL OUTER JOIN

The FULL OUTER JOIN chooses the small of the two tables as the build side of a hash join, meaning that the memory usage is proportional to the size of the smaller table (500K rows).

-- CPU time = 3058 ms,  elapsed time = 783 ms.
-- MaxUsedMemory: 29016 KB
-- Table '#t1'. Scan count 5, logical reads 1301, physical reads 0
-- Table '#t2'. Scan count 5, logical reads 12989, physical reads 0
SELECT COUNT(*), AVG(id), AVG(val)
FROM (
    SELECT COALESCE(t1.id, t2.id) AS id, COALESCE(t1.val, t2.val) AS val
    FROM #t1 t1
    FULL OUTER JOIN #t2 t2
        ON t2.id = t1.id
        AND t2.val = t1.val
) x
GO

enter image description here

UNION

The UNION builds a hash table for a hash aggregate on the overall data set, meaning that the memory usage is proportional to the total number of distinct rows (5.4MM rows in this case; generally, at least the number of rows in the larger of the two tables). The memory usage is over 10x greater than the FULL OUTER JOIN, and both CPU time and elapsed time are slower as well. If I were to scale this up to the point that hash aggregate can't fit within a single query's memory grant, the performance difference would become huge (as it was in our large production query).

-- CPU time = 4651 ms,  elapsed time = 1188 ms.
-- MaxUsedMemory: 301600 KB
-- Table '#t1'. Scan count 5, logical reads 1301, physical reads 0
-- Table '#t2'. Scan count 5, logical reads 12989, physical reads 0
SELECT COUNT(*), AVG(id), AVG(val)
FROM (
    SELECT t1.id, t1.val
    FROM #t1 t1
    UNION 
    SELECT t2.id, t2.val
    FROM #t2 t2
) x

enter image description here

Best Answer

The semantics of the two queries are not the same - UNION removes duplicates, whereas the FULL OUTER JOIN will not:

DECLARE @T1 AS table (id bigint NULL, val integer NULL);
DECLARE @T2 AS table (id bigint NULL, val integer NULL);

INSERT @T1 (id, val) VALUES (1, 1);
INSERT @T1 (id, val) VALUES (1, 1);
INSERT @T2 (id, val) VALUES (1, 1);
INSERT @T2 (id, val) VALUES (1, 1);

SELECT COALESCE(t1.id, t2.id) AS id, COALESCE(t1.val, t2.val) AS val
FROM @t1 t1
FULL OUTER JOIN @t2 t2
    ON t2.id = t1.id
    AND t2.val = t1.val;

SELECT t1.id, t1.val
FROM @t1 t1
UNION 
SELECT t2.id, t2.val
FROM @t2 t2;

Output:

╔════╦═════╗
║ id ║ val ║
╠════╬═════╣
║  1 ║   1 ║
║  1 ║   1 ║
║  1 ║   1 ║
║  1 ║   1 ║
╚════╩═════╝

╔════╦═════╗
║ id ║ val ║
╠════╬═════╣
║  1 ║   1 ║
╚════╩═════╝

That said, the optimizer does not know many FOJN tricks, so it is always possible that there is a better way to express the query than the natural UNION. Only commonly-useful and always-correct transformations are implemented.

Note that with a unique constraint only on the larger table, the optimizer chooses a hash union, without expensive duplicate-removal on the probe input, that makes it choose Concat Union All in the question example:

ALTER TABLE #t2 
ADD CONSTRAINT UQ2 
UNIQUE CLUSTERED (id);

SELECT COUNT(*), AVG(x.id), AVG(x.val)
FROM (
    SELECT t1.id, t1.val
    FROM #t1 t1
    UNION
    SELECT t2.id, t2.val
    FROM #t2 t2
) AS x;

Hash union plan

The FOJN rewrite may well be a useful one in cases where you know there cannot be duplicates within each input set, but this condition is not enforced with a unique constraint or index (particularly on the large input).

If such a uniqueness guarantee does exist, and yet the optimizer does not select a Hash Union, you might try an OPTION (HASH UNION) hint, to see how it compares.

Related Question