not_in_anti_join_v0.6.patch

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 3e7dc85..6a6adb2 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -27,6 +27,7 @@
 #include "optimizer/prep.h"
 #include "optimizer/subselect.h"
 #include "optimizer/var.h"
+#include "parser/parse_clause.h"
 #include "parser/parse_relation.h"
 #include "rewrite/rewriteManip.h"
 #include "utils/builtins.h"
@@ -1222,7 +1223,7 @@ SS_process_ctes(PlannerInfo *root)
  */
 JoinExpr *
 convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
-							Relids available_rels)
+							bool under_not, Relids available_rels)
 {
 	JoinExpr   *result;
 	Query	   *parse = root->parse;
@@ -1237,6 +1238,16 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	Assert(sublink->subLinkType == ANY_SUBLINK);
 
 	/*
+	 * The SQL standard's requirements for handling of NULL values in a
+	 * NOT IN() condition requires that if a NULL appears within the NOT IN
+	 * condition that the whole condition is UNKNOWN, therefore FALSE. Here,
+	 * if we can be sure that the NOT IN condition will never produce any NULL
+	 * values, then we can allow this to become an ANTI JOIN.
+	 */
+	if (under_not && queryTargetListCanHaveNulls(subselect))
+		return NULL;
+
+	/*
 	 * The sub-select must not refer to any Vars of the parent query. (Vars of
 	 * higher levels should be okay, though.)
 	 */
@@ -1302,7 +1313,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	 * And finally, build the JoinExpr node.
 	 */
 	result = makeNode(JoinExpr);
-	result->jointype = JOIN_SEMI;
+	result->jointype = under_not ? JOIN_ANTI : JOIN_SEMI;
 	result->isNatural = false;
 	result->larg = NULL;		/* caller must fill this in */
 	result->rarg = (Node *) rtr;
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 9cb1378..c1d7091 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -334,7 +334,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 		/* Is it a convertible ANY or EXISTS clause? */
 		if (sublink->subLinkType == ANY_SUBLINK)
 		{
-			if ((j = convert_ANY_sublink_to_join(root, sublink,
+			if ((j = convert_ANY_sublink_to_join(root, sublink, false,
 												 available_rels1)) != NULL)
 			{
 				/* Yes; insert the new join node into the join tree */
@@ -360,7 +360,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 				return NULL;
 			}
 			if (available_rels2 != NULL &&
-				(j = convert_ANY_sublink_to_join(root, sublink,
+				(j = convert_ANY_sublink_to_join(root, sublink, false,
 												 available_rels2)) != NULL)
 			{
 				/* Yes; insert the new join node into the join tree */
@@ -452,7 +452,61 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 
 		if (sublink && IsA(sublink, SubLink))
 		{
-			if (sublink->subLinkType == EXISTS_SUBLINK)
+			if (sublink->subLinkType == ANY_SUBLINK)
+			{
+				if ((j = convert_ANY_sublink_to_join(root, sublink, true,
+												   available_rels1)) != NULL)
+				{
+					/* Yes; insert the new join node into the join tree */
+					j->larg = *jtlink1;
+					*jtlink1 = (Node *) j;
+					/* Recursively process pulled-up jointree nodes */
+					j->rarg = pull_up_sublinks_jointree_recurse(root,
+																j->rarg,
+																&child_rels);
+
+					/*
+					 * Now recursively process the pulled-up quals.  Because
+					 * we are underneath a NOT, we can't pull up sublinks that
+					 * reference the left-hand stuff, but it's still okay to
+					 * pull up sublinks referencing j->rarg.
+					 */
+					j->quals = pull_up_sublinks_qual_recurse(root,
+															 j->quals,
+															 &j->rarg,
+															 child_rels,
+															 NULL, NULL);
+					/* Return NULL representing constant TRUE */
+					return NULL;
+				}
+				if (available_rels2 != NULL &&
+					(j = convert_ANY_sublink_to_join(root, sublink, true,
+												   available_rels2)) != NULL)
+				{
+					/* Yes; insert the new join node into the join tree */
+					j->larg = *jtlink2;
+					*jtlink2 = (Node *) j;
+					/* Recursively process pulled-up jointree nodes */
+					j->rarg = pull_up_sublinks_jointree_recurse(root,
+																j->rarg,
+																&child_rels);
+
+					/*
+					 * Now recursively process the pulled-up quals.  Because
+					 * we are underneath a NOT, we can't pull up sublinks that
+					 * reference the left-hand stuff, but it's still okay to
+					 * pull up sublinks referencing j->rarg.
+					 */
+					j->quals = pull_up_sublinks_qual_recurse(root,
+															 j->quals,
+															 &j->rarg,
+															 child_rels,
+															 NULL, NULL);
+					/* Return NULL representing constant TRUE */
+					return NULL;
+				}
+			}
+			else if (sublink->subLinkType == EXISTS_SUBLINK)
 			{
 				if ((j = convert_EXISTS_sublink_to_join(root, sublink, true,
 												   available_rels1)) != NULL)
@@ -506,6 +560,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 					return NULL;
 				}
 			}
+
 		}
 		/* Else return it unmodified */
 		return node;
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 4931dca..db50e62 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -21,6 +21,7 @@
 #include "commands/defrem.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
+#include "optimizer/clauses.h"
 #include "optimizer/tlist.h"
 #include "parser/analyze.h"
 #include "parser/parsetree.h"
@@ -78,6 +79,8 @@ static int get_matching_location(int sortgroupref,
 static List *addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
 					 List *grouplist, List *targetlist, int location,
 					 bool resolveUnknown);
+static Relids find_inner_rels(Query *query);
+static void find_inner_rels_walker(Node *jtnode, Relids *innerrels);
 static WindowClause *findWindowClause(List *wclist, const char *name);
 static Node *transformFrameOffset(ParseState *pstate, int frameOptions,
 					 Node *clause);
@@ -2406,6 +2409,180 @@ assignSortGroupRef(TargetEntry *tle, List *tlist)
 }
 
 /*
+ * find_inner_rels
+ *		Returns all relids in the query that are INNER JOIN rels.
+ *		Note that this function should only be used if this information
+ *		is required before deconstruct_jointree has been called.
+ */
+static Relids
+find_inner_rels(Query *query)
+{
+	Relids innerrels = NULL;
+
+	find_inner_rels_walker((Node *) query->jointree, &innerrels);
+
+	return innerrels;
+}
+
+/*
+ * find_inner_rels_walker
+ *		Worker function for find_inner_rels
+ */
+static void
+find_inner_rels_walker(Node *jtnode, Relids *innerrels)
+{
+	if (jtnode == NULL)
+	{
+		*innerrels = NULL;
+		return;
+	}
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+		*innerrels = bms_add_member(*innerrels, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+		{
+			find_inner_rels_walker((Node *)lfirst(l), innerrels);
+		}
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		if (j->jointype == JOIN_INNER)
+		{
+			find_inner_rels_walker(j->larg, innerrels);
+			find_inner_rels_walker(j->rarg, innerrels);
+		}
+	}
+}
+
+/*
+ * queryTargetListListCanHaveNulls
+ *		True if the logic in the function was unable to prove without doubt
+ *		that NULL values could not exist in the result set.
+ *
+ * Note: resjunk targets are ignored.
+ */
+bool
+queryTargetListCanHaveNulls(Query *query)
+{
+	List	 *local_nonnullable_vars;
+	bool	  computed_nonnullable_vars = false;
+	ListCell *tl;
+	Node	 *node;
+	Relids	  innerrels;
+
+	/*
+	 * It should also be possible to determine if no NULLs can exist in the
+	 * results even when set operators are present in the query, but for now
+	 * we'll just report that NULLs are possible. It may be worth fixing this
+	 * up in the future, but at the time of writing this function, no call
+	 * sites existed which would call the function if the query contained set
+	 * operators.
+	 */
+	if (query->setOperations)
+		return true;
+
+	/*
+	 * In the following loop we loop over each TargetEntry in the targetList
+	 * of the query with the aim to determine if a NULL value is impossible for
+	 * each TargetEntry. When doing this we must err on the side of caution,
+	 * it's ok for us to return True even if no NULL values do actually appear
+	 * in the final result set. We use the following methods to determine if
+	 * NULLs cannot exist:
+	 *
+	 * 1. If the TargetEntry is a Const, we can instantly tell if it's NULL
+	 *    or not.
+	 *
+	 * 2. If the Var comes from a relation and that relation has an INNER JOIN
+	 *    join type, we can lookup pg_attribute.attnotnull.
+	 *
+	 * 3. When not-nullness could not be proved by point 2 we may still be able
+	 *    to find a qual in the WHERE clause of the query that allows us to
+	 *    determine that a NULL will never be seen in the result set.
+	 *    For example the presense of; col IS NOT NULL, or col = 42 would allow
+	 *    us to determine that NULLs would not be possible in the result set.
+	 */
+
+	/* any rel not in this list must have an outer join type */
+	innerrels = find_inner_rels(query);
+
+	foreach(tl, query->targetList)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(tl);
+
+		/* ignore columns which won't be in the final results */
+		if (tle->resjunk)
+			continue;
+
+		node = (Node *) tle->expr;
+
+		/* Check point 1: If the Const is NULL then report NULLs are possible. */
+		if (IsA(node, Const))
+		{
+			if (((Const *) node)->constisnull)
+				return true;
+		}
+
+		else if (IsA(node, Var))
+		{
+			ListCell	  *lc;
+			bool		   matched;
+			Var			  *tlevar = (Var *) node;
+
+			/* check point 2 */
+			if (OidIsValid(tle->resorigtbl) &&
+				bms_is_member(tlevar->varno, innerrels) &&
+				get_attnotnull(tle->resorigtbl, tle->resorigcol))
+				continue; /* cannot be NULL */
+
+			/* check point 3 */
+			if (!computed_nonnullable_vars)
+			{
+				/*
+				 * Analyzing the WHERE clause for not-nullable Vars likely is
+				 * a more expensive check, for this reason we do this last and
+				 * only do it once on the first time it is required.
+				 */
+				local_nonnullable_vars = find_nonnullable_vars(query->jointree->quals);
+				computed_nonnullable_vars = true;
+			}
+
+			matched = false;
+			foreach(lc, local_nonnullable_vars)
+			{
+				Var *var = (Var *) lfirst(lc);
+
+				if (var->varno == tlevar->varno &&
+					var->varattno == tlevar->varattno &&
+					var->varlevelsup == 0)
+				{
+					matched = true;
+					break;
+				}
+			}
+
+			/*
+			 * if check point 3 failed then we've run out of ways to determine
+			 * the nullability of the target entry, so we must return True.
+			 */
+			if (!matched)
+				return true;
+		}
+		else
+			return true; /* not a Const or a Var */
+	}
+	return false; /* Cannot have NULLs */
+}
+
+/*
  * targetIsInSortList
  *		Is the given target item already in the sortlist?
  *		If sortop is not InvalidOid, also test for a match to the sortop.
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 4b5ef99..c98adc7 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -816,6 +816,37 @@ get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
 /*				---------- ATTRIBUTE CACHES ----------					 */
 
 /*
+ * get_attnotnull
+ *		Returns true if pg_attribute.attnotnull is true, otherwise returns
+ *		false. An error is raised if no record is found for the relid/attnum.
+ *
+ * Note: Calling functions should be careful and test relid for InvalidOid
+ * before calling this function.
+ */
+bool
+get_attnotnull(Oid relid, AttrNumber attnum)
+{
+	HeapTuple	tp;
+
+	tp = SearchSysCache2(ATTNUM,
+						 ObjectIdGetDatum(relid),
+						 Int16GetDatum(attnum));
+	if (HeapTupleIsValid(tp))
+	{
+		Form_pg_attribute att_tup = (Form_pg_attribute) GETSTRUCT(tp);
+		bool result = att_tup->attnotnull;
+		ReleaseSysCache(tp);
+		return result;
+	}
+	else
+	{
+		elog(ERROR, "cache lookup failed for attribute %d of relation %u",
+			attnum, relid);
+		return false; /* keep compiler quiet */
+	}
+}
+
+/*
  * get_attname
  *		Given the relation id and the attribute number,
  *		return the "attname" field from the attribute relation.
diff --git a/src/include/optimizer/subselect.h b/src/include/optimizer/subselect.h
index 5607e98..3e8bfe7 100644
--- a/src/include/optimizer/subselect.h
+++ b/src/include/optimizer/subselect.h
@@ -18,6 +18,7 @@
 extern void SS_process_ctes(PlannerInfo *root);
 extern JoinExpr *convert_ANY_sublink_to_join(PlannerInfo *root,
 							SubLink *sublink,
+							bool under_not,
 							Relids available_rels);
 extern JoinExpr *convert_EXISTS_sublink_to_join(PlannerInfo *root,
 							   SubLink *sublink,
diff --git a/src/include/parser/parse_clause.h b/src/include/parser/parse_clause.h
index e9e7cdc..1bad04e 100644
--- a/src/include/parser/parse_clause.h
+++ b/src/include/parser/parse_clause.h
@@ -47,5 +47,6 @@ extern List *addTargetToSortList(ParseState *pstate, TargetEntry *tle,
 					bool resolveUnknown);
 extern Index assignSortGroupRef(TargetEntry *tle, List *tlist);
 extern bool targetIsInSortList(TargetEntry *tle, Oid sortop, List *sortList);
+extern bool queryTargetListCanHaveNulls(Query *query);
 
 #endif   /* PARSE_CLAUSE_H */
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index f46460a..5e7d946 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -63,6 +63,7 @@ extern List *get_op_btree_interpretation(Oid opno);
 extern bool equality_ops_are_compatible(Oid opno1, Oid opno2);
 extern Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype,
 				  int16 procnum);
+extern bool get_attnotnull(Oid relid, AttrNumber attnum);
 extern char *get_attname(Oid relid, AttrNumber attnum);
 extern char *get_relid_attribute_name(Oid relid, AttrNumber attnum);
 extern AttrNumber get_attnum(Oid relid, const char *attname);
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index 0f070ef..35608ad 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -768,3 +768,207 @@ select nextval('ts1');
       11
 (1 row)
 
+--
+-- Check NOT IN performs ANTI JOIN when subquery columns are NOT NULL
+-- and does not when subquery columns can contain NULLs.
+--
+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
+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
+         ->  Seq Scan on b
+(6 rows)
+
+-- No ANTI JOIN, y can be NULL
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on b
+(4 rows)
+
+-- No ANTI JOIN, x is NOT NULL, but we don't know if + 1 will change that.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT x+1 FROM b);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on b
+(4 rows)
+
+-- ANTI JOIN 1 is a Const that is not null.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT 1 FROM b);
+        QUERY PLAN         
+---------------------------
+ Nested Loop Anti Join
+   Join Filter: (a.id = 1)
+   ->  Seq Scan on a
+   ->  Materialize
+         ->  Seq Scan on b
+(5 rows)
+
+-- No ANTI JOIN, results contain a NULL Const
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT NULL::int FROM b);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on b
+(4 rows)
+
+-- ANTI JOIN y = 1 means y can't be NULL
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1);
+          QUERY PLAN           
+-------------------------------
+ Hash Anti Join
+   Hash Cond: (a.id = b.y)
+   ->  Seq Scan on a
+   ->  Hash
+         ->  Seq Scan on b
+               Filter: (y = 1)
+(6 rows)
+
+-- No ANTI JOIN, OR condition does not ensure y = 1
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1 OR x = 1);
+               QUERY PLAN               
+----------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on b
+           Filter: ((y = 1) OR (x = 1))
+(5 rows)
+
+-- No ANTI JOIN, OR condition does not ensure y = 1 or y = 2
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND (y = 2 OR x = 2));
+                            QUERY PLAN                             
+-------------------------------------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Seq Scan on b
+           Filter: (((y = 1) OR (x = 1)) AND ((y = 2) OR (x = 2)))
+(5 rows)
+
+-- ANTI JOIN y must be 2, so can't be NULL
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND y = 2);
+                        QUERY PLAN                        
+----------------------------------------------------------
+ Hash Anti Join
+   Hash Cond: (a.id = b.y)
+   ->  Seq Scan on a
+   ->  Hash
+         ->  Seq Scan on b
+               Filter: ((y = 2) AND ((y = 1) OR (x = 1)))
+(6 rows)
+
+-- ANTI JOIN y can be 1 or 2, but can't be null.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR y = 2));
+                 QUERY PLAN                 
+--------------------------------------------
+ Hash Anti Join
+   Hash Cond: (a.id = b.y)
+   ->  Seq Scan on a
+   ->  Hash
+         ->  Seq Scan on b
+               Filter: ((y = 1) OR (y = 2))
+(6 rows)
+
+-- No ANTI JOIN c.z is from an outer join so it can have nulls.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Left Join
+           Merge Cond: (b.x = c.z)
+           ->  Sort
+                 Sort Key: b.x
+                 ->  Seq Scan on b
+           ->  Sort
+                 Sort Key: c.z
+                 ->  Seq Scan on c
+(11 rows)
+
+-- ANTI JOIN, c.z is from an inner join and has a NOT NULL constraint.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b INNER JOIN c ON b.x = c.z);
+               QUERY PLAN                
+-----------------------------------------
+ Merge Anti Join
+   Merge Cond: (a.id = c.z)
+   ->  Index Only Scan using a_pkey on a
+   ->  Materialize
+         ->  Merge Join
+               Merge Cond: (b.x = c.z)
+               ->  Sort
+                     Sort Key: b.x
+                     ->  Seq Scan on b
+               ->  Sort
+                     Sort Key: c.z
+                     ->  Seq Scan on c
+(12 rows)
+
+-- ANTI JOIN, c.z must be 1
+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 = 1);
+                QUERY PLAN                 
+-------------------------------------------
+ Hash Anti Join
+   Hash Cond: (a.id = c.z)
+   ->  Seq Scan on a
+   ->  Hash
+         ->  Nested Loop
+               ->  Seq Scan on c
+                     Filter: (z = 1)
+               ->  Materialize
+                     ->  Seq Scan on b
+                           Filter: (x = 1)
+(10 rows)
+
+-- ANTI JOIN, c.z can't be NULL
+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);
+                    QUERY PLAN                     
+---------------------------------------------------
+ Merge Anti Join
+   Merge Cond: (a.id = c.z)
+   ->  Index Only Scan using a_pkey on a
+   ->  Materialize
+         ->  Merge Join
+               Merge Cond: (b.x = c.z)
+               ->  Sort
+                     Sort Key: b.x
+                     ->  Seq Scan on b
+               ->  Sort
+                     Sort Key: c.z
+                     ->  Seq Scan on c
+                           Filter: (z IS NOT NULL)
+(13 rows)
+
+ROLLBACK;
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index b3fb03c..30ec0ab 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -435,3 +435,72 @@ select * from
   order by 1;
 
 select nextval('ts1');
+
+--
+-- Check NOT IN performs ANTI JOIN when subquery columns are NOT NULL
+-- and does not when subquery columns can contain NULLs.
+--
+
+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
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT x FROM b);
+
+-- No ANTI JOIN, y can be NULL
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b);
+
+-- No ANTI JOIN, x is NOT NULL, but we don't know if + 1 will change that.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT x+1 FROM b);
+
+-- ANTI JOIN 1 is a Const that is not null.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT 1 FROM b);
+
+-- No ANTI JOIN, results contain a NULL Const
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT NULL::int FROM b);
+
+-- ANTI JOIN y = 1 means y can't be NULL
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1);
+
+-- No ANTI JOIN, OR condition does not ensure y = 1
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1 OR x = 1);
+
+-- No ANTI JOIN, OR condition does not ensure y = 1 or y = 2
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND (y = 2 OR x = 2));
+
+-- ANTI JOIN y must be 2, so can't be NULL
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND y = 2);
+
+-- ANTI JOIN y can be 1 or 2, but can't be null.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR y = 2));
+
+-- No ANTI JOIN c.z is from an outer join so it can have nulls.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z);
+
+-- ANTI JOIN, c.z is from an inner join and has a NOT NULL constraint.
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b INNER JOIN c ON b.x = c.z);
+
+-- ANTI JOIN, c.z must be 1
+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 = 1);
+
+-- ANTI JOIN, c.z can't be NULL
+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);
+
+ROLLBACK;