MS SQL 查询联接运算系列－－合并联接（Merge Join) - 海峡IT网

与嵌套循环联接不同（支持任何联接谓词），合并联接至少需要一个相等联接谓词．此外，合并联接的输入必须是经过排序的．例如，存在这样一个联接谓词：[Customers].[CustomerId] =[Orders].[CustomerId]，Customoers表和Orders表必须在CustomerID列上进行排序．

我们使用伪代码来描述合并联接的工作过程：

get first row R1 from input 1

get first row R2 from input 2

while not at the end of either input

begin

if R1 joins with R2

begin

output (R1, R2)

get next row R2 from input 2

end

else if R1 < R2

get next row R1 from input 1

else

get next row R2 from input 2

end

和嵌套循环联接不同（inpute表的行数是积），而合并联接中，每一行至多读取一次，总开销是input表的行的总和，因此，对于大量的input表来说，合并联接是最好的选择．

一对多与多对多的合并联接

通过上面的伪代码描述，其实现了一对多的合并联接．当联接了两行后，接下来将丢弃了R2，从input 2中取得下一行．这里其从未从input1取得另一行．换句话说，在input 1中根不存在重复行，另一方面，在input 2中可以存在重复值是可以接受的．

合并联接也支持多对多的联接，在此种情况中，不论何时联接两行时都必须保留input2表每一行的幅本．如果在之后在input1找到重复行，将其重新联接并保存该行数据．另一方面，如果从input1中找到了并不重复的下一行，它将丢弃已保存的．合并联接将这些数据行以Worktable的形式存储在tempdb中，Worketable需要的磁盘空间取决于input2中重复的行数．

一对多的合并联接总是比多对多的合并联接的效率高，主要是它不需要使用worktable.要使用一对多的合并联接，查询优化器能够确定input中的一行确实由唯一的一行组成.一般来说，这意味着在查询计划中，要么存在一个唯一索引，要么存在一个显式运算符（可能是distinct或groupby）来确保input行是唯一的．

排序合并联接(Sort Merge Join)与索引合并联接(Index Merge Join)

对合并联接来说，SQL Server获取排序的input行有两种方法：显式使用sort运算符来排序input行或者使用索引来读取数据行．一般地讲，查询计划使用索引来获取排序的开销要比使用显式排序的开销低．

联接谓词与逻辑联接类型

若联接链已经排序，合并联接支持多个相等联接谓词，特定的顺序次序并不关心两个输入是否是排序的．例如：我们有这样的一个联接谓词：T1.[Col1] = T2.[Col1] and T1.[Col2] =T2.[Col2],只要T1和T2表在(Col1,Col2)或(Col2,Col1)上排序，就可以使用合并联接．

合并联接也支持残留的谓词，如：考虑这样的联接谓词：T1.[Col1] = T2.[Col1] and T1.[Col2] >T2.[Col2].虽然不等谓词不能作为合并联接的一部分，该谓词的相等部分也可以执行合并联接（假定两个表均已在Col1上进行排序）．对于谓词中相等部分的联接的每一行，合并联接然后应用不等谓词，若不等返回真，则联接返回记录行，否则丢弃行．

合并联接支持所有的outer和semi-join联接

示例

创建以下表结构对象：

create table T1 (a int, b int, x char(200))

create table T2 (a int, b int, x char(200))

set nocount on

declare @i int

set @i = 0

while @i < 1000

begin

insert T1 values (@i * 2, @i * 5, @i)

insert T2 values (@i * 3, @i * 7, @i)

set @i = @i + 1

end

打开set statistics profile on开关，执行以下查询：

select *

from T1 join T2 on T1.a = T2.a

option (merge join)

注意，我们在T1和T2表上并没有创建索引，要使用合并联接，查询优化器将使用一个显式的排序运算符对表进行排序，其查询计划如下：  

虽然这两个输入表的行是唯一的，查询优化器并不知道或者也不能强制的，因而我们通过MANY-TO-MANY关键字知道，得到的是多对多的联接．正如先前提到的，每一个输入表只需扫描一次，不关心处理的行数，同时从图中可以看到，T2表经过排序仅返回６６８行记录，为什么不是１０００行记录呢？在处于T2表的６６８行后，合并联接从T2中读取的一行，而这一行要比T1表的任何一行都大，在这一点上，合并联接将从T1表中读取所有剩余的行，一旦到达T1表的尾部，合并联接则退出运算，即不需要读取T2表的所有行．

现在我们在T1表上创建一个索引，看看会发生什么情况？

create unique clustered index T1ab on T1(a, b)

重新执行刚才的查询：

set statistics profile on

select *

from T1 join T2 on T1.a = T2.a

option (merge join)

set statistics profile off  

这一次产生的计划与先前的计划一样，由于我们在T1表上使用了索引来达到排序，在T2表上则需要一个排序操作．注意：既使我们在T1上创建了唯一的聚集索引，我们仍得到的是一个多对多的联接．为什么会是这样呢？索引确保在(a,b)列的唯一性，而并非确保在单一的a列的唯一性．可能在列a上有重复值，这样既便是仅在a列上联接，我们仍旧使用的是多对多的联接．

现在我们在T2表上创建唯一的聚集索引，看看会是什么情况？

create unique clustered index T2a on T2(a)

由于两个表上均创建了索引，因而不需要hint来得到合并联接．

执行以下查询：

set statistics profile on

select *

from T1 join T2 on T1.a = T2.a

set statistics profile off
 

通过上图的信息，由于使用了索引，所以不需要任何排序运算，而且T2上的唯一聚集索引确保了在列a上的唯一性，因而我们现以得到的是一个＂一对多＂的联接．注意在本例中已经找不到MANY-TO-MANY关键字了（在text showplan也没有ONE-TO-MANY关键字）

值得注意的一点是：查询优化器交换了两个输入表的顺序，将T2表首先处理，因而使用的是＂一对多＂的联接．

下面我们看看在两个列上进行联接的情况：

set statistics profile on

select *

from T1 join T2 on T1.a = T2.a and T1.b = T2.b

set statistics profile off  

注意：我们在两个键上使用合并，有趣的是仍使用索引来实现排序．单列在列a上的索引是怎样的？能否在两列(a,b)上进行排序？

由于在T2上的索引是一个唯一的聚集索引，我们可以将列集的任何一个追加到唯一索引键中．

以下是在两列上联接的另一个例子，注意现在不能在两列上进行合并：

set statistics profile on

select *

from T1 join T2 on T1.a = T2.a and T1.b > T2.b

set statistics profile off

其查询计划如下：

 以下是一个full outer联接的例子：

set statistics profile on

select *

from T1 full outer join T2 on T1.a = T2.a

set statistics profile off

其查询计划如下：

 从上面输出的信息发现，现在要处理两个表的所有行（１０００），而不再是仅处理T2的６６８行后就终止联接，由于这里使用的是outer join，它必须读取T2的所有行和与该联接不匹配的那些NULL行．