性能调优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的结果合并作为连接操作最终输出的结果。
参考文档：