通往性能优化的JOIN方法说明(4)

使用inner merge join或者option(merge join)强制使用merge join方法。 Kh$,3@:2m  
Qr3 R[]_E  
3. hash join KPfdU!gIA  
h9_I gRAN  
hash join有两个输入：build input（也叫做outer input）和probe input（也叫做inner input），不仅用于inner/left/right join等，象union/group by等也会使用hash join进行操作，在group by中build input和probe input都是同一个记录集。 ?Zux:;v  
) ~t{_ Q  
同nested loop，在执行计划中build input位于上方，probe input位于下方。 k~~/xgd  
!c9\Fqe$S  
hash join操作分两个阶段完成：build（构造）阶段和probe（探测）阶段。 1~F o\A3  
KDr2'{XN  
Build阶段 ]j bq)[Af  
|P^f+Rv  
这个阶段主要构造hash table。在inner/left/right join等操作中，表的关联字段作为hash key；在group by操作中，group by的字段作为hash key；在union或其它一些去除重复记录的操作中，hash key包括所有的select字段。 ~U_XI r  
Y`r_of.t  
Build操作从build input输入中取出每一行记录，将该行记录关联字段的值使用hash函数生成hash值，这个hash值对应到hash table中的hash buckets（哈希表目）。如果一个hash值对应到多个hash buckts，则这些hash buckets使用链表数据结构连接起来。当整个build input的table处理完毕后，build input中的所有记录都被hash table中的hash buckets引用/关联了。 TmVFhRz+09  
,-F4F x  
Probe阶段 [7MJ6d*kte  
rtzT '8NS  
在这个阶段，SQL Server从probe input输入中取出每一行记录，同样将该行记录关联字段的值，使用build阶段中相同的hash函数生成hash值，根据这个hash值，从build阶段构造的hash table中搜索对应的hash bucket。hash算法中为了解决冲突，hash bucket可能会链接到其它的hash bucket，probe动作会搜索整个冲突链上的hash bucket，以查找匹配的记录。 WQ^Sh/-  
M;ob}Lov;  
关于hash算法的细节，可以查看数据结构的一些资料。hash算法主要是用于大数据量的搜索，为了避免每次都象merge join一样在全部的数据中进行搜索匹配，通过合适的 hash函数，先给要搜索的数据根据hash key建立hash值作为索引，在搜索时，先通过hash值定位到一个较小的搜索范围，然后在这个范围中搜索匹配符合条件的结果，以提高效率。 hJ0+x!  
9,aEG6  
SQL Server将数据量较小的表作为build input，尽量使根据build input构造的hash table能够完全放在内存中，这样probe阶段的匹配操作就完全是在内存中进行，这样的hash join叫做In-Memory Hash Join。 0mwYrvEx  
Q*:'v ;  
如果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算法。 l6f{P  ^  
I #E~'AK