浅谈SQLServer中的三种物理连接操作

介绍在SQLServer中，我们经常看到的表与表之间的InnerJoin和OuterJoin，引擎会根据选择的列和数据上是否有索引来执行，将所选数据的选择性转换为三种物理连接之一：LoopJoin、MergeJoin和HashJoin。理解这三种物理连接是理解连接表时如何解决性能问题的基础。下面我分别介绍一下这三种连接的原理和适用场景。嵌套循环连接（NestedLoopJoin）循环嵌套连接是最基本的连接。顾名思义，需要循环嵌套。嵌套循环是三种方法中最支持不等式连接的方式。这种连接方式的流程可以简单的用下图表示：图1.循环嵌套连接的第一步图2.循环嵌套连接的第二步从以上两图不难看出，loopnestedconnectionsearch内循环表的次数等于外循环的行数，当外循环没有更多行时，循环嵌套结束。另外也可以看出，这种连接方式要求内层循环表是有序的（即有索引），外层循环表的行数要小于内层循环表的行数循环，否则查询分析器更倾向于HashJoin（本文后面会讨论）。从嵌套循环连接也可以看出，随着数据量的增加，这种方式的性能消耗会呈指数增长，所以当数据量达到一定程度时，查询分析器往往会采用这种方式。下面通过一个例子来看看循环嵌套连接，使用微软的AdventureWorks数据库：图3.一个简单的嵌套循环连接图3ProductID被索引，在循环的外层表（Product表）中符合ProductID的有4688个rows=870，因此对应的SalesOrderDetail表需要查找4688次。让我们考虑上述查询中的另一个示例，如图4所示。图4.额外列带来的额外书签查找从图4中可以看出，由于选择了额外的UnitPrice列，连接索引无法覆盖请求查询，必须通过书签搜索，这就是为什么我们需要养成只选择所需列的好习惯。为了解决上述问题，我们可以使用覆盖索引或者减少所需的列来避免书签查找。此外，只有5行与上面的ProductID匹配，因此查询分析器将选择书签搜索。如果我们增加符合条件的行数，查询分析器会倾向于扫描表（通常达到表行数的1%以上往往会进行表扫描而不是书签搜索，但这不是绝对的），如如图5所示。图5.查询分析器选择表扫描。可以看出此时查询分析器选择了表扫描连接。这种方法效率低很多，所以一个好的覆盖索引和Select*是需要注意的地方。另外，上面的情况即使涉及到表扫描，也是比较理想的情况。更糟糕的情况是，当使用多个不等式作为连接时，即使查询分析器知道每一列的统计分布，也不知道几个条件的条件。联合分布，导致执行计划错误，如图6。图6无法估计联合分布导致的偏差从图6可以看出，估计的行数和实际执行的行数存在巨大偏差实际行数，所以应该使用表扫描，但是查询分析器选择了书签查找，这种情况对性能的影响会比表扫描大。它有多大？我们可以通过强制表扫描将其与查询分析器的默认计划进行比较，如图7所示。图7.强制表扫描性能更好#p#MergeJoin(MergeJoin)当谈到合并连接时，我突然想起我晚上在西雅图的SQLPass峰会上在酒吧排队点酒。因为我和另一个哥们站错了位置，好像我们两个在插队，所以我赶紧说：对不起，我以为这里是队尾。对方都幽默地说：“没关系，在SQLServer里，我们叫mergejoin”。从上面的故事不难看出，MergeJoin其实就是把两个有序的队列连接起来，而且两端都需要有序，所以不需要像LoopJoin一样在循环里面不断的找表。其次，MergeJoin要求表连接条件中至少有一个等号查询分析器选择MergeJoin。MergeJoin的过程可以用下图简单描述：图8.MergeJoinMergeJoin的第一步是从两个输入集合中分别提取第一行，如果匹配则返回匹配的行。如果添加了两条不匹配的行，那么值较小的输入集+1，如图9所示。图9.值较小的输入集往下减1如果MergeJoin表示在C#代码中，它显示在代码1中。publicclassMergeJoin{//AssumethatleftandrightarealalreadysortedpublicstaticRelationSort(Relationleft,Relationright){Relationoutput=newRelation();while(!left.IsPastEnd()&&!right.IsPastEnd()){if(left.Key==right.Key){output.Add(left.Key);左.Advance();对.Advance();}elseif(left.Keyright.Key)right.Advance();}返回输出；}}代码1.MergeJoin的C#代码表示因此，一般来说，如果MergeJoin的输入端是有序的，那么MergeJoin的效率会非常高，但是如果需要使用显式Sort来保证顺序的话实现了MergeJoin，那么HashJoin会是一个更高效的选择。但是也有一个例外，就是查询中存在orderby,groupby,distinct等可能会导致查询分析器进行显式排序，所以对于查询分析器来说，无论如何已经进行了显式排序，为什么不一石二鸟直接用Sort后的结果进行MERGEJOIN成本更低呢？这种情况下，MergeJoin会是更好的选择。另外，从MergeJoin的原理可以看出，当连接条件不等（但不包括!=），比如><>=等时，MergeJoin效率更高。让我们来看看一个简单的MergeJoin。这个MergeJoin使用聚集索引和非聚集索引来保证MergeJoin的两端是有序的，如图10所示。图10.聚集索引和非聚集索引保证输入的两端是有序的被订购。当然，在OrderBy、GroupBy时，查询分析器必须使用显式的Sort，这样才能一箭双雕，而且还要选择MergeJoin而不是HashJoin，如图11所示。图11.MergeJoin一石二鸟。HashJoinHashJoin比前两种方法复杂，但是HashMatch在数据量大和无序的情况下比MergeJoin和LoopJoin表现更好。.对于join列未排序（即没有索引）的情况，查询分析器会倾向于使用HashJoin。哈希匹配分为两个阶段，分别是生成阶段和检测阶段。首先是生成阶段，finalphase生成阶段的具体过程如图12所示。图12散列匹配的第一阶段图12中，输入源中的每一个条目都是通过散列函数计算得到的，放在不同的HashBucket中，这里HashFunction的选择和HashBuckets的个数都是Blackbox，具体算法微软没有公布，但相信已经是很不错的算法了。此外，哈希桶中的条目是无序的。一般来说，查询优化器会使用连接两端较小的输入集作为最后阶段的输入源。下一步是检测阶段。对于另外一个输入集合，同样对每一行进行哈希函数，以确定它应该在的哈希桶中。将这一行与对应哈希桶中的每一行进行匹配。如果匹配，则返回相应的行。通过了解哈希匹配的原理，不难看出哈希匹配涉及到哈希函数，所以CPU消耗会非常高。另外，HashBucket中的行是乱序的，所以输出的结果也是乱序的。图13是一个典型的哈希匹配，其中查询分析器使用表数据量相对较少的Product表作为生成器，使用数据量较大的SalesOrderDetail表作为探针。图13.典型的哈希匹配连接上面的情况是内存可以容纳生成阶段所需的内存。如果内存吃紧，还会涉及到Gracehashmatching和recursivehashmatching，可能会被ToTempDB吃掉很多IO。这里就不细说了，有兴趣的同学可以移步：http://msdn.microsoft.com/zh-cn/library/aa178403(v=SQL.80).aspx。总结下面用一个表格来简单总结一下这几种连接方式的消耗和使用场景：嵌套循环连接合并连接哈希连接适用场景外循环小，内存循环条件列有序。两端都是有序的。数据量很大。,andnoindexCPUlow(如果没有显式排序)high内存lowlow(如果没有显式排序)highIO可能很高tuning需要说的是，在很多情况下，当过滤条件很多，表连接多的时候，查询分析器可能就没那么聪明了，所以了解这些连接方式对于定位问题就变得尤为重要。此外，我们还可以从业务角度通过缩小查询范围来降低join性能不佳的可能性。原文链接：http://www.cnblogs.com/CareySon/archive/2013/01/09/2853094.html