SQL Server Join方式

0.参考文献

Microsoft SQL Server企业级平台管理实践 

看懂SqlServer查询计划

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执行的联结以及其所对应的执行计划，

View Code

--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 

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

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

顾名思义，Hash Join就是利用哈希算法作匹配的联接算法。具体的哈希算法可以参考我的另外一篇博客：Hashmap实现原理。简单来说，哈希算法分成两步，“构建哈希桶(Build hash 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方式作一下比较。

在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表的数据集小。