主页 / dba / 问题 / 167086
Accepted
sam.bishop
Asked: 2017-03-14 17:17:59 +0800 CST

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

  • 772

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

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

sql-server optimization

3 个回答

  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 ║
╚════════════╩══════════╩══════════════╝
    • 7
  2. Best Answer

    一个示例查询会很棒。

    使用数字表（整数 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

    哈希联合

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

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

    这个怎么运作

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

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

    • 7

  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

    还使用哈希匹配

    在此处输入图像描述

    这次是哈希匹配（Inner Join）。每个查询中哈希匹配的属性不同。

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

    • 5

相关问题