图12中,将输入源中的每一个条目经过散列函数的计算都放到不同的Hash Bucket中,其中Hash Function的选择和Hash Bucket的数量都是黑盒,微软并没有公布具体的算法,但我相信已经是非常好的算法了。另外在Hash Bucket之内的条目是无序的。通常来讲,查询优化器都会使用连接两端中比较小的哪个输入集来作为第一阶段的输入源。
接下来是探测阶段,对于另一个输入集合,同样针对每一行进行散列函数,确定其所应在的Hash Bucket,在针对这行和对应Hash Bucket中的每一行进行匹配,如果匹配则返回对应的行。
通过了解哈希匹配的原理不难看出,哈希匹配涉及到散列函数,所以对CPU的消耗会非常高,此外,在Hash Bucket中的行是无序的,所以输出结果也是无序的。图13是一个典型的哈希匹配,其中查询分析器使用了表数据量比较小的Product表作为生成,而使用数据量大的SalesOrderDetail表作为探测。
图13.一个典型的哈希匹配连接
上面的情况都是内存可以容纳下生成阶段所需的内存,如果内存吃紧,则还会涉及到Grace哈希匹配和递归哈希匹配,这就可能会用到TempDB从而吃掉大量的IO。这里就不细说了。
总结
下面我们通过一个表格简单总结这几种连接方式的消耗和使用场景:
嵌套循环连接 | 合并连接 | 哈希连接 | |
适用场景 | 外层循环小,内存循环条件列有序 | 输入两端都有序 | 数据量大,且没有索引 |
CPU | 低 | 低(如果没有显式排序) | 高 |
内存 | 低 | 低(如果没有显式排序) | 高 |
IO | 可能高可能低 | 低 | 可能高可能低 |