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

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