使用哈希匹配运算符实现的联合

Question

我正在查看 TechNet 上列出的 SQL Server 物理运算符（不要判断，你知道你已经完成了）并读到哈希匹配物理运算符有时用于实现UNION逻辑运算符。

我从未见过这样做过，并想了解更多。一个示例查询会很棒。什么时候使用它，什么时候它比替代品更好？（这些通常是相同的，但并非总是如此。）

Answer 1

我不记得在野外看到过散列匹配（联合）运算符，所以我无法权威地说它们何时比替代方案更好。可以使用{ CONCAT | HASH | MERGE } UNION 查询提示强制执行一个，但让我们尝试创建一个真实示例。引用问题中引用的文档：

对于联合运算符，使用第一个输入来构建哈希表（删除重复项）。使用第二个输入（必须没有重复项）来探测哈希表，返回没有匹配项的所有行，然后扫描哈希表并返回所有条目。

那么我们如何创建一个带有哈希匹配（联合）操作符作为成本最低的选项的查询呢？好吧，散列连接的并行性往往比合并连接的扩展性好得多，因此并行运行的查询可以帮助扩展到散列匹配。我们需要第二个输入没有重复，因此表上的唯一约束可能会有所帮助，但唯一约束是作为索引实现的，因此也有助于合并连接。也许为哈希表提供大量重复项将有利于哈希匹配而不是串联选项，因为我们将进行更小的有效排序？

经过反复试验，在我的机器上工作的一种方法是将具有 10000 个不同值的一百万行插入到一个表中，并将一百万个不同值插入到另一个表中。示例代码：

CREATE TABLE X_NUM_SMALL (ID INT NOT NULL);
GO
INSERT INTO X_NUM_SMALL WITH (TABLOCK)
SELECT TOP (10000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;
GO 100

CREATE TABLE X_NUM_1000000_UQ (ID INT NOT NULL);

INSERT INTO X_NUM_1000000_UQ WITH (TABLOCK)
SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM master..spt_values t1
CROSS JOIN master..spt_values t2;

ALTER TABLE X_NUM_1000000_UQ 
ADD CONSTRAINT UC_X_NUM_1000000 UNIQUE (ID);  

SET STATISTICS IO, TIME ON;

以下查询有一个哈希匹配（联合）运算符，估计总成本为 12.3812 个单位：

SELECT *
FROM X_NUM_SMALL

UNION

SELECT *
FROM X_NUM_1000000_UQ
OPTION (MAXDOP 4);

向MERGE UNION查询添加提示只会将成本增加到 12.6551 个优化器单元。将该提示交换为CONCAT UNION提示会使成本进一步增加到 17.2215 个优化器单元。

我做了一些测试运行，通常哈希匹配（联合）运算符查询比其他运算符查询快一点。以下是最近一次运行的结果：

????????????????????????????????????????
? UNION TYPE ? CPU TIME ? ELAPSED TIME ?
????????????????????????????????????????
? HASH       ?      657 ?         2279 ?
? MERGE      ?      312 ?         2375 ?
? CONCAT     ?      906 ?         2459 ?
????????????????????????????????????????

Answer 2

一个示例查询会很棒。

使用数字表（整数 1...n，在此示例中，n 需要至少为 1000）：

SELECT N.n % 10, SPACE(100) 
FROM dbo.Numbers AS N 
WHERE N.n BETWEEN 1 AND 1000
UNION
SELECT 999, SPACE(100);

结果：

999
6
4
8
3
1
0
7
5
9
2

什么时候使用它，什么时候它比替代品更好？

哈希联合不是很常见。当一个表很宽并且有很多重复项，而另一个表很小（相对较少的行）并且已知是不同的时，这是首选。具有大量重复项的广泛构建侧发挥了哈希表的优势，因为每个重复项仅立即存储一次。

这个怎么运作

Hash Union 运算符在上层（构建）输入上构建一个哈希表，并在执行过程中消除重复项（就像执行不同的哈希聚合一样）。然后它从较低的（探针）输入读取行。如果哈希表中没有匹配项，则返回该行。当探测输入用完时，运算符返回哈希表中的每一行。

Hash Union 不会将探测端的行添加到哈希表中，因此它无法从该输入中消除重复项。优化器要么必须保证唯一性，要么在探测端添加一个分组操作符。

Answer 3

UNION 运算符将一个查询中的所有行与另一个查询中的所有行组合在一起，消除重复项并形成一个列表。散列运算符根据上层输入构建一个散列表，并用下层输入探测该表。考虑到执行引擎使用的一次行拉模型，我可以看到这将如何实现 UNION。我想它的工作原理是这样的。

哈希运算符要求一行。反过来，它从上表中拉出一行，对其进行散列并将其与当前列表进行比较。如果在列表中没有找到它是一个新值，它会被添加到哈希列表并返回给调用操作符。这还在继续。最终读取在哈希表中具有匹配项的行。该行被拒绝（UNION 消除重复）并读取下一行。最终上层输入用尽。处理继续处理较低的输入，读取行，拒绝匹配并传递新值，直到它也用完为止。

在什么情况下会使用哈希匹配而不是另一个运算符？简单的答案是因为优化器已经确定，对于给定的数据集，哈希运算符的成本低于可以执行此任务的任何其他运算符的成本。更具体地说（我从连接中推断出）哈希匹配通常发生在没有适当排序的较大数据集上。

这是一个显示用法的示例。我有一个Numbers 表，我已经复制它来创建 dbo.Numbers 和 dbo.Numbers2。

查询

select * from dbo.Numbers

union

select * from dbo.Numbers2

使用合并连接。不出所料，因为两个表都针对查询进行了适当的排序。然而，通过删除一个表上的主键并将其转换为堆，优化器不再保证排序，而是使用哈希运算符：

但是，请注意命名。这是哈希匹配（联合）。将查询更改为连接

select * from dbo.Numbers as n1
inner join dbo.Numbers2 as n2
    on n2.Number = n1.Number

也使用哈希匹配

这次是Hash Match (Inner Join)。每个查询中哈希匹配的属性都不同。

至于表大小，dbo.Numbers 中有 10,000 行，仍然使用哈希匹配。使用 5,000 排序和合并连接（联合）代替。