通往性能优化的天堂-地狱 JOIN方法说明

　　Probe阶段

　　在这个阶段，SQL Server从probe input输入中取出每一行记录，同样将该行记录关联字段的值，使用build阶段中相同的hash函数生成hash值，根据这个hash值，从build阶段构造的hash table中搜索对应的hash bucket。hash算法中为了解决冲突，hash bucket可能会链接到其它的hash bucket，probe动作会搜索整个冲突链上的hash bucket，以查找匹配的记录。

　　关于hash算法的细节，可以查看数据结构的一些资料。hash算法主要是用于大数据量的搜索，为了避免每次都象merge join一样在全部的数据中进行搜索匹配，通过合适的 hash函数，先给要搜索的数据根据hash key建立hash值作为索引，在搜索时，先通过hash值定位到一个较小的搜索范围，然后在这个范围中搜索匹配符合条件的结果，以提高效率。

　　SQL Server将数据量较小的表作为build input，尽量使根据build input构造的hash table能够完全放在内存中，这样probe阶段的匹配操作就完全是在内存中进行，这样的hash join叫做In-Memory Hash Join。

　　如果build input记录数非常大，构建的hash table无法在内存中容纳时，SQL Server分别将build input和probe input切分成多个分区部分（partition），每个partition都包括一个独立的、成对匹配的build input和probe input，这样就将一个大的hash join切分成多个独立、互相不影响的hash join，每一个分区的hash join都能够在内存中完成。SQL Server将切分后的partition文件保存在磁盘上，每次装载一个分区的build input和probe input到内存中，进行一次hash join。这种hash join叫做Grace Hash Join，使用的Grace Hash Join算法。

　　伴随着大数据的hash join运算，还会有standard external merge sorts、multiple merge levels、multiple partitioning steps、multiple partitioning levels，SQL Server还可能会使用Recursive Hash Join等算法或其它的优化手段。