SQL连接操作符介绍(循环嵌套, 哈希匹配和合并连接)

SQL连接操作符介绍(循环嵌套, 哈希匹配和合并连接)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

 

  今天我将介绍在SQLServer 中的三种连接操作符类型,分别是:循环嵌套、哈希匹配和合并连接。主要对这三种连接的不同、复杂度用范例的形式一一介绍。

  本文中使用了示例数据库AdventureWorks ,下面是下载地址:http://msftdbprodsamples.codeplex.com/releases/view/4004

简介:什么是连接操作符

  连接操作符是一种算法类型,它是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'

 

执行计划的结果如下:

join types 1 exec plan

图右上方的叫“outer input”,在其下面的叫做“inner input” 

本质上讲,“Nested Loops”操作符就是:为每一个记录的外部输入找到内部输入的匹配行。

技术上讲,这意味着外表聚集索引被扫描获取外部输入相关的记录,然后内表聚集索引查找每一个匹配外表索引的记录。

我们可以通过把鼠标放在聚集索引扫描操作符上面来验证这个信息,请看这个tooltip:

join types 2 details

看这个执行的估计行数是1,索引查找tooltip如下:

join types 3 details

这次发现执行的估计行数是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

 

查询执行计划如下:

join types 4 exec plan

  • 首先我们注意到两套数据是在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:

join types 5 exec plan

由于ContactID列没有索引,所以选择哈希操作符。

在深入理解这个例子之前,介绍两个重要的概念:一个是“Hashing”函数,一个是“Hash Table”。

函数是一个程序性函数,它接收1或者多个值然后转换他们为一个符号值(通常是数字)。这个函数通常是单向的,意味着不能反转回来原始值,但是确定性保证如果你提供了相同的值,符号值是完全一样的。也就是说,几个不同的输入值,可以有相同的Hash值。

“Hash Table”是一个数据结构,把所有行都放到一个相同尺寸的桶里面。每一个桶代表一个哈希值。这意味着当你激活函数的行,使用结果你就会知道它属于哪个桶。

利用统计信息,SQLServer 会选择较小的两个数据输入来提供构造输入,并且输入被用来在内存中创建哈希表。如果没有足够的内存,在tempdb中会使用物理磁盘。在哈希表建立后,SQLServer将从较大的表中得到数据,叫做探测输入。利用哈希匹配函数与哈希表比较,然后返回匹配行。在图形执行计划中,构造输入的查询在上面,探测输入的查询在下面。

只要较小的表非常小,这个算法就是非常有效的。但是如果两个表都非常大,这可能是非常低效的执行计划。

查询Hints

利用Hints,破事SQLServer使用指定的连接类型。但是强烈不推荐这么做,尤其在生产环境,因为没有永恒的最佳选择(因为数据在变化),并且优化器通常是正确的。

添加OPTION 子句作为查询的结尾,使用关键字LOOP JOINMERGE 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*hc+M*hm+J)
  • 最后默认的操作符
  • 使用哈希表和动态哈希匹配函数匹配行

     本篇随笔详细介绍了三种链接操作符和它们的触发机制,当然这些也都是动态的,就像前面说的没有最佳的操作符,只有最合适的,要根据实际请款选择不同的操作符。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119624.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • html遮罩层样式,遮罩层样式

    .shade{width:100%;height:100%;position:absolute;top:0px;left:0px;z-index:5000;background:#000;opacity:0.7;}要遮罩的内容中还有下拉框,不用iframe的话,盖不住下拉框。使用了宽和高都为100%的iframe后,用了后会导致背景色和文字颜色等失效。//隐藏sele…

  • 基于javaEE的医院病历管理系统的设计与实现[通俗易懂]

    网络的高速发展,促使着数字化医院的建设,现如今大多数医院已经在使用病历管理系统来管理患者电子病历。在医院中,病历记录了医生和患者的诊疗过程,医生可以通过之前病历记载,快速诊断患者,所以病历是医院的重要资产。使用计算机可以提高病历质量,方便存储、查阅、检索等,从而提高病案管理效率,实现病历信息同时异地共享和反复利用。电子病历的推广应用已经势不可挡,未来电子病历需求更高,应用也将继续成熟,市场的竞争也更加激烈。本次毕业设计的题目是基于javaEE的医院病历管理系统的设计与实现。本系统主要运用java编程语言、基

  • 查询数据库空间使用情况的函数_查看当前数据库

    查询数据库空间使用情况的函数_查看当前数据库sp_spaceused[[@objname=]'objname'][,[@updateusage=]'updateusage'][@objname

  • 使用mxnet实现卷积神经网络LeNet

    1.LeNet模型LeNet是一个早期用来识别手写数字的卷积神经网络,这个名字来源于LeNet论文的第一作者YannLeCun。LeNet展示了通过梯度下降训练卷积神经网络可以达到手写数字识别在当

    2021年12月30日
  • mysql数据库中,求和函数怎么用_sql语句count函数用法

    mysql数据库中,求和函数怎么用_sql语句count函数用法mysql窗口函数(mysql版本8):1.涉及到排名问题,可以使用窗口函数2.专用窗口函数rank,dense_rank,row_number有什么区别呢?它们的区别我举个例子,你们一下就能看懂:select*,rank()over(orderby成绩desc)asranking,dense_rank()over(orderby成绩desc)asdese_ra…

  • 现在哪款诺基亚能玩Java游戏_回忆S60(塞班)年代的JAVA游戏:有没有哪一款是你在课堂偷偷玩的?…

    现在哪款诺基亚能玩Java游戏_回忆S60(塞班)年代的JAVA游戏:有没有哪一款是你在课堂偷偷玩的?…Bounce我们把这个游戏叫为蹦球,也是诺基亚手机内置的一款游戏。需要操控一只红色的小皮球,滚动、蹦跳来一路闯关,碰触黄色的圈得分,关卡设计在今天来说都算是十分灵活的,可以来回进行冒险,不像常见的横版卷轴过关游戏,经过的关卡就不能回去了。玩这款游戏很是需要耐心,有些关卡需要特别注意机关、暗道,更有些关卡连弹跳的力度和位置都需要尝试很多次去掌握,依稀还记得按键2,5跳跃,按*(星键)可以改变蹦球形象…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号