SQL Server中的三种Join方式

 

1.测试数据准备

参考：Sql Server中的表访问方式Table Scan, Index Scan, Index Seek 这篇博客中的实验数据准备。这两篇博客使用了相同的实验数据。

2.SQL Server中的三种Join方式

在Sql Server中，每一个join命令，在内部执行时，都会采用三种更具体的join方式来运行。这三种join的方法是：nested loops join、merge join和hash join。这三种方法，没有哪一种是永远最好的，但是都有其最适合的上下文。SQL Server会根据两个结果集所基于的表格结构，以及结果集的大小，选择最合适的联接方法。当然，用户也可以在语句里指定join的方法，也就是添加join hint，SQL Server会尽力尊重你的选择。但是，有些查询按照指定的join方法可能做不出执行计划，SQL Server会报错。而且建议不要使用sql hint，因为SqlServer的选择基本上都是正确的

sql server有三种join方式，那么就有三种join hint，如下所示就是按照三种join hint执行的联结以及其所对应的执行计划，

--nested loop join
select count(b.SalesOrderID)
from dbo.SalesOrderHeader_test a --outer table
inner loop join dbo.SalesOrderDetail_test b --inner table
on a.SalesOrderID = b.SalesOrderID
where a.SalesOrderID >43659 and a.SalesOrderID< 53660
go

--merge join
select count(b.SalesOrderID)
from dbo.SalesOrderHeader_test a
inner merge join dbo.SalesOrderDetail_test b
on a.SalesOrderID = b.SalesOrderID
where a.SalesOrderID >43659 and a.SalesOrderID< 53660
go

-- hash join
select count(b.SalesOrderID)
from dbo.SalesOrderHeader_test a
inner hash join dbo.SalesOrderDetail_test b
on a.SalesOrderID = b.SalesOrderID
where a.SalesOrderID >43659 and a.SalesOrderID< 53660
go

--不加join hint,使用的是hash match
select count(b.SalesOrderID)
from dbo.SalesOrderHeader_test a --outer table
inner join dbo.SalesOrderDetail_test b --inner table
on a.SalesOrderID = b.SalesOrderID
where a.SalesOrderID >43659 and a.SalesOrderID< 53660
go

执行计划：

2.1Nested Loop Join

Nested Loops是一种最基本的联接方法，被SQL Server广泛使用。对于两张要被join在一起的表格，SQL Server选择一张做Outer table(在执行计划的上端，SalesOrderHeader_test)，另外一张做Inner table(在执行计划的下端，SalesOrderDetail_test)。如下图所示

其算法是：

foreach(row r1 in outer table) --尽量小
    foreach(row r2 in inner table)
        if( r1, r2 符合匹配条件 )
            output(r1, r2);

以上面的查询为例子，SQL Server选择了SalesOrderHeader_test作为Outer table，SalesOrderDetail_test作为Inner table。首先SQL Server在SalesOrderHeader_test上做了一个clustered index seek，找出每一条a.SalesOrderID >43 659 and a.SalesOrderID< 53 660的记录。每找到一条记录，SQL Server都进入Inner table，找能够和它join返回数据的记录（a.SalesOrderID = b.SalesOrderID）。由于Outer Table SalesOrderHeader_test上有10 000条SalesOrderID在43 659和53 660的记录，每一条SQL Server都要到inner table里去找能join的row，所以inner table SalesOrderDetail_test被扫描了10 000次，在执行计划中的体现就是：Clustered index seek返回的row有10000，而executes的次数是1。而Index Seek被执行的次数executes为10000，这是因为inner table被扫描了10000次。外表的rows决定了内表的executes。

Nested Loops Join是一种基本的联接方式。它不需要SQL Server为join建立另外的数据结构，所以也比较省内存空间，也无须使用tempdb的空间。它适用的Join类型是非常广泛的。有些联接是merge和hash做不了的，但Nexted Loops可以做。所以这种联接方式的优点是很明显的，但是它的缺点也很明显。

1. 算法的复杂度等于Inner table乘以Outer table。

如果是两张表比较大，尤其是Outer table比较大的情况，Inner table会被扫描很多次。这时候的算法复杂度增加得非常快，总的资源消耗量也会增加得很快。所以Nested Loops Join比较适合于两个比较小的结果集做联接，或者至少是Outer table的结果集比较小。

像前面的那个例子，由于Outer table SalesOrderHeader_test的数据集有10 000条记录，所以Inner table就会被扫描10 000次。这是不太划算的。如果让SQL Server自己选择而不加join hint，SQL Server不会选择nested loops的联接方式。

2. Outer table的数据集最好能够事先排序好，以便提高检索效率。

如果数据集能够事先排序好，做Nested loops当然能够更快一些。当然如果没有排序，Nested Loops Join也能做得出来，就是cost会大大增加。

3. Inner table上最好有一个索引，能够支持检索。

nested loop算法会逐一拿着Outer table里的每一个值，在Inner table里找所有符合条件的记录，所以在Inner table里找得快慢也能很大程度上影响整体的速度。如果进行检索的字段上有一个索引，查找的速度会大大加快，Inner table数据集稍微大一点也没关系。否则就要每次做整个数据集的扫描，是很浪费资源的。

总之，Nested Loops Join对数据集比较小的联接，效率是最高的，因此在SQL Server里使用得很广泛。当SQL Server发现能够选择一个很小的数据集作为Outer table的时候，它往往会选择Nested Loops，性能也比较好。但是Nested Loops Join对数据集大小的敏感性太强。如果SQL Server预测发生错误，用大的数据集做Outer table，性能会急剧下降。很多语句性能问题，都是由于这个造成的。

2.2Merge join

在前面提到过，Nested Loops Join只适用于Outer table数据集比较小的情况。如果数据集比较大，SQL Server会使用其他两种联接方式，Merge Join和Hash Join。如果需要连接的两张表已经联接列上排序（例如，如果它们是通过扫描已排序的索引获得的），则Merge Join是最快的联接操作。如果两个联接输入都很大，而且这两个输入的大小差不多，则预先排序的Merge Join提供的性能与Hash Join相近。但是，如果这两个输入的大小相差很大，则Hash Join操作通常快得多。

Merge Join算法如下：

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 

也就是说，从两边的数据集里各取一个值，比较一下。如果相等，就把这两行联接起来返回。如果不相等，那就把小的那个值丢掉，按顺序取下一个更大的。两边的数据集有一边遍历结束，整个Join的过程就结束。所以整个算法的复杂度是O(M+N)，这个比起Nested Loops Join两个数据集相乘的复杂度O(M*N)，的确是小了很多。所以在数据集大的情况下，Merge Join的优势是非常明显的。

但是从上面的Merge Join算法看出，它的局限性也很强，所以在实际的语句里，使用得并不是那么的普遍。它的局限性主要有：

1. 做联接的两个数据集必须要事先按照Join的字段排好序。

这个先决条件是Merge Join算法的基础，而对大的数据集排序本来就是一件比较复杂的事情。不过有些数据集是基于Join的那个字段上的索引得到的，所以能够不费额外的资源就排好了顺序，这时候使用Merge Join可能就比较合适。例如范例查询，两个数据集都是根据在SalesOrderID字段的索引上seek出来的，所以不需要再做排序。范例查询的执行计划如下所示：

从查询计划中我们可以看到merge join的范例查询可以分解成两个查询，

select * from dbo.SalesOrderHeader_test where SalesOrderID >43659 and SalesOrderID< 53660
select count(SalesOrderID) from dbo.SalesOrderDetail_test where SalesOrderID >43659 and SalesOrderID< 53660

第一个查询使用clustered index seek，因为有聚集索引，所以查询结果肯定按照聚集索引列SalesOrderID排序。第二个查询虽然SalesOrderID不是SalesOrderDetail_test表的聚集索引键，但是因为在SalesOrderDetail_test表上有非聚集索引，而且只需要查询count(SalesOrderID)，所以之在非聚集索引上面查询，查询结果也是按照SalesOrderID排序。从而最终两个结果集都是按照SalesOrderID排序的。

2. Merge Join只能做以“值相等”为条件的联接，而且如果数据集可能有重复的数据，Merge Join要采用Many-To-Many这种很费资源的联接方式。

在SQL Server扫描数据集时，如果数据集1有两个或者多个记录值相等，SQL Server必须得把数据集2里扫描过的数据暂时建立一个数据结构存放起来，万一数据集1里下一个记录还是这个值，那还有用。这个临时数据结构被称为“Worktable”，会被放在tempdb或者内存里。这样做很耗资源，所以在上面的执行计划里，Merge Join的两句子句的Subtree Cost分别为0.202和0.109。但Many-To-Many的Join子句Subtree Cost是5.051。也就是说，Join自己的cost是4.74（5.051 – 0.202 – 0.109 =4.74)）。这是一个不小的cost。

如果在[SalesOrderHeader_test]表的SalesOrderID列上再添加一个Unique的索引（或者将原来的聚集索引改成唯一聚集索引），

--SalesOrderID列上原本有了聚集索引，现在再添加一个唯一索引
--如果SalesOrderID列上有重复之，添加唯一索引会失败。
create unique index idx_uniq_SalesOrderID on SalesOrderHeader_test(SalesOrderID);

SQL Server就知道数据集1（SalesOrderHeader_test）的值不会重复的，也就不需要做Many-To-Many Join。执行计划果然发生变化，预估的cost降低了一个数量级。

总结:

上面这两个限制，影响了Merge Join的使用范围。但是Merge Join的一个独特好处是，返回的数据集也是按照顺序排好的。这里顺便提一下结果集的顺序问题。我们在使用同一个查询的时候，会发现结果集有时候是按我们想要的顺序排列，有时候又不是。或者是在SQL Server 2000里是这个顺序，到了SQL Server 2005/2008又是另外顺序。在讲完了Merge Join以后，我们就能够明白，同样做Join操作，Merge Join就能够按顺序返回，但是Nested Loops就不能。只要语句里没有指定“Order By”，SQL Server选取哪一种Join并不需要考虑结果集是否是按顺序返回的。它更多考虑的是哪一种Join算法代价最小。如果数据量和数据分布让SQL Server觉得Nested Loops划算，它就转用Nested Loops。结果集就不按顺序返回了，但是SQL Server并没有做错什么。一句话，如果想要结果集按照某个顺序返回，就要明确地用“order by”指定。如果没有指定，哪怕一模一样的查询，结果集顺序这一次和上一次不一样是很正常的。因为数据发生变化，或者参数不同，SQL Server很可能就会选择不同的执行计划。

2.3Hash Join

顾名思义，Hash Join就是利用哈希算法作匹配的联接算法。具体的哈希算法可以参考我的另外一篇博客：Hashmap实现原理。简单来说，哈希算法分成两步，“构建哈希桶(Buildhash bucket)”和“探测哈希桶中的值(Probe hash bucket)”。在“Build”阶段，SQL Server选择两个要做Join的数据集中的一个，根据记录的值建立起一张在内存中的Hash表。然后在“Probe”阶段，SQL Server选择另外一个数据集，将里面的记录值依次带入，返回符合条件可以做联接的行。具体的算法是：

for each row R1 in the build table
   begin
      calculate hash value on join key(s) of R1
      insert R1 into the appropriate hash bucket
   end
for each row R2 in the probe table
   begin
      calculate hash value on join key(s) of R2
      for each row R1 in the corresponding hash bucket
         if R1 joins with R2
            output (R1, R2)
   end

算法描述：

1. 选择两个需要join的表中的一个a，对于a中的每一个记录R1，计算其联接列的hash值，然后根据hash值将R1插入到hash bucket当中。
2. 选择两外一张表b，对于b中的每一条记录R2，我们也计算其联接列的hash值，然后去hash bucket上查找。如果hash bucket上有R1能够跟R2进行连接，那么久输出(R1,R2)的联接结果，可能有多个R1的记录。

其结构可以参考下图所示：

上面的0-15就是hash bucket，而右边的那些节点就是R1。

和其他两种Join算法比，Hash Join的优点是很明显的。

1. 它的算法复杂度就是分别遍历两边的数据集各一遍。

这对于数据集比较大的Join，其复杂度能够控制在合理的范围以内。相对于已经排好序的Merge Join，Hash Join多了一步计算Hash值，因此复杂度要比Merge Join要高一些，但是比Nested Loops要简单许多。

2. 它不需要数据集事先按照什么顺序排序，也不要求上面有索引。

因为联接使用的是哈希算法，对输入没有限制，不需要SQL Server像为Merge Join一样，事先准备好一个排过序的输入。由于做Hash Join总是要把两边的数据集都要扫描一遍，所以有没有索引其实帮助也不大。没有索引，对性能也不会有太大的影响。

3. 可以比较容易地升级成使用多处理器的并行执行计划。

因为算法没有要求代入的数据有任何次序，所以用多个CPU并行完成是比较容易的。

总之，Hash Join是一种适合于要Join的数据集比较大，上面没有合适的索引的情况。像刚才的那个例子，是一个10 000条记录的数据集和一个50 577条记录的数据集之间的联接。使用Nested Loops要循环10 000次，代价比较高。SQL Server预估出来的cost是2.233。使用Merge Join时，虽然两个数据集都是排序好的，但是由于可能有重复的值，SQL Server只好使用Many-To-Many的join方式，cost也很高，预估是5.882。使用Hash Join，预估的cost是0.727，比前两个都小。所以如果不代入Join Hint的话，SQL Server默认会对这句话使用Hash Join。

但是，Hash Join并不是一种最优的Join算法，只是SQL Server在输入不优化（Join的数据集比较大，或上面没有合适的索引）的时候的一种不得已选择。这是因为Hash Join是一种最耗资源的Join算法。它在做Join之前，要先在内存里建立一张Hash表。建立的过程需要CPU资源，Hash表需要用内存或tempdb存放。而Join的过程也要使用CPU资源来计算（“Probe”）。如果同时有很多用户在用Hash算法做Join，对SQL Server的整体负担是比较重的。从降低SQL Server整体负荷的角度考虑，还是要尽量降低Join输入的数据集的大小，配以合适的索引，引导SQL Server尽量使用Nested Loops Join或者Merge Join。

下面用表对这三种Join方式作一下比较。

	Nested Loops Join	Merge Join	Hash Join
最适合于	相对较小的两个数据集，inner table在做Join的字段上有一个索引	输入数据集大小中等或较大，且在Join字段上有索引帮助排序，或者语句要求返回一个排好序的结果集	输入数据集较大。尤其适合于Data warehouse 环境下的那些复杂的查询语句
并发性	能够支持大量的并发用户同时运行	有索引支持的Many-to-one的join并发性较好，Many-To-Many的就差了	最好同时只有少数用户在同时运行
Join时要否两个字段相等	不要	要(除非是full outer join)	要
要否使用内存资源	不使用	不使用(如果要为Merge Join做排序，可能要使用)	使用
要否使用tempdb	不使用	many-to-many join要使用	使用
输入数据集要否排序	不要	要	不要
希望输入数据集排序否	希望outer input是排序的	是的	不要

在SQL Server做联接的时候，会按照输入数据集所基于的表格的结构，衡量可能利用的索引，也根据统计信息，预估两个输入数据集的大小，选择使用三种Join方式其中的一种。如果选得不对，可能就会造成Join的速度非常慢。

实际应用

这是一道面试题，可以参考我之前写过的一篇博客：查询在一张表不在另外一张表的记录。现在发现之前写的还是不够清晰透彻，我会修改那篇博客，具体的解法也在写在那篇博客中。

题目的大致意思是：

假如要查询在a表中存在，但是在b表中不存在的记录，应该如何查询。为了便于说明，我们假设a表和b表都只有一个字段id，a表中的记录为{1,2,3,4,5}，b表中的记录为{2,4}，那么我们需要通过一个sql查询得到{1,3,5}这样的结果集。还有就是a和b表中id不一定是排序的，a表的数据集大，b表的数据集小。