Fix wrong results Left Anti Semi (Not-In) Join.

[avamingli]

Fix issue #15662

See all reproduce cases there, I pick a case to show the problem and how I resolve it.

GPDB's special join type Left Anti Semi (Not-In) Join, Nestloop or HashJoin may generate wrong results if:

1. There are redistribution_clauses that contains both side's varno, so that Restriction->mergeopfamilies is not NUL. And cdbpath_motion_for_join decides to Redistribute one or both if possible.
2. And there are null values in the inner side.

Left Anti Semi (Not-In) Join will quit as soon as possible if we find a null tuple from the inner side and should return empty rows. If we are Left Anti Semi (Not-In) Join, we must Broadcast the inner side or Gather all sides to a single segment even though the locus of both are compatible.

Example:

create table t1(c1 int) distributed by (c1);
create table t2(c2n int) distributed by (c2n);
insert into t1 values (generate_series (1,10));
insert into t2 values (1), (2), (3), (null), (5), (6), (7);

select c1 from t1 where c1 not in (select c2n from t2 where c2n is null or c2n > 0) and c1 is not null;
     							QUERY PLAN
-----------------------------------------------------------------------------------
 Gather Motion 3:1  (slice1; segments: 3)  (cost=1.05..2.16 rows=3 width=4)
   ->  Hash Left Anti Semi (Not-In) Join  (cost=1.05..2.11 rows=1 width=4)
		 Hash Cond: (t1.c1 = t2.c2n)
		 ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4)
			   Filter: (c1 IS NOT NULL)
		 ->  Hash  (cost=1.03..1.03 rows=2 width=4)
			   ->  Seq Scan on t2  (cost=0.00..1.03 rows=2 width=4)
					 Filter: ((c2n IS NULL) OR (c2n > 0))

Subquery select c2n from t2 where c2n is null or c2n > 0 return all tuples from c2n including null value and the restriction c1 is not null won't affect the expected results. The right result is returning empty rows.

GPDB will convert this NOT IN sql to Left Anti Semi (Not-In) Join, and the join keys are c1 and c2n. In this sql, the locus of t1 and t2 are compatible and we don't add Motion for them as before. But that plan will get wrong results and return non-empty rows which are not expected. Think about the plan, assume that the null value of t2 is stored on segment_1 of GPDB which has 3 segments.

When execution, it's OK for segment_1 because Left Anti Semi Join will first build the inner side. It will quit as soon as possible if find a null value. That means stop building the hash table and avoid probing the outer table. It's similar to Nested Loop Left Anti Semi (Not-In) Join. But for plan executed on segment_0 or segment_2, it will scan the inner table without null values, probe the outer table and send tuples to QD. And we will get unexpected tuples from segment_0 and segment_2.

It's also not correct if join on a table's distribution keys and we choose to redistribute another side. The reason is similar, after Redistribute Motion, null values would be on a same segment and it rollbacks to the above example.

Conclusion: For Left Anti Semi (Not-In) Join, the follows are not correct: 1.Avoid Motion for inner and outer locus are compatible on the join keys. 2.Redistribute outer path if join on inner path's distribution keys and vice versa. 3.Redistribute both sides.

And as Left Anti Semi (Not-In) Join is an outer join, we couldn't broadcast the outer side. The only right ways are: 1.Broadcast the inner side if possible. 2.Gather all rels to a single segment.

cdbpath_motion_for_join always keep the Gather to SingleQE as the Last resort, it's hard to create a not in case using the way Gather all rels to a single segment

Provide a ORCA case to show that right.

--
-- Test left anti semi (not-in) join
-- For ORCA, use Gather to a single segment instead of Broadcast.
--
begin;
\pset null '<NULL>'
create table t9_lasj(c1 int) distributed by (c1);
create table t10_lasj_has_null(c1n int) distributed by (c1n);
insert into t9_lasj values (generate_series (1,10));
insert into t10_lasj_has_null values (1), (2), (3), (null), (5), (6), (7);
analyze t9_lasj;
analyze t10_lasj_has_null;
select c1n from t10_lasj_has_null where c1n is null or c1n > 0;
  c1n   
--------
      2
      3
 <NULL>
      7
      1
      5
      6
(7 rows)

set local optimizer_enable_motion_broadcast = off;
-- Hash left anti semi (not-in) join
explain(costs off) select c1 from t9_lasj where c1 not in (select c1n from t10_lasj_has_null where c1n is null or c1n > 0) and c1 is not null;
                        QUERY PLAN                        
----------------------------------------------------------
 Hash Left Anti Semi (Not-In) Join
   Hash Cond: (t9_lasj.c1 = t10_lasj_has_null.c1n)
   ->  Gather Motion 3:1  (slice1; segments: 3)
         ->  Seq Scan on t9_lasj
               Filter: (NOT (c1 IS NULL))
   ->  Hash
         ->  Gather Motion 3:1  (slice2; segments: 3)
               ->  Seq Scan on t10_lasj_has_null
                     Filter: ((c1n IS NULL) OR (c1n > 0))
 Optimizer: Pivotal Optimizer (GPORCA)
(10 rows)

select c1 from t9_lasj where c1 not in (select c1n from t10_lasj_has_null where c1n is null or c1n > 0) and c1 is not null;
 c1 
----
(0 rows)

reset optimizer_enable_motion_broadcast;
\pset null ''
abort;

This is not suitable for General/SegmentGeneral locus, they have all data including null values on every segment.

Authored-by: Zhang Mingli [email protected]

Here are some reminders before you submit the pull request

• [x] Add tests for the change
• [ ] Document changes
• [ ] Communicate in the mailing list if needed
• [x] Pass make installcheck
• [x] Review a PR in return to support the community