在产品环境中,往往存在着大量的表连接情景,不管是inner join、outer join、cross join和full
join(逻辑连接符号),在内部都会转化为物理连接(Physical Join),SQL Server共有三种物理连接:Nested
Loop(嵌套循环),Merge Join(合并连接)和Hash Join(哈希连接)。这三个物理连接的处理方式不同,分别应用在不同的场景中。


在同一时刻,表连接只能是两表(或者是数据集,也就是表的一部分)之间的连接,通常按照表处于Join操作的位置来区分,把Join操作符前面的表叫做左表,把Join操作符后面的表叫做右表。如果有n个表连接,那么必须进行n-1次关联操作,上一次关联操作的结果作为下一次关联操作的一个数据集。On子句用于设置连接条件,可以决定连接的顺序。

一,嵌套循环


嵌套循环是最基本的Join算法,分为两个循环,内部循环和外部循环,内部循环嵌套在外部循环内部。任何一个连接语句,都包含两个表,内部循环对应内部表,外部循环对应外部表。在图形执行计划中,上面的输入表是外部表,下面的输入表是内部表。


在嵌套循环中,外部循环逐行处理外部表,内部循环针对每一个外部行到内部表中进行查找,以找出所有匹配外部行的数据行。外部循环每输出一行,内部表中所有行都会和外部行进行匹配,假如外部表有N行,内部表有M行,对于外部表的每一行,内部表都会匹配M行,这种算法的开销是基于外部表的行数
乘以内部表的行数来确定,即以 N*M 来确定开销。

如果内部循环在连接条件上存在索引,那么把连接条件的每一个值叫做关联参数(Correlated Parameter),使用关联参数可以应用index
seek算法去查找匹配行。


嵌套循环适用于:大表和小表进行连接,并且大表在连接条件上存在索引。当把外部表是小表,内部表是大表,且内部表是在连接列上有索引时,优化器倾向于使用嵌套循环。优化器对嵌套循环的优化是:

1,如果内部表在连接列上存在索引,那么优化器把外部表的输入行作为关联参数,基于关联参数对内部表使用index seek查询

2,对内部表使用Lazy Spool,Spool是指缓存中间结果集,以便重用。当内部表在连接条件上有很多重复值,但只有少数行可以和外部行匹配时,Nested
Loop算法的效率非常高。

不是所有的Join都有相关参数,如果没有合适的索引,或者on子句没有指定合适的连接条件,就不会使用index
seek算法,也就不会有相关参数,通常情况下,inner join和left join 可以有相关参数,而right join,cross join和full
join 没有相关参数。

二,合并连接


合并连接使用的是合并算法,要求至少存在一个相等的连接谓词(on子句中至少存在一个相等条件),并且两个输入在合并列上必须是有序的。通常情况下,查询优化器会扫描表上的索引,以检查是否有索引包含合并列;如果没有适当的索引,那么合并连接的后面使用sort操作符对合并列进行排序,索引和Sort操作符都是为了满足“合并算法对两个输入必须是有序的”这一硬性要求。合并连接,也称作排序-合并-连接(Sort-Merge-Join)。

如果合并连接需要对数据集进行排序,那么还需要为Sort操作符向系统申请授予内存(Granted
Memory),以存储排序的中间结果集。如果查询语句输出的结果在连接键上是有序,order by
join-keys,那么连接查询倾向于使用合并连接,如果排序是不必要的,那么可以去掉order by子句。

由于两个输入都已经排序,Merge Join操作符从每一输入各获取一行进行比较,例如,对于inner
join,如果两行相等,则放回这个相等的结果;如果不相等,则废弃值较小的行,并从该输入中获取下一行。这一过程重复进行,直到处理完所有的数据行。

如果两个输入是有序的数据,那么Merge Join的执行速度很快,但是,当需要添加Sort操作符对输入数据进行排序时,选择使用Merge
Join操作符将十分费时。对于数据量大,并且可以从B-Tree索引中获得已排序的数据,那么Merge Join是执行速度最快的连接算法。 

三,哈希连接

哈希连接(Hash Join)适用于无序的大表之间的连接,有两个输入:生成输入(Build Input) 和 探测输入(Porbe
Input),查询优化器使用两个输入中较小的作为生成输入。哈希连接扫描生成输入,加载到内存中,生成哈希表,这个过程叫做生成阶段(build
phrase)。当生成输入的所有行都加载到Hash 表之后,开始探测阶段(probe
phrase):对于探测输入的每一行,计算其Hash值,和哈希表进行匹配,输出匹配的数据行。在探测阶段,每做一次哈希连接操作,探测输入的每一行只会扫描一次,再根据哈希键值去扫描整个哈希表。

Hash连接的两个阶段是有先后顺序的,生成阶段在前,探测阶段在后。Hash连接在生成阶段需要生成Hash
Table,这需要向系统申请授予内存(granted memory),以存储Hash值,如果授予内存不足,那么Hash连接就不会开始。

1,哈希连接的内存消耗和溢出

在Hash连接开始执行前,SQL
Server尝试估计需要多少内存去创建Hash表,优化器使用预估的行数和每行的平均大小去估算需要的内存大小。为了最小化内存的使用,优化器从两个表中选择一个小表作为生成输入(Build
Input),SQL Server通过向系统申请授予内存来保证Hash表可以有“足够”的内存创建成功。

如果SQL
Server授予哈希连接的内存小于实际需要的内存,那么Hash连接在生成阶段会耗尽授予的内存,并把部分Hash表的数据溢出到硬盘上,也就是tempdb的workfile文件中。在这样的情景下,Hash连接维护的Hash
桶(Hash Bucket)实际上存储在两个地方:内存中的hash表和硬盘上的workfile。


Hash连接会记录Hash桶存储的位置,当从生成输入中继续读取一行数据时,它检查该行是映射到内存的Hash桶中,还是映射到硬盘的Hash桶中,如果映射到内存的Hash桶中,那么把该Hash值写入到内存中;如果映射到硬盘的Hash桶中,那么把该Hash值写入到硬盘上的workfile结构中。

在探测阶段,对于探测表的每一行,优化器都会检查该行是映射到内存中的Hash 桶,还是映射到硬盘上的Hash
桶。如果映射到内存中hash桶,优化器就探测Hash表,产生连接的数据集存储到内存中,并舍弃当前行;如果映射到硬盘的Hash桶,它会被写入到硬盘中,暂时不做Join运算,当Hash的探测阶段完成之后,Hash连接会把溢出到硬盘的数据读取到内存,为每个Hash
桶重建内存Hash表,做Join运算。也就是说,哈希连接把硬盘上的结果集和内存中的结果集合并为最终的结果集。

2,Hash连接的性能优化


Hash连接使用授予内存来创建哈希表,如果授予内存不足,那么部分哈希桶就会被溢出到硬盘,硬盘的读取和写入都会影响哈希连接的性能。因此,应该为Hash连接分配足够的授予内存。优化器使用统计信息来预估授予内存的大小,如果统计信息过时,导致预估的授予内存过小,这会严重降低Hash连接的性能。


还有一种可能性是,参与Hash连接的两个表都很大,以至于不能分配足够的内存来构建哈希表,这也会导致哈希桶被溢出到workfile,导致哈希连接的性能低下。对于大表之间的映射,尽量使连接列有序,进而使用合并算法来做连接。

3,哈希连接的类型

本文只简单介绍内存哈希连接和Grace 哈希连接,对于递归哈希连接(Recursive Hash Join)和 Hash Bailout
是这两个连接类型的优化,不再赘述。

(1),内存哈希连接(In-Memory Hash Join)

哈希连接计算整个生成输入,然后在内存中创建一个哈希表(Hash Table)。每一个行都根据哈希值(Hash
Value)计算Hash键,插入到相应的哈希桶(Hash Bucket)中。如果整个生成输入小于可能的内存,那么所有的数据行都会被存储到内存中哈希表中。

(2),Grace 哈希连接(Grace Hash Join)

如果生成输入太大,不能放到内存中,那么Hash Join将会被处理成多个步骤,这就是Grace
哈希连接。每一个步骤都有一个生成阶段和探测阶段。首先,Grace
哈希连接使用一个哈希函数,把整个生成输入和探测输入按照Hash键进行分区,把分区输入到不同的文件中,分区的规则是:

hash_func(join-field)


由于使用相同的hash算法,在连接列上进行分区,这就保证了匹配的任意两行数据都位于相同的文件对中,我推测:文件是在tempdb中创建的workfile,也就是说,需要调用IO子系统,把数据写入到硬盘中。Grace
hash join的主要的贡献就在于,它使得每条数据只需要Join一次。

Grace 哈希连接首先把两个大的输入,分割成多个小的输入,然后再对每个文件对进行哈希连接操作,最后把每个分区Join的结果合并作为连接操作最终输出的结果。

 

 

参考文档:

Advanced Query Tuning Concepts
<https://msdn.microsoft.com/en-us/library/ms191426(v=SQL.100).aspx>

你真的了解Join吗? <https://www.jianshu.com/p/47db8ac001ea>

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信