ITPub博客

首页 > Linux操作系统 > Linux操作系统 > MS SQL 查询联接运算系列--合并联接(Merge Join)

MS SQL 查询联接运算系列--合并联接(Merge Join)

原创 Linux操作系统 作者:bigholy 时间:2008-11-17 21:10:14 0 删除 编辑

与嵌套循环联接不同(支持任何联接谓词),合并联接至少需要一个相等联接谓词.此外,合并联接的输入必须是经过排序的.例如,存在这样一个联接谓词:[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中可以存在重复值是可以接受的.

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

一对多的合并联接总是比多对多的合并联接的效率高,主要是它不需要使用worktable.要使用一对多的合并联接,查询优化器能够确定input中的一行确实由唯一的一行组成.一般来说,这意味着在查询计划中,要么存在一个唯一索引,要么存在一个显式运算符(可能是distinct或group by)来确保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表经过排序仅返回668行记录,为什么不是1000行记录呢?在处于T2表的668行后,合并联接从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

其查询计划如下:

 从上面输出的信息发现,现在要处理两个表的所有行(1000),而不再是仅处理T2的668行后就终止联接,由于这里使用的是outer join,它必须读取T2的所有行和与该联接不匹配的那些NULL行.

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/355374/viewspace-496183/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2008-11-08

  • 博文量
    43
  • 访问量
    84465