欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

性能调优7:多表连接 - join

程序员文章站 2022-03-12 15:38:28
在产品环境中,往往存在着大量的表连接情景,不管是inner join、outer join、cross join和full join(逻辑连接符号),在内部都会转化为物理连接(Physical Join),SQL Server共有三种物理连接:Nested Loop(嵌套循环),Merge Join ......

在产品环境中,往往存在着大量的表连接情景,不管是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

你真的了解join吗?