数据库性能优化JOIN方法说明(3)

2. merge join

merge join第一个步骤是确保两个关联表都是按照关联的字段进行排序。如果关联字段有可用的索引，并且排序一致，则可以直接进行merge join操作；否则，SQL Server需要先对关联的表按照关联字段进行一次排序（就是说在merge join前的两个输入上，可能都需要执行一个Sort操作，再进行merge join）。

两个表都按照关联字段排序好之后，merge join操作从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则，将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。

在多对多的关联表上执行merge join时，通常需要使用临时表进行操作。例如A join B使用merge join时，如果对于关联字段的某一组值，在A和B中都存在多条记录A1、A2...An、B1、B2...Bn，则为A中每一条记录A1、A2...An，都必须在B中对所有相等的记录B1、B2...Bn进行一次匹配。这样，指针需要多次从B1移动到Bn，每一次都需要读取相应的B1...Bn记录。将B1...Bn的记录预先读出来放入内存临时表中，比从原数据页或磁盘读取要快。

merge join操作本身是非常快的，但是merge join前进行的排序可能会相当耗时（SQL Server最消耗内存和CPU的操作，一个是大数据排序，一个是大数据的hash运算，这都是指查询计划里面的Sort以及Hash相关的操作，例如hash join、使用hash算法实现的Distinct操作等，而不是指你的SQL中order by关键字），尤其是对数据量非常大的记录集，因此导致使用merge join的查询成本变得非常高。对于数据量非常大的表，如果merge join的关联字段可以使用聚集索引，merge join是最快的Join方法之一。因此优化方案是在表结构设计层面良好的设计关联关系和表的索引结构，SQL语句充分利用索引，尽可能减少merge join前的排序操作，减少Bookmark Lookup操作。

一般情况下，如果无法满足nested loop条件，会考虑对merge join方法的评估。merge join的选择，主要是考虑两个输入的数据量，以及分别对应于关联字段是否能够命中索引。例如tableA join tableB，关联字段在两个表中都能命中索引，数据量超过了nested loop的选择范围，则会考虑使用merge join方法。当然，如果tableA和tableB的数据量过大导致评估出来的成本过高，则会放弃merge join而评估hash join了。

使用inner merge join或者option(merge join)强制使用merge join方法。

3. hash join

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都是同一个记录集。

同nested loop，在执行计划中build input位于上方，probe input位于下方。

hash join操作分两个阶段完成：build（构造）阶段和probe（探测）阶段。