性能调优7:多表连接 – 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吗?

(0)
上一篇 2022年3月21日
下一篇 2022年3月21日

相关推荐