<< 返回文章列表

排序归并连接Merge Sort Join

2019年1月21日
吴怡玲
1919


1、 实现算法

排序归并连接算法大致可以分为以下几步:

(1)首先以目标SQL中指定的谓词条件(如果有的话)去访问表T1,然后对访问结果按照表T1中的连接列来排序,排好序后的结果集我们记为结果集1。

(2)接着以目标SQL中指定的谓词条件(如果有的话)去访问表T2,然后对访问结果按照表T2中的连接列来排序,排好序后的结果集我们记为结果集2。

(3)最后对结果集1和结果集2执行合并操作。

排序归并连接可以分为2个过程:排序、归并。以下介绍的是归并实现的算法。这个算法用伪代码实现如下:

pr := r的第一个记录的地址;

ps := s的第一个记录的地址;

while (ps≠nu while (ps≠null and pr≠null) do

begin ts := ps所指向的记录; Ss := { ts };

         让ps指向关系s的下一个记录; done := false;

          while (not done and ps≠null) do

          begin ts’:= ps所指向的记录;

                     if (ts’[JoinAttrs] = ts [JoinAttrs])

                     then begin Ss := Ss∪{ ts’};

                                   让ps指向关系s的下一个记录;

                              end

                     else done := true; ll and pr≠null) do

begin ts := ps所指向的记录; Ss := { ts };

         让ps指向关系s的下一个记录; done := false;

          while (not done and ps≠null) do

          begin ts’:= ps所指向的记录;

                     if (ts’[JoinAttrs] = ts [JoinAttrs])

                     then begin Ss := Ss∪{ ts’};

                                   让ps指向关系s的下一个记录;

                              end

                     else done := true;

           end(在连接属性上具有相同值的S记录被加入到了Ss中。Ps指向在连接属性上具有另一个值的S记录。)

这段伪代码看的人头大,用图来进行解释就很好理解了。假设记录集T1、T2已经排好序,为了简单起见,只显示T1和T2在连接列上的取值。假设为等值连接,大致过程如下:

 1.png

假设内存中有2个BUFFER,一个BUFFER能容纳2个记录,取出T1的(1,3)和T2的(1,4)进行比较,此时只有(1,1)是匹配的,把1所在的记录放到结果集中,3,4不匹配,那么接下来再取出记录集中的其他值:

                                          2.png 






此时可能会有疑问:3和4怎么没了呢?这是因为T2中剩下最小的值是4,由于我们的假设是等值连接,那么显然,3舍弃。同理舍弃4。接下来就是新的一轮循环啦,直到两个表比较完成。


2、 表访问过程

排序归并连接每个表最大的访问次数为1,这个访问次数是为了根据WHERE子句中的条件筛选和过滤出用于归并的记录集,归并过程是对排序过程筛选出来的BUFFER进行操作的。

 

构造表T1和T2,构造过程略,表的记录数:

2.png

为了得到真实的执行计划,尤其是表访问次数,我选择了alter session set statistics_level=all 来获取执行计划。

执行查询语句:

SELECT  /*+ leading(t1) use_merge(t2)*/ *

FROM t1, t2

WHERE t1.id = t2.t1_id;

这里HINT里使用了LEADING,实际上只是指定了首先进行排序操作的表,并非驱动表。

获取执行计划:

 3.png

 

表T1和表T2都只访问了一次,如果查询一个T1中不存在的值那么执行计划为

4.png

T1表访问次数为1,T2表访问次数为0,可以看到BUFFERS的访问数目为3,是在步骤3中产生的,步骤4和5的BUFFERS都是0,也就是说,T1表即LEADING表没有返回值时,不会再去访问T2。如果修改HINT,使T2成为驱动表,那么执行计划就不一样了:

5.png

这时候相比于使用T1作为驱动表,耗费的资源要多很多,包括内存消耗、逻辑读、以及执行时间都大大增涨。

 

尝试一种特殊的情况:

SELECT /*+ leading(t2) use_merge(t1)*/ *

FROM t1, t2

WHERE t1.id = t2.t1_id

and 1=2;

6.png

此时表的访问次数都为0。这是因为限制条件中有一个永假的条件: AND 1=2,优化器此时会聪明地绕过表的访问,直接访问数据字典(filter(NULL IS NOT NULL)),返回结果为表的结构。