浅谈SQL Server查询优化器中的JOIN算法

    查询优化器都是支持JOIN操作的，而SQL Server 中主要有以下三类JOIN算法：Nested Loop、Sort-Merge以及Hash Join。尽管每种算法都并不是很复杂，但考虑到性能优化，在产品级的优化器实现时往往使用的是改进过的变种算法。譬如SQL Server 支持block nested loops、index nexted loops、sort-merge、hash join以及hash team。我们在这里只对上述三种基本算法的原型做一个简单的介绍。

　　【假设】有两张表R和S，R共占有M页，S共占有N页。r 和 s 分别代表元组，而 i 和 j 分别代表第i或者第 j 个字段，也就是后文提到的JOIN字段。

　　1. Nested Loop Join(嵌套循环联结)

　　算法：

　　其思路相当的简单和直接：对于关系R的每个元组 r 将其与关系S的每个元组 s 在JOIN条件的字段上直接比较并筛选出符合条件的元组。写成伪代码就是：

　　代价：

　　被联结的表所处内层或外层的顺序对磁盘I/O开销有着非常重要的影响。而CPU开销相对来说影响较小，主要是元组读入内存以后(in-memory)的开销，是 O (n * m)

　　对于I/O开销，根据 page-at-a-time 的前提条件，I/O cost = M + M * N，翻译一下就是 I/O的开销 = 读取M页的I/O开销 + M次读取N页的I/O开销。

　　使用小结：

　　• 适用于一个集合大而另一个集合小的情况(将小集合做为外循环)，I/O性能不错。

　　• 当外循环输入相当小而内循环非常大且有索引建立在JOIN字段上时，I/O性能相当不错。

　　• 当两个集合中只有一个在JOIN字段上建立索引时，一定要将该集合作为内循环。

 • 对于一对一的匹配关系(两个具有唯一约束字段的联结)，可以在找到匹配元组后跳过该次内循环的剩余部分(类似于编程语言循环语句中的continue)。

　　2. Sort-Merge Join (排序合并联结)

　　Nested Loop一般在两个集合都很大的情况下效率就相当差了，而Sort-Merge在这种情况下就比它要高效不少，尤其是当两个集合的JOIN字段上都有聚集索引(clustered index)存在时，Sort-Merge性能将达到最好。

　　算法：

　　基本思路也很简单(复习一下数据结构中的合并排序吧)，主要有两个步骤：

　　(1) 按JOIN字段进行排序

　　(2) 对两组已排序集合进行合并排序，从来源端各自取得数据列后加以比较(需要根据是否在JOIN字段有重复值做特殊的“分区”处理)

　　代价：(主要是I/O开销)

　　有两个因素左右Sort-Merge的开销：JOIN字段是否已排序 以及 JOIN字段上的重复值有多少。

　　• 最好情况下(两列都已排序且至少有一列没有重复值)：O (n + m) 只需要对两个集合各扫描一遍

　　• 最差情况下(两列都未排序且两列上的所有值都相同)：O (n * log n + m * log m + n * m) 两次排序以及一次全部元组间的笛卡尔乘积