数据库性能优化JOIN方法说明(4)
Build阶段
这个阶段主要构造hash table。在inner/left/right join等操作中，表的关联字段作为hash key；在group by操作中，group by的字段作为hash key；在union或其它一些去除重复记录的操作中，hash key包括所有的select字段。
Build操作从build input输入中取出每一行记录，将该行记录关联字段的值使用hash函数生成hash值，这个hash值对应到hash table中的hash buckets（哈希表目）。如果一个hash值对应到多个hash buckts，则这些hash buckets使用链表数据结构连接起来。当整个build input的table处理完毕后，build input中的所有记录都被hash table中的hash buckets引用/关联了。
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等算法或其它的优化手段。
hash join一般都用于大数据量的操作，例如join中某个表的数据达到一定程度或者无法一次加载到内存，另外如果你的关联字段在两个join表中都不能够命中索引，也是使用hash join来处理。因此一般情况下，hahs join处理代价非常高，是数据库服务器内存和CPU的头号杀手之一，尤其是涉及到分区（数据量太大导致内存不够的情况，或者并发访问很高导致当前处理线程无法获得足够的内存，那么数据量不是特大的情况下也可能需要进行分区），为了尽快的完成所有的分区步骤，将使用大量异步的I/O操作，因此期间单一一个线程就可能导致多个磁盘驱动器出于忙碌状态，这很有可能阻塞其它线程的执行。
使用inner hash join或者option (hash join)强制使用hash join方法。
建议
三种join方法，都是拥有两个输入。优化的基本原则：1. 避免大数据的hash join，尽量将其转化为高效的merge join、nested loop join。可能使用的手段有表结构设计、索引调整设计、SQL优化，以及业务设计优化。例如冗余字段的运用，将统计分析结果用service定期跑到静态表中，适当的冗余表，使用AOP或类似机制同步更新等。2. 尽量减少join两个输入端的数据量。这一点比较常犯的毛病是，条件不符合SARG（光这一点就有很多高超的技巧可以发挥），在子查询内部条件给的不充分（SQL过于复杂情况下SQL Server查询优化器经常犯傻，写在子查询外部的条件不会被用在子查询内部，影响子查询内部的效率或者是跟子查询再join时候的效率）。另外也是设计、业务端尽量限制这两个输入的数据量了。
关于业务设计方面的优化，参考以前写的一篇post：系统分析设计 一个JOIN问题解决方案的感想 重视业务分析设计。
补充：关于SQL Server 2005
大致看了下SQL Server 2005，执行计划的显示确实有一些不一样，但主要部分或者说原理上是差不多的，不会有多少偏差。上面的示例SQL，在tableB上面使用非聚集索引时，SQL Server 2005的执行计划。
一个主要的不同点是SQL Server 2000下面Bookmark Lookup操作，在2005下面显示成一个RID Lookup操作 + 一个Nested Loops操作实现，其实这也是很好理解的，可以说这样显示执行计划更合理一点，让你一看到这个操作，就知道它是通过一个循环机制到tableB中获取实际数据。
另外一点是，将鼠标移动到执行计划的图标上面后，弹出的提示信息的一些改变，例如2005里面会显示每个操作的输出列表（output list），而我上面的文章中基本都使用“输出数据结构”这样一个词汇在表达。通过查看output list，你更能明白RID Lookup（Bookmark Lookup）这样的操作存在的理由了。
最后，2005里面可以将图形显示的执行计划保存下来，以后可以打开再以图形方式进行查看分析，这个在2000下面是不行的，2000只能保存执行计划的文本。这样一些小功能对于分析SQL性能非常有用，在图形界面上的分析更直观。