图2.循环嵌套连接的第二步

    通过嵌套循环连接也可以看出，随着数据量的增长这种方式对性能的消耗将呈现出指数级别的增长，所以数据量到一定程度时，查询分析器往往就会采用这种方式。

    下面我们通过例子来看一下循环嵌套连接,利用微软的AdventureWorks数据库:

    图3.一个简单的嵌套循环连接   

    图3中ProductID是有索引的，并且在循环的外部表中（Product表）符合ProductID=870的行有4688条，因此，对应的SalesOrderDetail表需要查找4688次。让我们在上面的查询中再考虑另外一个例子,如图4所示。

    图4.额外的列带来的额外的书签查找

    由图4中可以看出，由于多选择了一个UnitPrice列，导致了连接的索引无法覆盖所求查询，必须通过书签查找来进行，这也是为什么我们要养成只Select需要的列的好习惯，为了解决上面的问题，我们既可以用覆盖索引，也可以减少所需的列来避免书签查找。另外，上面符合ProductID的行仅仅只有5条，所以查询分析器会选择书签查找，假如我们将符合条件的行进行增大，查询分析器会倾向于表扫描（通常来说达到表中行数的1%以上往往就会进行table scan而不是书签查找，但这并不绝对），如图5所示。

    图5.查询分析器选择了表扫描

    可以看出，查询分析器此时选择了表扫描来进行连接，这种方式效率要低下很多，因此好的覆盖索引和Select *都是需要注意的地方。另外，上面情况即使涉及到表扫描，依然是比较理想的情况，更糟糕的情况是使用多个不等式作为连接时，查询分析器即使知道每一个列的统计分布，但却不知道几个条件的联合分布，从而产生错误的执行计划,如图6所示。

    图6.由于无法预估联合分布，导致的偏差

   由图6中，我们可以看出，估计的行数和实际的行数存在巨大的偏差，从而应该使用表扫描但查询分析器选择了书签查找，这种情况对性能的影响将会比表扫描更加巨大。具体大到什么程度呢？我们可以通过强制表扫描和查询分析器的默认计划进行比对，如图7所示。

    图7.强制表扫描性能反而更好

    谈到合并连接，我突然想起在西雅图参加SQL Pass峰会晚上酒吧排队点酒，由于我和另外一哥们站错了位置，貌似我们两个在插队一样，我赶紧说:I'm sorry,i thought here is end of line。对方无不幽默的说:”It's OK,In SQL Server,We called it merge join”。

    由上面的小故事不难看出，Merge Join其实上就是将两个有序队列进行连接，需要两端都已经有序，所以不必像Loop Join那样不断的查找循环内部的表。其次，Merge Join需要表连接条件中至少有一个等号查询分析器才会去选择Merge Join。

    Merge Join的过程我们可以简单用下面图进行描述:

    图8.Merge Join第一步

    Merge Join首先从两个输入集合中各取第一行，如果匹配，则返回匹配行。加入两行不匹配，则有较小值的输入集合+1，如图9所示。

    图9.更小值的输入集合向下进1

    用C#代码表示Merge Join的话如代码1所示。

    因此，通常来说Merge Join如果输入两端有序，则Merge Join效率会非常高，但是如果需要使用显式Sort来保证有序实现Merge Join的话，那么Hash Join将会是效率更高的选择。但是也有一种例外，那就是查询中存在order by,group by,distinct等可能导致查询分析器不得不进行显式排序，那么对于查询分析器来说，反正都已经进行显式Sort了,何不一石二鸟的直接利用Sort后的结果进行成本更小的MERGE JOIN？在这种情况下，Merge Join将会是更好的选择。

    另外，我们可以由Merge Join的原理看出，当连接条件为不等式(但不包括!=)，比如说> < >=等方式时，Merge Join有着更好的效率。

    下面我们来看一个简单的Merge Join,这个Merge Join是由聚集索引和非聚集索引来保证Merge Join的两端有序，如图10所示。

    图10.由聚集索引和非聚集索引保证输入两端有序

    当然，当Order By,Group By时查询分析器不得不用显式Sort,从而可以一箭双雕时，也会选择Merge Join而不是Hash Join,如图11所示。

    图11.一箭双雕的Merge Join

    哈希匹配连接相对前面两种方式更加复杂一些，但是哈希匹配对于大量数据，并且无序的情况下性能均好于Merge Join和Loop Join。对于连接列没有排序的情况下(也就是没有索引)，查询分析器会倾向于使用Hash Join。

    哈希匹配分为两个阶段,分别为生成和探测阶段，首先是生成阶段，第一阶段生成阶段具体的过程可以如图12所示。

    图12.哈希匹配的第一阶段

    图12中，将输入源中的每一个条目经过散列函数的计算都放到不同的Hash Bucket中，其中Hash Function的选择和Hash Bucket的数量都是黑盒，微软并没有公布具体的算法，但我相信已经是非常好的算法了。另外在Hash Bucket之内的条目是无序的。通常来讲，查询优化器都会使用连接两端中比较小的哪个输入集来作为第一阶段的输入源。

    接下来是探测阶段，对于另一个输入集合，同样针对每一行进行散列函数，确定其所应在的Hash Bucket,在针对这行和对应Hash Bucket中的每一行进行匹配，如果匹配则返回对应的行。

    通过了解哈希匹配的原理不难看出，哈希匹配涉及到散列函数，所以对CPU的消耗会非常高，此外，在Hash Bucket中的行是无序的，所以输出结果也是无序的。图13是一个典型的哈希匹配，其中查询分析器使用了表数据量比较小的Product表作为生成，而使用数据量大的SalesOrderDetail表作为探测。

    图13.一个典型的哈希匹配连接