排序归并连接Merge Sort Join
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在连接列上的取值。假设为等值连接,大致过程如下:
假设内存中有2个BUFFER,一个BUFFER能容纳2个记录,取出T1的(1,3)和T2的(1,4)进行比较,此时只有(1,1)是匹配的,把1所在的记录放到结果集中,3,4不匹配,那么接下来再取出记录集中的其他值:
此时可能会有疑问:3和4怎么没了呢?这是因为T2中剩下最小的值是4,由于我们的假设是等值连接,那么显然,3舍弃。同理舍弃4。接下来就是新的一轮循环啦,直到两个表比较完成。
2、 表访问过程
排序归并连接每个表最大的访问次数为1,这个访问次数是为了根据WHERE子句中的条件筛选和过滤出用于归并的记录集,归并过程是对排序过程筛选出来的BUFFER进行操作的。
构造表T1和T2,构造过程略,表的记录数:
为了得到真实的执行计划,尤其是表访问次数,我选择了alter session set statistics_level=all 来获取执行计划。
执行查询语句:
SELECT /*+ leading(t1) use_merge(t2)*/ *
FROM t1, t2
WHERE t1.id = t2.t1_id;
这里HINT里使用了LEADING,实际上只是指定了首先进行排序操作的表,并非驱动表。
获取执行计划:
表T1和表T2都只访问了一次,如果查询一个T1中不存在的值那么执行计划为
T1表访问次数为1,T2表访问次数为0,可以看到BUFFERS的访问数目为3,是在步骤3中产生的,步骤4和5的BUFFERS都是0,也就是说,T1表即LEADING表没有返回值时,不会再去访问T2。如果修改HINT,使T2成为驱动表,那么执行计划就不一样了:
这时候相比于使用T1作为驱动表,耗费的资源要多很多,包括内存消耗、逻辑读、以及执行时间都大大增涨。
尝试一种特殊的情况:
SELECT /*+ leading(t2) use_merge(t1)*/ *
FROM t1, t2
WHERE t1.id = t2.t1_id
and 1=2;
此时表的访问次数都为0。这是因为限制条件中有一个永假的条件: AND 1=2,优化器此时会聪明地绕过表的访问,直接访问数据字典(filter(NULL IS NOT NULL)),返回结果为表的结构。