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:
-- 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
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
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