not_in_anti_join_v0.9.delta.patch

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 4b44662..6ebab4d 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -70,6 +70,8 @@ static Node *convert_testexpr_mutator(Node *node,
 static bool subplan_is_hashable(Plan *plan);
 static bool testexpr_is_hashable(Node *testexpr);
 static bool hash_ok_operator(OpExpr *expr);
+static bool is_NOTANY_compatible_with_antijoin(Query *outerquery,
+				 SubLink *sublink);
 static bool simplify_EXISTS_query(Query *query);
 static Query *convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect,
 					  Node **testexpr, List **paramIds);
@@ -1187,6 +1189,117 @@ SS_process_ctes(PlannerInfo *root)
 }
 
 /*
+ * is_NOTANY_compatible_with_antijoin
+ *		True if the NOT IN sublink can be safely converted into an ANTI JOIN.
+ *		Per SQL spec, NOT IN is not ordinarily equivalent to an anti-join,
+ *		however, if we can prove that all of the expressions on both sides of
+ *		the would be join condition are all certainly not NULL, then it's safe
+ *		to convert NOT IN to an anti-join.
+ *
+ * Note: This function is quite locked into the NOT IN syntax. Certain
+ *       assumptions are made about the structure of the join conditions:
+ *
+ * 1. We assume that when more than 1 join condition exists that these are AND
+ *    type conditions, i.e not OR conditions.
+ *
+ * 2. We assume that each join qual has 2 arguments and the first arguments in
+ *    each join qual is the one that belongs to the outer side of the NOT IN
+ *    clause.
+ */
+static bool
+is_NOTANY_compatible_with_antijoin(Query *outerquery, SubLink *sublink)
+{
+	ListCell *lc;
+	List	 *outerexpr;
+	List	 *innerexpr;
+	Node	 *testexpr = sublink->testexpr;
+	Query	 *subselect = (Query *) sublink->subselect;
+
+	/*
+	 * We must build 2 lists of expressions, one for the outer query side and
+	 * one for the subquery/inner side of the NOT IN clause. It is these lists
+	 * that we pass to to expressions_are_not_nullable to allow it to determine
+	 * if each expression cannot contain NULL values or not. We'll try and be
+	 * as lazy about this as possible and we won't bother generating the 2nd
+	 * list if the first list can't be proved to be free from null-able
+	 * expressions. The order that we checks these lists does not really matter
+	 * as neither one seems to be more likely to allow us to exit from this
+	 * function more quickly.
+	 */
+
+	/* if it's a single expression */
+	if (IsA(testexpr, OpExpr))
+	{
+		OpExpr *opexpr = (OpExpr *) testexpr;
+
+		Assert(list_length(opexpr->args) == 2);
+
+		outerexpr = lappend(NIL, linitial(opexpr->args));
+	}
+
+	/* multiple expressions ANDed together */
+	else if (IsA(testexpr, BoolExpr))
+	{
+		List	 *list = ((BoolExpr *) testexpr)->args;
+
+		outerexpr = NIL;
+
+		 /* loop through each expression appending to the list each iteration. */
+		foreach(lc, list)
+		{
+			OpExpr *opexpr = (OpExpr *) lfirst(lc);
+
+			Assert(list_length(opexpr->args) == 2);
+
+			outerexpr = lappend(outerexpr, linitial(opexpr->args));
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+					(int) nodeTag(testexpr));
+
+	if (outerexpr == NIL)
+		elog(ERROR, "unexpected empty clause");
+
+	/*
+	 * Check the expressions being used in the outer query side of the NOT IN
+	 * clause to ensure NULLs are not possible.
+	 */
+	if (!expressions_are_not_nullable(outerquery, outerexpr))
+		return false;
+
+	/*
+	 * Now we check to ensure each TargetEntry in the subquery can be proved to
+	 * never be NULL.
+	 */
+
+	innerexpr = NIL;
+
+	foreach(lc, subselect->targetList)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(lc);
+
+		/* Resjunk columns can be ignored: they don't produce output values */
+		if (tle->resjunk)
+			continue;
+
+		innerexpr = lappend(innerexpr, tle->expr);
+	}
+
+	if (innerexpr == NIL)
+		elog(ERROR, "unexpected empty clause");
+
+	/*
+	 * Check if all the subquery's targetlist columns can be proved to be not
+	 * null.
+	 */
+	if (!expressions_are_not_nullable(subselect, innerexpr))
+		return false;
+
+	return true; /* supports ANTI JOIN */
+}
+
+/*
  * convert_ANY_sublink_to_join: try to convert an ANY SubLink to a join
  *
  * The caller has found an ANY SubLink at the top level of one of the query's
@@ -1242,10 +1355,11 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	/*
 	 * Per SQL spec, NOT IN is not ordinarily equivalent to an anti-join, so
 	 * that by default we have to fail when under_not.  However, if we can
-	 * prove that the sub-select's output columns are all certainly not NULL,
-	 * then it's safe to convert NOT IN to an anti-join.
+	 * prove that all of the expressions on both sides of the, would be, join
+	 * condition are all certainly not NULL, then it's safe to convert NOT IN
+	 * to an anti-join.
 	 */
-	if (under_not && !query_outputs_are_not_nullable(subselect))
+	if (under_not && !is_NOTANY_compatible_with_antijoin(parse, sublink))
 		return NULL;
 
 	/*
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index f8e3eaa..dd02327 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -1994,9 +1994,9 @@ find_forced_null_var(Node *node)
 }
 
 /*
- * query_outputs_are_not_nullable
- *		Returns TRUE if the output values of the Query are certainly not NULL.
- *		All output columns must return non-NULL to answer TRUE.
+ * expressions_are_not_nullable
+ *		Returns TRUE if each Expr in the expression list is certainly not NULL.
+ *		All Exprs must return non-NULL to answer TRUE.
  *
  * The reason this takes a Query, and not just an individual tlist expression,
  * is so that we can make use of the query's WHERE/ON clauses to prove it does
@@ -2012,7 +2012,7 @@ find_forced_null_var(Node *node)
  * side of conservatism: if we're not sure, it's okay to return FALSE.
  */
 bool
-query_outputs_are_not_nullable(Query *query)
+expressions_are_not_nullable(Query *query, List *exprlist)
 {
 	PlannerInfo subroot;
 	Relids		innerjoined_rels = NULL;
@@ -2020,7 +2020,7 @@ query_outputs_are_not_nullable(Query *query)
 	List	   *usable_quals = NIL;
 	List	   *nonnullable_vars = NIL;
 	bool		computed_nonnullable_vars = false;
-	ListCell   *tl;
+	ListCell   *lc;
 
 	/*
 	 * If the query contains set operations, punt.  The set ops themselves
@@ -2044,16 +2044,11 @@ query_outputs_are_not_nullable(Query *query)
 	subroot.parse = query;
 
 	/*
-	 * Examine each targetlist entry to prove that it can't produce NULL.
+	 * Examine each Expr to prove that it can't produce NULL.
 	 */
-	foreach(tl, query->targetList)
+	foreach(lc, exprlist)
 	{
-		TargetEntry *tle = (TargetEntry *) lfirst(tl);
-		Expr	   *expr = tle->expr;
-
-		/* Resjunk columns can be ignored: they don't produce output values */
-		if (tle->resjunk)
-			continue;
+		Expr *expr = (Expr *) lfirst(lc);
 
 		/*
 		 * For the most part we don't try to deal with anything more complex
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index 5b25d01..90f745c 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -69,7 +69,7 @@ extern Relids find_nonnullable_rels(Node *clause);
 extern List *find_nonnullable_vars(Node *clause);
 extern List *find_forced_null_vars(Node *clause);
 extern Var *find_forced_null_var(Node *clause);
-extern bool query_outputs_are_not_nullable(Query *query);
+extern bool expressions_are_not_nullable(Query *query, List *exprlist);
 
 extern bool is_pseudo_constant_clause(Node *clause);
 extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids);
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index b63f7ac..610c175 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -805,24 +805,96 @@ select nextval('ts1');
 
 --
 -- Check NOT IN performs an ANTI JOIN when NULLs are not possible
--- in the target list of the subquery.
+-- on either side of the, would be, join condition.
 --
 BEGIN;
 CREATE TEMP TABLE a (id INT PRIMARY KEY);
 CREATE TEMP TABLE b (x INT NOT NULL, y INT);
 CREATE TEMP TABLE c (z INT NOT NULL);
--- ANTI JOIN. x is defined as NOT NULL
+INSERT INTO b VALUES(1,1),(2,2),(3,NULL);
+-- No ANTI JOIN, b.x is from an outer join
 EXPLAIN (COSTS OFF)
-SELECT * FROM a WHERE id NOT IN (SELECT x FROM b);
-               QUERY PLAN                
------------------------------------------
- Merge Anti Join
-   Merge Cond: (a.id = b.x)
-   ->  Index Only Scan using a_pkey on a
-   ->  Sort
-         Sort Key: b.x
+SELECT * FROM a 
+LEFT OUTER JOIN b ON a.id = b.x
+WHERE b.x NOT IN(SELECT z FROM c);
+             QUERY PLAN             
+------------------------------------
+ Hash Right Join
+   Hash Cond: (b.x = a.id)
+   Filter: (NOT (hashed SubPlan 1))
+   ->  Seq Scan on b
+   ->  Hash
+         ->  Seq Scan on a
+   SubPlan 1
+     ->  Seq Scan on c
+(8 rows)
+
+-- ANTI JOIN, b.x is from an outer join but b.x > 100
+-- forces the join not to produce NULL on the righthand
+-- side.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a 
+LEFT OUTER JOIN b ON a.id = b.x 
+WHERE b.x NOT IN(SELECT z FROM c)
+  AND b.x > 100;
+           QUERY PLAN            
+---------------------------------
+ Hash Join
+   Hash Cond: (b.x = a.id)
+   ->  Hash Anti Join
+         Hash Cond: (b.x = c.z)
          ->  Seq Scan on b
-(6 rows)
+               Filter: (x > 100)
+         ->  Hash
+               ->  Seq Scan on c
+   ->  Hash
+         ->  Seq Scan on a
+(10 rows)
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a 
+FULL OUTER JOIN b ON a.id = b.x 
+WHERE b.x NOT IN(SELECT y FROM c);
+         QUERY PLAN          
+-----------------------------
+ Hash Full Join
+   Hash Cond: (b.x = a.id)
+   Filter: (NOT (SubPlan 1))
+   ->  Seq Scan on b
+   ->  Hash
+         ->  Seq Scan on a
+   SubPlan 1
+     ->  Seq Scan on c
+(8 rows)
+
+-- No ANTI JOIN. y can have NULLs
+EXPLAIN (COSTS OFF)
+SELECT * FROM b WHERE y NOT IN (SELECT z FROM c);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on b
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on c
+(4 rows)
+
+-- c is an empty relation so should cause no filtering on b
+SELECT * FROM b WHERE y NOT IN (SELECT z FROM c);
+ x | y 
+---+---
+ 1 | 1
+ 2 | 2
+ 3 |  
+(3 rows)
+
+INSERT INTO c VALUES(1);
+-- Records where y is NULL should be filtered out.
+SELECT * FROM b WHERE y NOT IN (SELECT z FROM c);
+ x | y 
+---+---
+ 2 | 2
+(1 row)
 
 -- No ANTI JOIN, y can be NULL
 EXPLAIN (COSTS OFF)
@@ -988,7 +1060,7 @@ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
                  ->  Seq Scan on c
 (11 rows)
 
--- No ANTI JOIN, c.z is not from an outer join
+-- No ANTI JOIN, c.z is from an outer join
 EXPLAIN (COSTS OFF)
 SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z);
              QUERY PLAN             
@@ -1080,23 +1152,22 @@ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHER
                            Filter: (z IS NOT NULL)
 (13 rows)
 
-ALTER TABLE c ADD COLUMN x INT;
--- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+-- ANTI JOIN, b.y cannot be NULL due to the join condition b.y = c.z
 EXPLAIN (COSTS OFF)
-SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+SELECT * FROM a WHERE id NOT IN (SELECT b.y FROM b INNER JOIN c ON b.y = c.z);
                QUERY PLAN                
 -----------------------------------------
  Merge Anti Join
-   Merge Cond: (a.id = b.x)
+   Merge Cond: (a.id = b.y)
    ->  Index Only Scan using a_pkey on a
    ->  Materialize
          ->  Merge Join
-               Merge Cond: (b.x = c.x)
+               Merge Cond: (b.y = c.z)
                ->  Sort
-                     Sort Key: b.x
+                     Sort Key: b.y
                      ->  Seq Scan on b
                ->  Sort
-                     Sort Key: c.x
+                     Sort Key: c.z
                      ->  Seq Scan on c
 (12 rows)
 
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index c3ca67f..c4f9102 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -447,7 +447,7 @@ select nextval('ts1');
 
 --
 -- Check NOT IN performs an ANTI JOIN when NULLs are not possible
--- in the target list of the subquery.
+-- on either side of the, would be, join condition.
 --
 
 BEGIN;
@@ -456,9 +456,40 @@ CREATE TEMP TABLE a (id INT PRIMARY KEY);
 CREATE TEMP TABLE b (x INT NOT NULL, y INT);
 CREATE TEMP TABLE c (z INT NOT NULL);
 
--- ANTI JOIN. x is defined as NOT NULL
+INSERT INTO b VALUES(1,1),(2,2),(3,NULL);
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a
+LEFT OUTER JOIN b ON a.id = b.x
+WHERE b.x NOT IN(SELECT z FROM c);
+
+-- ANTI JOIN, b.x is from an outer join but b.x > 100
+-- forces the join not to produce NULL on the righthand
+-- side.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a
+LEFT OUTER JOIN b ON a.id = b.x
+WHERE b.x NOT IN(SELECT z FROM c)
+  AND b.x > 100;
+
+-- No ANTI JOIN, b.x is from an outer join
 EXPLAIN (COSTS OFF)
-SELECT * FROM a WHERE id NOT IN (SELECT x FROM b);
+SELECT * FROM a
+FULL OUTER JOIN b ON a.id = b.x
+WHERE b.x NOT IN(SELECT y FROM c);
+
+-- No ANTI JOIN. y can have NULLs
+EXPLAIN (COSTS OFF)
+SELECT * FROM b WHERE y NOT IN (SELECT z FROM c);
+
+-- c is an empty relation so should cause no filtering on b
+SELECT * FROM b WHERE y NOT IN (SELECT z FROM c);
+
+INSERT INTO c VALUES(1);
+
+-- Records where y is NULL should be filtered out.
+SELECT * FROM b WHERE y NOT IN (SELECT z FROM c);
 
 -- No ANTI JOIN, y can be NULL
 EXPLAIN (COSTS OFF)
@@ -508,7 +539,7 @@ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
 EXPLAIN (COSTS OFF)
 SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
 
--- No ANTI JOIN, c.z is not from an outer join
+-- No ANTI JOIN, c.z is from an outer join
 EXPLAIN (COSTS OFF)
 SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z);
 
@@ -528,11 +559,8 @@ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHER
 EXPLAIN (COSTS OFF)
 SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHERE c.z IS NOT NULL);
 
-ALTER TABLE c ADD COLUMN x INT;
-
--- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+-- ANTI JOIN, b.y cannot be NULL due to the join condition b.y = c.z
 EXPLAIN (COSTS OFF)
-SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
-
+SELECT * FROM a WHERE id NOT IN (SELECT b.y FROM b INNER JOIN c ON b.y = c.z);
 
 ROLLBACK;