浅谈SQL Server查询优化器中的JOIN算法

    使用小结：

　　如前所述，可以考虑在两个结果集都很大情况下使用，最好能有聚集索引保证已经排序完毕。而在实际应用中，我们经常会与遇到的主键-外键关系就是 Sort-Merge的一个很好的应用。这种情况下，一般两列都会有聚集索引(已排序)而且一对多的关系保证了至少有一列没有重复值，这种情况下， Sort-Merge的性能是三种里面最好的。

　　另外，如果要求查询的SQL语法本身就要求GROUP BY、ORDER BY、CUBE等运行，则查询语法整体本来就要做排序，因此可以重用排序结果，此时Merge也是不错的选择。

　　3. Hash Join (哈希联结)

 Hash Join在本质上类似于两列都有重复值时的Sort-Merge的处理思想——分区(patitioning)。但它们也有区别：Hash Join通过哈希来分区(每一个桶就是一个分区)而Sort-Merge通过排序来分区(每一个重复值就是一个分区)。

　　值得注意的是，Hash Join与上述两种算法之间的较大区别同时也是一个较大限制是它只能应用于等值联结(equality join)，这主要是由于哈希函数及其桶的确定性及无序性所导致的。

　　算法：

　　基本的Hash Join算法由以下两步组成：

　　(1) Build Input Phase： 基于JOIN字段，使用哈希函数h2为较小的S集合构建内存中(in-memory)的哈希表，相同键值的以linked list组成一个桶(bucket)

　　(2) Probe Input Phase： 在较大的R集合上对哈希表进行核对以完成联结。其中核对操作包括：

　　代价：

　　值得注意的是对于大集合R的每个元组 r ，hash bucket中对应 r 的那个bucket中的每个元组都需要与 r 进行比较，这也是算法最耗时的地方所在。

　　CPU开销是O (m + n * b) b是每个bucket的平均元组数量。

　　使用小结：

　　一般来说，查询优化器会首先考虑Nested Loop和Sort-Merge，但如果两个集合量都不小且没有合适的索引时，才会考虑使用Hash Join。

　　Hash Join也用于许多集合比较操作，inner join、left/right/full outer join、intersect、difference等等，当然了，需要保证都是等值联结。

　　另外，Hash Join的变种能够移除重复和进行分组，它只使用一个输入，兼做Build和Probe的角色。

　  其实产品级的优化器一般都改进了这些基本算法，而改进过的版本的确有较大的性能提升。在这里只是给需要判断执行计划优劣或者研究查询优化器实现的兄弟提供原理方面的介绍，在实际应用中我们还得结合丰富的statistics作出准确的判断。