哈希聚合救助

Question

在聊天讨论中出现的一个问题：

我知道散列连接救助在内部切换到某种嵌套循环。

SQL Server 为散列聚合救助做了什么（如果它可以发生的话）？

Answer 1

散列连接和散列聚合在内部都使用相同的运算符代码，尽管散列聚合仅使用单个（构建）输入。的基本操作散列集合体是由Craig弗里德曼描述：

与散列连接一样，散列聚合需要内存。在使用散列聚合执行查询之前，SQL Server 使用基数估计来估计我们需要多少内存来执行查询。使用散列连接，我们存储每个构建行，因此总内存需求与构建行的数量和大小成正比。联接的行数和联接的输出基数对联接的内存要求没有影响。对于散列聚合，我们为每个组存储一行，因此总内存需求实际上与输出组或行的数量和大小成正比。如果按列分组的唯一值越少，组越少，我们需要的内存就越少。如果我们有更多的 group by column(s) 和更多组的唯一值，我们需要更多的内存。

他继续谈论哈希递归：

那么，如果内存不足会发生什么？同样，就像散列连接一样，如果内存不足，我们必须开始将行溢出到 tempdb。我们溢出一个或多个存储桶或分区，包括任何部分聚合的结果以及散列到溢出存储桶或分区的任何其他新行。虽然我们不尝试聚合溢出的新行，但我们会散列它们并将它们分成几个桶或分区。一旦我们完成了所有输入组的处理，我们输出完成的内存组并通过回读和一次聚合一个溢出分区来重复算法。通过将溢出的行划分为多个分区，我们减小了每个分区的大小，从而降低了算法需要重复多次的风险。

救助

散列救助的文档很少，但 Nacho Alonso Portillo 在强制救助之前散列迭代器的最大递归级别是多少？

该值是一个常量，在产品中进行了硬编码，其值为五 (5)。这意味着，在散列扫描运算符对任何不适合工作区授予内存的给定子分区采用基于排序的算法之前，必须已经进行了五次将原始分区细分为更小的分区的先前尝试。

该“散列扫描运算符”中提到存在对内部类的引用CQScanHash在sqlmin.dll。这个类负责我们在执行计划中看到的哈希运算符的实现（所有形式，包括部分聚合和流不同）。

救助算法

这将我们带到了您的问题的核心 - 救助算法究竟是做什么的？它是“基于排序”还是基于“某种嵌套循环”？

这可以说是两者兼而有之，这取决于您的观点。当哈希递归达到第 5 级时，内存中的哈希分区从哈希表变为哈希值上最初为空的 b 树索引。单个先前溢出的散列分区中的每一行都在 b 树索引中查找，并根据需要插入（新组）或更新（维护聚合）。

这一系列对 b 树的无序插入同样可以被视为插入排序或索引嵌套循环查找。

在任何情况下，这种回退算法都可以保证最终完成而不分配更多内存。如果 b-tree 的可用空间不足以容纳来自溢出分区的所有分组键和聚合，则可能需要多次传递。

一旦可用于保存 b 树索引的内存耗尽，任何其他行（来自当前溢出分区）将发送到单个新tempdb分区（保证较小），并根据需要重复该过程。溢出级别保持在 5，因为散列递归已经结束。使用未记录的跟踪标志 7357 可以观察到一些处理细节。