SQL连接操作符介绍（循环嵌套，哈希匹配和合并连接）
  今天我将介绍在SQLServer 中的三种连接操作符类型，分别是：循环嵌套、哈希匹配和合并连接。主要对这三种连接的不同、复杂度⽤范例的形式⼀⼀介绍。
简介：什么是连接操作符
  连接操作符是⼀种算法类型，它是SQLServer优化器为了实现两个数据集合之间的逻辑连接选择的操作符。优化器可以基于请求查询、可⽤索引、统计信息和估计⾏数等不同的场景为每⼀套数据选择不同的算法
  通过查看执⾏计划可以发现操作符如何被使⽤。接下来我们看⼀下如何具体使⽤。
NESTED LOOPS（循环嵌套）
种子哈希转换链接  我们通过下⾯的例⼦来展⽰⼀下（查询2001年7⽉份的数据）：
SELECT
OH.OrderDate, OD.OrderQty, OD.ProductID, OD.UnitPrice
FROM
Sales.SalesOrderHeader AS OH
JOIN
Sales.SalesOrderDetail AS OD
ON
OH.SalesOrderID = OD.SalesOrderID
WHERE
OH.OrderDate BETWEEN '2001-07-01' AND '2001-07-31'
执⾏计划的结果如下:
图右上⽅的叫“outer input”，在其下⾯的叫做“inner input”
本质上讲，“Nested Loops”操作符就是：为每⼀个记录的外部输⼊到内部输⼊的匹配⾏。
技术上讲，这意味着外表聚集索引被扫描获取外部输⼊相关的记录，然后内表聚集索引查每⼀个匹配外表索引的记录。
我们可以通过把⿏标放在聚集索引扫描操作符上⾯来验证这个信息，请看这个tooltip：
看这个执⾏的估计⾏数是1，索引查tooltip如下:
这次发现执⾏的估计⾏数是179，这是很接近返回的外部输⼊⾏的。
按照复杂度计算（假设N是外部输出的⾏数，M是总⾏数在SalesOrderDetai表的）：查询复杂度是O(NlogM)，这⾥logM是在内部输⼊表的每次查的复杂度。
当外部输⼊⽐较⼩并且内部输⼊有索引在连接的字段上的时候SQLServer 优化器更喜欢选择这种操作符类型（Nested Loop）。外部和内部输⼊的数据⾏差距越⼤，这个操作符提供的性能越⾼。
MERGE Join（合并连接）
“Merge”算法是连接两个较⼤且按序存储的在连接键上最有效的⽅式。请看⼀下下⾯这个查询例⼦（查询返回⽤户和销售表的ID）:
SELECT
OC.CustomerID, OH.SalesOrderID
FROM
Sales.SalesOrderHeader AS OH
JOIN
Sales.Customer AS OC
ON
OH.CustomerID = OC.CustomerID
查询执⾏计划如下:
⾸先我们注意到两套数据是在CustomerID上是有序的：因为聚集索引是有序的且在SalesorderHeader表上该字段是⾮聚集索引。
根据在操作符的箭头（⿏标放在上⾯），我们能看到每个返回结果⾏数都是很⼤的。
除此之外，在On 的⼦句后⾯要⽤=操作符。
就是这三个因素会导致优化器选择Merge Join查询操作符。
使⽤这种连接操作符的最⼤的性能就是两个输⼊操作符执⾏⼀次。我们能把⿏标放在两个数据的上⾯看⼀下执⾏的次数都是1，也就是说算法是很有效率的。
合并连接同时读取两个输⼊然后⽐较他们。如果匹配就返回，否则，⾏数较⼩的被放弃，因为两边输⼊是有序的。放弃的⾏不再匹配任何⾏。
知道其中⼀个表完毕⼀直重复匹配，即使另⼀个表还有数据，那么最⼤的时间复杂的消耗就是两个表完全不同键值，那么最⼤的复杂度就是: O(N+M)。
HASH Match（哈希匹配）
“Hash”连接是我们称为 “the go-to guy” 的操作符。当其他连接操作符都不⽀持的场景时，就会选择这种操作符。⽐如当表恰好不排序，或者没有索引时。当优化器选择这种操作符，⼀般来说可能是我们没有做好⼀些基础⼯作（例如，加索引）。但是有些情况（复杂查询）没有别的⽅式，只能选择它。
请看下⾯这个查询（获取contacts 表中姓和名中以“John”开始的包含销售的ID字段的数据集）:
SELECT
OC.FirstName, OC.LastName, OH.SalesOrderID
FROM
Sales.SalesOrderHeader AS OH
JOIN
Person.Contact AS OC
ON
OH.ContactID = OC.ContactID
WHERE
OC.FirstName LIKE 'John%'
The execution plan looks like this:
由于ContactID列没有索引，所以选择哈希操作符。
在深⼊理解这个例⼦之前，介绍两个重要的概念：⼀个是“Hashing”函数，⼀个是“Hash Table”。
函数是⼀个程序性函数，它接收1或者多个值然后转换他们为⼀个符号值（通常是数字）。这个函数通常是单向的，意味着不能反转回来原始值，但是确定性保证如果你提供了相同的值，符号值是完全⼀样的。也就是说，⼏个不同的输⼊值，可以有相同的Hash值。
“Hash Table”是⼀个数据结构，把所有⾏都放到⼀个相同尺⼨的桶⾥⾯。每⼀个桶代表⼀个哈希值。这意味着当你激活函数的⾏，使⽤结果你就会知道它属于哪个桶。
利⽤统计信息，SQLServer 会选择较⼩的两个数据输⼊来提供构造输⼊，并且输⼊被⽤来在内存中创建哈希表。如果没有⾜够的内存，在tempdb中会使⽤物理磁盘。在哈希表建⽴后，SQLServer将从较⼤的表中得到数据，叫做探测输⼊。利⽤哈希匹配函数与哈希表⽐较，然后返回匹配⾏。在图形执⾏计划中，构造输⼊的查询在上⾯，探测输⼊的查询在下⾯。
只要较⼩的表⾮常⼩，这个算法就是⾮常有效的。但是如果两个表都⾮常⼤，这可能是⾮常低效的执⾏计划。
查询Hints
利⽤Hints，破事SQLServer使⽤指定的连接类型。但是强烈不推荐这么做，尤其在⽣产环境，因为没有
永恒的最佳选择（因为数据在变化），并且优化器通常是正确的。
添加OPTION ⼦句作为查询的结尾，使⽤关键字LOOP JOIN, MERGE JOIN 或者 HASH JOIN可以强制执⾏连接。
看看如何实现:
SELECT OC.CustomerID, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Sales.Customer AS OC
ON OH.CustomerID = OC.CustomerID
OPTION (HASH JOIN)
SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Person.Contact AS OC
ON OH.ContactID = OC.ContactID
WHERE OC.FirstName LIKE 'John%'
OPTION (LOOP JOIN)
SELECT OC.FirstName, OC.LastName, OH.SalesOrderID
FROM Sales.SalesOrderHeader AS OH
JOIN Person.Contact AS OC
ON OH.ContactID = OC.ContactID
WHERE OC.FirstName LIKE 'John%'
OPTION (MERGE JOIN)
总结
Nested Loops
复杂度: O(NlogM)。
其中⼀个表很⼩的时候。
较⼤的表允许使⽤索引查连接字段。
Merge Join
复杂度: O(N+M)。
两个输⼊的连接字段是有序的。
使⽤=操作符
适合⾮常⼤的表
Hash Match
复杂度: O(N*h c+M*h m+J)
最后默认的操作符
使⽤哈希表和动态哈希匹配函数匹配⾏
本篇随笔详细介绍了三种链接操作符和它们的触发机制，当然这些也都是动态的，就像前⾯说的没有最佳的操作符，只有最合适的，要根据实际请款选择不同的操作符。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。