除了操作符后面的算法是什么？

Question

例外操作符如何在Server的掩护下工作的内部算法是什么？它内部是否接受每一行的散列并进行比较？

David进行了一项研究，他向SQL:插入尚不存在的新记录的最快方法展示了除了语句对大量行来说是最快的；与我们下面的结果紧密结合在一起。

假设:我认为左联接最快，因为它只比较1列，除了耗时最长，因为它必须对所有列进行比较。

有了这些结果，现在我们的想法是，除了自动和内部的散列每一行？除了执行计划之外，我还看了一下，它确实使用了一些散列。

背景:我们的团队正在比较两个堆表。表B中未列的表A行已插入表B。

堆表(来自遗留文本文件系统)没有主键/guid/标识符。有些表有重复的行，因此我们找到了每一行的哈希，并删除了重复项，并创建了主键标识符。

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

令人惊讶的是，was语句插入速度最快。

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

Answer 1

在SQL Server中，除了操作符如何工作的内部算法是什么？

我不会说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关键字的that获得相同的计划。例如，下面的查询计划与使用散列连接的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))
);

Diffing执行计划的XML只是揭示了别名和诸如此类的表面差异。散列联接的探测残数进行行比较。对于这两个查询，它们是相同的：

如果您仍然有疑问，我以最高的可用样本率运行PerfView来获得EXCEPT查询的调用堆栈，以及没有它的查询。以下是并排的结果：

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

发生的任何散列都是由于哈希匹配操作符的实现造成的。EXCEPT没有什么特别之处，它导致了一个特殊的内部哈希比较。