GPDB技术内幕 - SEMI JOIN浅析

GPDB技术内幕 - SEMI JOIN浅析

SEMI JOIN顾名思义，半连接，相对于join字段来说，针对外表的一行记录，内表只要有一条满足，就输出外表记录。注意，这里是仅输出外表记录。GPDB中有几种实现方式，本文我们简单聊聊。

从代码中，我们看到SEMI JOIN的类型有3类：

1、JOIN_SEMI

这是普通实现方式。针对nestloop join、merge join、hash join的inner join来说，只要针对JOIN字段，内表有记录就输出外表记录。以nestloop join为例：

外表和内表记录是无序的，针对外表第一个记录1，遍历内表。内表第一记录为11，不匹配，继续下一条记录；下一条是1，join匹配，输出外表1的值；此时针对外表记录1，就不必继续内表扫描了，join结束，继续外表下一个记录10重新扫描内表进行join条件判断。

这种方式是通用实现方式。下面看第二种实现方式。

2、JOIN_UNIQUE_OUTER/JOIN_UNIQUE_INNER

从SEMI JOIN的语义中，可以看出join过成中，外表一个值仅能匹配内表一个值；这样我们就可以先将内表进行去重，然后再进行普通inner join，从而实现SEMI JOIN。

先将内表进行去重：可以通过group by进行聚合（hash agg或者sort agg）去重得到内表值；然后针对外表1，顺序扫描内表去重后的值11，不匹配，继续下一个值；下一个值是1，匹配，输出外表值1。针对Join的结果，内表因为去过重，所以满足join条件的必然只有一个值。

3、JOIN_DEDUP_SEMI/JOIN_DEDUP_SEMI_REVERSE

以上两种实现方式是沿用PgSQL，针对的是集中式实现方式。GPDB是分布式，当分布键不匹配时，就需要进行广播MOTION，即使每个segment上去过重，广播MOTION后仍旧可能存在重复值，这样就不能使用第2种实现方式。比如下面案例：第三种实现方式

postgres=# explain select * from s where exists (select 1 from r where s.a = r.b);
                         QUERY PLAN                                                   
---------------------------------------------------------------------------------------------------------------
Gather Motion 3:1  (slice1; segments: 3)  (cost=153.50..155.83 rows=100 width=8)
->  HashAggregate  (cost=153.50..153.83 rows=34 width=8)
    Group Key: (RowIdExpr)
    ->  Redistribute Motion 3:3  (slice2; segments: 3)  (cost=11.75..153.00 rows=34 width=8)
      Hash Key: (RowIdExpr)
      ->  Hash Join  (cost=11.75..151.00 rows=34 width=8)
          Hash Cond: (r.b = s.a)
          ->  Seq Scan on r  (cost=0.00..112.00 rows=3334 width=4)
          ->  Hash  (cost=8.00..8.00 rows=100 width=8)
            ->  Broadcast Motion 3:3  (slice3; segments: 3)  (cost=0.00..8.00 rows=100 width=8)
                ->  Seq Scan on s  (cost=0.00..4.00 rows=34 width=8)
Optimizer: Postgres query optimizer
(12 rows)

分析：

1）上面案例s作为内表，r作为外表。s表远大于r表。s广播motion记录数量众多，代价非常大

2）Hash join构建hash表阶段进行去重

3）外表r不可以广播motion，否则会产生重复值

4）基于上述原因，只能选择广播大表进行JOIN_SEMI了

所以，GPDB实现了第3种方式，即先进行join，然后再去重。主要是为了能够广播小表，比如上述例子种的小表r（作为外表），即使产生重复值也可以在去重阶段去掉。

为了方便去重，GPDB引入了表达式RowIdExpr，即去重操作：DISTINCT ON (RowIdExpr)。该表达式为一条记录产生唯一标识值，附加到该记录中作为一个额外字段。广播后进行join，相对于JOIN_SEMI计划，多了一个重分布MOTION节点，当然MOTION的记录都非常少。上述例子中可以看到hash join后需要在RowIdExpr上进行重分布，然后再在RowIdExpr这个字段上通过Hash Agg进行去重。鉴于hash join前的广播分布和join后的重分布传输的记录数量都比较小，JOIN_DEDUP_SEMI实现方式就在三种实现方式中胜出了。