EXCEPT 运算符背后的算法是什么？

Question

在 SQL Server 中，Except运算符如何在幕后工作的内部算法是什么？它是否在内部获取每一行的哈希值并进行比较？

David Lozinksi 进行了一项研究，SQL：在不存在新记录的地方插入新记录的最快方法他表明，对于大量行，Except 语句是最快的；与我们下面的结果密切相关。

假设：我认为 Left join 会最快，因为它只比较 1 列，Except 花费的时间最长，因为它必须比较所有列。
有了这些结果，现在我们的想法是，Except 自动并在内部获取每一行的哈希值？我查看了除非执行计划，它确实使用了一些哈希。

背景：我们的团队正在比较两个堆表。表 A 不在表 B 中的行被插入到表 B 中。

堆表（来自旧文本文件系统）没有主键/guids/标识符。有些表有重复的行，所以我们找到每一行的Hash，并去除重复，并创建主键标识符。

1）首先我们运行一个except语句，排除（哈希列）

select * from TableA
Except
Select * from TableB,

2）然后我们在HashRowId上的两个表之间运行左连接比较

select * 
FROM dbo.TableA A
left join dbo.TableB B
    on A.RowHash =  B.RowHash
where B.Hash is null

令人惊讶的是，Except Statement Insert 是最快的。

结果实际上与 David Lozinksi 的测试结果接近

Answer 1

在 SQL Server 中，Except 运算符如何在幕后工作的内部算法是什么？

我不会说EXCEPT. 对于A EXCEPT B，引擎从 A 中获取不同的（如果需要）元组并减去 B 中匹配的行。没有特殊的查询计划运算符。区别和减法是通过您在排序或连接中看到的典型运算符实现的。嵌套循环连接、合并连接和散列连接都受支持。为了说明这一点，我将把 1500 万行放入一对堆中：

DROP TABLE IF EXISTS dbo.TABLE_1;

CREATE TABLE dbo.TABLE_1 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_1 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


DROP TABLE IF EXISTS dbo.TABLE_2;

CREATE TABLE dbo.TABLE_2 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_2 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

优化器通常基于成本做出关于如何实现排序和连接的决策。对于两个堆，我按预期获得了哈希连接。您可以通过添加索引或更改任一表中的数据来自然地查看其他连接类型。下面我使用提示强制合并和循环连接，仅用于说明目的：

它是否在内部获取每一行的哈希值并进行比较？

否。它与任何其他连接一样实现。一个区别是 NULL 被视为相等。这是一种特殊类型的比较，你可以在执行计划中看到：<Compare CompareOp="IS">。但是，您可以使用不包含EXCEPT关键字的T-SQL 获得相同的计划。例如，以下查询计划与EXCEPT使用散列连接的查询完全相同：

SELECT t1.*
FROM
(
    SELECT DISTINCT COL1, COL2
    FROM dbo.TABLE_1
) t1
WHERE NOT EXISTS (
    SELECT 1
    FROM dbo.TABLE_2 t2
    WHERE (t1.COL1 = t2.COL1 OR (t1.COL1 IS NULL AND t2.COL1 IS NULL))
    AND (t1.COL2 = t2.COL2 OR (t1.COL2 IS NULL AND t2.COL2 IS NULL))
);

对执行计划的 XML 进行区分只会揭示围绕别名之类的表面差异。散列连接的探测残差进行行比较。对于两个查询，它们是相同的：

如果您仍有疑问，我以最高的可用采样率运行PerfView，以获取带有EXCEPT和不带有它的查询的调用堆栈。以下是并排的结果：

没有真正的区别。由于计划中的哈希匹配，存在引用哈希的调用堆栈。如果我添加索引以获得自然合并连接，您将不会在调用堆栈中看到任何对散列的引用：

发生的任何散列都是由于散列匹配运算符的实现。没有什么特别之处EXCEPT会导致特殊的内部散列比较。