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

《浅谈查询优化器中的join算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、浅谈查询优化器中的JOIN算法>>教育资源库　　查询优化器都是支持JOIN操作的，而SQLServer中主要有以下三类JOIN算法：NestedLoop、Sort-Merge以及HashJoin。尽管每种算法都并不是很复杂，但考虑到性能优化，在产品级的优化器实现时往往使用的是改进过的变种算法。譬如SQLServer支持blocknestedloops、indexnextedloops、sort-merge、hashjoin以及hashteam。我们在这里只对上述三种基本算法的原型做一个简单的介绍。　　【假设】有两张表R和S，R共占有M页，S共占有N页。r和s

2、分别代表元组，而i和j分别代表第i或者第j个字段，也就是后文提到的JOIN字段。　　1.NestedLoopJoin(嵌套循环联结)　　算法：　　其思路相当的简单和直接：对于关系R的每个元组r将其与关系S的每个元组s在JOIN条件的字段上直接比较并筛选出符合条件的元组。写成伪代码就是：　　foreachtuplerÎRdo　　foreachtuplesÎSdo　　ifri==sjthenaddtoresult　　代价：　　被联结的表所处内层或外层的顺序对磁盘I/O开销有着非常重要的影响。而CPU开销相对来说影响较小，主要是元组读入内存

3、以后(in-memory)的开销，是O(n*m)　　对于I/O开销，根据page-at-a-time的前提条件，I/Ocost=M+M*N，翻译一下就是I/O的开销=读取M页的I/O开销+M次读取N页的I/O开销。　　使用小结：　　•适用于一个集合大而另一个集合小的情况(将小集合做为外循环)，I/O性能不错。　　•当外循环输入相当小而内循环非常大且有索引建立在JOIN字段上时，I/O性能相当不错。　　•当两个集合中只有一个在JOIN字段上建立索引时，一定要将该集合作为内循环。　　•对于一对一的匹配关系(两个具有唯一约束

4、字段的联结)，可以在找到匹配元组后跳过该次内循环的剩余部分(类似于编程语言循环语句中的continue)。　　2.Sort-MergeJoin(排序合并联结)　　NestedLoop一般在两个集合都很大的情况下效率就相当差了，而Sort-Merge在这种情况下就比它要高效不少，尤其是当两个集合的JOIN字段上都有聚集索引(clusteredindex)存在时，Sort-Merge性能将达到最好。　　算法：　　基本思路也很简单(复习一下数据结构中的合并排序吧)，主要有两个步骤：　　(1)按JOIN字段进行排序　　(2)对两组已排序集合进行合并排序，从端各自取得

5、数据列后加以比较(需要根据是否在JOIN字段有重复值做特殊的分区处理)　　代价：(主要是I/O开销)　　有两个因素左右Sort-Merge的开销：JOIN字段是否已排序以及JOIN字段上的重复值有多少。　　•最好情况下(两列都已排序且至少有一列没有重复值)：O(n+m)只需要对两个集合各扫描一遍　　•最差情况下(两列都未排序且两列上的所有值都相同)：O(n*logn+m*logm+n*m)两次排序以及一次全部元组间的笛卡尔乘积　　使用小结：　　如前所述，可以考虑在两个结果集都很大情况下使用，最好能有聚集索引保证已经排序完毕。而在实际应用中

6、，我们经常会与遇到的主键-外键关系就是Sort-Merge的一个很好的应用。这种情况下，一般两列都会有聚集索引(已排序)而且一对多的关系保证了至少有一列没有重复值，这种情况下，Sort-Merge的性能是三种里面最好的。　　另外，如果要求查询的SQL语法本身就要求GROUPBY、ORDERBY、CUBE等运行，则查询语法整体本来就要做排序，因此可以重用排序结果，此时Merge也是不错的选择。　　3.HashJoin(哈希联结)　　HashJoin在本质上类似于两列都有重复值时的Sort-Merge的处理思想分区(patitioning)。但它们也有区别：Ha

7、shJoin通过哈希来分区(每一个桶就是一个分区)而Sort-Merge通过排序来分区(每一个重复值就是一个分区)。　　值得注意的是，HashJoin与上述两种算法之间的较大区别同时也是一个较大限制是它只能应用于等值联结(equalityjoin)，这主要是由于哈希函数及其桶的确定性及无序性所导致的。　　算法：　　基本的HashJoin算法由以下两步组成：　　(1)BuildInputPhase：基于JOIN字段，使用哈希函数h2为较小的S集合构建内存中(in-memory)的哈希表，相同键值的以linkedlist组成一个桶(bucket)　　(2)Pro

8、beInputPhase：在较大的R集合上对哈希表进