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

核心提示：查询优化器都是支持JOIN操作的，而SQL Server 中主要有以下三类JOIN算法：Nested Loop、Sort-Merge以及Hash Join，浅谈查询优化器中的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条件的字段上直接比较并筛选出符合条件的元组。写成伪代码就是：

　　foreachtuplerÎRdo
　　foreachtuplesÎSdo
　　ifri==sjthenaddtoresult

代价：

被联结的表所处内层或外层的顺序对磁盘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)。