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

　　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) 两次排序以及一次全部元组间的笛卡尔乘积

　　使用小结：

　　如前所述，可以考虑在两个结果集都很大情况下使用，最好能有聚集索引保证已经排序完毕。而在实际应用中，我们经常会与遇到的主键-外键关系就是Sort-Merge的一个很好的应用。这种情况下，一般两列都会有聚集索引(已排序)而且一对多的关系保证了至少有一列没有重复值，这种情况下，Sort-Merge的性能是三种里面最好的。

　　另外，如果要求查询的SQL语法本身就要求GROUP BY、ORDER BY、CUBE等运行，则查询语法整体本来就要做排序，因此可以重用排序结果，此时Merge也是不错的选择。

　　3. Hash Join (哈希联结)

　　Hash Join在本质上类似于两列都有重复值时的Sort-Merge的处理思想——分区(patitioning)。但它们也有区别：Hash Join通过哈希来分区(每一个桶就是一个分区)而Sort-Merge通过排序来分区(每一个重复值就是一个分区)。