在两个表中查找不同的行：全外连接比联合更有效？

Question

在我们不一定能确保预先排序的两个表中找到不同的行时，使用 aFULL OUTER JOIN而不是 a是个好主意UNION吗？这种方法有什么缺点吗？如果它始终更快，为什么查询优化器不为 UNION 选择FULL OUTER JOIN将使用的相同计划？

通过将 a 重写UNION为FULL OUTER JOIN. AUNION似乎是编写逻辑的更直观的方式，但在探索这两个选项时，我发现 A 的FULL OUTER JOIN内存和 CPU 使用率都更高。

如果您想运行我们的生产查询的简化和匿名版本，请参阅以下脚本：

安装脚本

-- 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选择了小的两个表的作为散列的生成端，这意味着存储器使用正比于较小的表（500K行）的大小。

-- 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对整个数据集的散列集料构建一个哈希表，这意味着存储器使用正比于不同行的总数目（5.4MM行在这种情况下;通常，行的数量至少在的较大两张桌子）。内存使用量比 大 10 倍以上FULL OUTER JOIN，并且 CPU 时间和运行时间也更慢。如果我将其扩展到哈希聚合无法容纳在单个查询的内存授予中的程度，则性能差异将变得巨大（就像在我们的大型生产查询中一样）。

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

Answer 1

两个查询的语义不同 -UNION删除重复项，而FULL OUTER JOIN不会：

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;

输出：

????????????
? id ? val ?
????????????
?  1 ?   1 ?
?  1 ?   1 ?
?  1 ?   1 ?
?  1 ?   1 ?
????????????

????????????
? id ? val ?
????????????
?  1 ?   1 ?
????????????

也就是说，优化器不知道很多FOJN技巧，所以总是有可能有比自然的更好的方式来表达查询UNION。仅实现常用且始终正确的转换。

请注意，仅在较大表上具有唯一约束时，优化器会选择散列联合，而无需对探针输入进行昂贵的重复删除，这使其在问题示例中选择 Concat Union All：

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;

FOJN如果您知道每个输入集中不能有重复项，则重写可能很有用，但这种情况不是通过唯一约束或索引强制执行的（尤其是在大输入上）。

如果这样的唯一性保证确实存在，但优化器没有选择散列联合，您可以尝试OPTION (HASH UNION)提示，看看它如何比较。