Allowing NOT IN to use ANTI joins

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index be92049..1d8614e 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"
@@ -1176,7 +1177,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;
@@ -1191,6 +1192,15 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	Assert(sublink->subLinkType == ANY_SUBLINK);
 
 	/*
+	 * For the case of NOT IN, we can only perform this optimization if we are
+	 * guaranteed that we'll never get NULL values from the subquery results.
+	 * For example "SELECT 1 WHERE 3 NOT IN(1,2,NULL)", the query will produce
+	 * 0 rows due to the fact that 3 <> NULL is unknown.
+	 */
+	if (under_not && queryTargetListCanHaveNulls(root, subselect))
+		return NULL;
+
+	/*
 	 * The sub-select must not refer to any Vars of the parent query. (Vars of
 	 * higher levels should be okay, though.)
 	 */
@@ -1256,7 +1266,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 776fe42..7ea165d 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 fcee137..7de2a52 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"
@@ -2406,6 +2407,115 @@ assignSortGroupRef(TargetEntry *tle, List *tlist)
 	return tle->ressortgroupref;
 }
 
+
+/*
+ * queryTargetListListCanHaveNulls
+ *		Checks if a query's targetList could produce NULL values. We only
+ *		return false if we can prove without question that no NULLs can exist
+ *		in all target list entries in the query.
+ *
+ * Note: resjunk targets are ignored here.
+ */
+bool
+queryTargetListCanHaveNulls(PlannerInfo *root, Query *query)
+{
+	List	 *local_nonnullable_vars;
+	bool	  computed_nonnullable_vars = false;
+	ListCell *tl;
+	Node	 *node;
+
+	/*
+	 * 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;
+
+
+	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;
+
+		/* for Constant expressions we can tell directly if they're NULL or not. */
+		if (IsA(node, Const))
+		{
+			if (((Const *) node)->constisnull)
+				return true;
+		}
+
+		else if (IsA(node, Var))
+		{
+			ListCell	  *lc;
+			RangeTblEntry *rte;
+			bool		   matched;
+			Var			  *tlevar = (Var *) node;
+			//Relids		   joinrelids;
+			/*
+			 * Now let's look at the WHERE clause items to see if there's anything in
+			 * there that will disallow NULLs from the results.
+			 */
+			if (!computed_nonnullable_vars)
+			{
+				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)
+				{
+					matched = true;
+					break;
+				}
+			}
+
+			/* Did we find the var non-nullable? */
+			if (matched)
+				continue; /* ok onto the next one */
+
+			/*
+			 * If we make it down here then we've been unable to find any quals
+			 * then ensure that the TargetEntry won't be NULL. All we have left
+			 * to go on is a NOT NULL constraint on the column, though this is
+			 * only going to prove that no nulls can be present if the relation
+			 * that the column belongs to is NOT from an OUTER JOIN.
+			 *
+			 * First we'll ensure we're dealing with a Var that's directly from
+			 * a table, then we'll ensure it's from an INNER JOIN type, finally
+			 * we'll look for a NOT NULL constraint on the column.
+			 */
+
+			if (!OidIsValid(tle->resorigtbl))
+				return true; /* Var is not from a table */
+
+			/* WRONG RangeTblEntry!!! */
+			rte =  rt_fetch(tlevar->varno, query->rtable);
+
+			if (IS_OUTER_JOIN(rte->jointype))
+				return true; /* Var from an outer join */
+
+			if (!get_attnotnull(tle->resorigtbl, tle->resorigcol))
+				return true; /* No NOT NULL constraint */
+		}
+		else
+			return true; /* not a Const or a Var */
+	}
+	return false; /* Cannot have NULLs */
+}
+
 /*
  * targetIsInSortList
  *		Is the given target item already in the sortlist?
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..8201574 100644
--- a/src/include/parser/parse_clause.h
+++ b/src/include/parser/parse_clause.h
@@ -15,6 +15,7 @@
 #define PARSE_CLAUSE_H
 
 #include "parser/parse_node.h"
+#include "nodes/relation.h"
 
 extern void transformFromClause(ParseState *pstate, List *frmList);
 extern int setTargetTable(ParseState *pstate, RangeVar *relation,
@@ -47,5 +48,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(PlannerInfo *root, 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 ce15af7..970a224 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -739,3 +739,207 @@ select * from int4_tbl where
   0
 (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 326fd70..53ba798 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -422,3 +422,72 @@ select * from int4_tbl where
 select * from int4_tbl where
   (case when f1 in (select unique1 from tenk1 a) then f1 else null end) in
   (select ten from tenk1 b);
+
+--
+-- 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;

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;

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 3e7dc85..7aaca33 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;
@@ -1317,9 +1328,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 /*
  * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
  *
- * The API of this function is identical to convert_ANY_sublink_to_join's,
- * except that we also support the case where the caller has found NOT EXISTS,
- * so we need an additional input parameter "under_not".
+ * The API of this function is identical to convert_ANY_sublink_to_join's.
  */
 JoinExpr *
 convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 9cb1378..055d741 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)
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 4931dca..a2ab6bf 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,231 @@ assignSortGroupRef(TargetEntry *tle, List *tlist)
 }
 
 /*
+ * find_inner_rels
+ *		Recursively traverse the jointree to seek out all relations which are
+ *		INNER JOIN relations.
+ *
+ *		Note: 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 *inner_join_rels)
+{
+	if (jtnode == NULL)
+	{
+		*inner_join_rels = NULL;
+		return;
+	}
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int varno = ((RangeTblRef *) jtnode)->rtindex;
+		*inner_join_rels = bms_add_member(*inner_join_rels, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *l;
+
+		foreach(l, f->fromlist)
+			find_inner_rels_walker((Node *)lfirst(l), inner_join_rels);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		/*
+		 * As we're only interested in finding inner relations we need not
+		 * recursively traverse down outer branches of the jointree.
+		 * For INNER join types we must look for inner relations on both sides
+		 * of the join. For LEFT, ANTI and SEMI joins we need only look on the
+		 * left hand side of the join tree. Right joins still can exist at this
+		 * early stage of planning so here we naturally just need to find inner
+		 * rels from the right side of the join. For FULL OUTER join types both
+		 * sides are outer, so we need not look any further for these.
+		 */
+
+		switch (j->jointype)
+		{
+			case JOIN_INNER:
+				find_inner_rels_walker(j->larg, inner_join_rels);
+				find_inner_rels_walker(j->rarg, inner_join_rels);
+
+				/*
+				 * NATURAL joins are a bit of a special case as TargetEntrys
+				 * will have the varno set to the rtindex of the JoinExpr from
+				 * which they are from. The NATURAL join type is actually an
+				 * inner join so we can just add the rtindex of this join to
+				 * the known inner rels.
+				 */
+				if (j->isNatural)
+					*inner_join_rels = bms_add_member(*inner_join_rels, j->rtindex);
+				break;
+
+			case JOIN_LEFT:
+			case JOIN_ANTI:
+			case JOIN_SEMI:
+				find_inner_rels_walker(j->larg, inner_join_rels);
+				break;
+
+			case JOIN_RIGHT:
+				find_inner_rels_walker(j->rarg, inner_join_rels);
+				break;
+
+			case JOIN_FULL:
+				break;
+
+			default:
+				elog(ERROR, "unrecognized join type: %d",
+					(int) j->jointype);
+		}
+	}
+	else
+	{
+		elog(ERROR, "unrecognized node type: %d",
+			(int) nodeTag(jtnode));
+	}
+}
+
+/*
+ * queryTargetListCanHaveNulls
+ *		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 presence of; col IS NOT NULL, or col = 42 would allow
+	 *    us to determine that NULLs would not be possible in the result set.
+	 *
+	 * Another possible way that we could prove not nullness would be to look
+	 * at join conditions. A query such as:
+	 * "select a.x from a inner join b on a.x = b.x" could never produce any
+	 * NULL valued a.x's due to the join condition filtering out NULLs. It may
+	 * be worth looking into doing this in the future.
+	 */
+
+	/* 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..6699c84 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -768,3 +768,301 @@ select nextval('ts1');
       11
 (1 row)
 
+--
+-- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+-- in the target list of the subquery.
+--
+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 a left 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 not from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+                     QUERY PLAN                      
+-----------------------------------------------------
+ Merge Left Join
+   Merge Cond: (c.z = b.x)
+   ->  Sort
+         Sort Key: c.z
+         ->  Merge Anti Join
+               Merge Cond: (a.id = c.z)
+               ->  Index Only Scan using a_pkey on a
+               ->  Sort
+                     Sort Key: c.z
+                     ->  Seq Scan on c
+   ->  Sort
+         Sort Key: b.x
+         ->  Seq Scan on b
+(13 rows)
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Right 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)
+
+-- No ANTI JOIN, c.z is not 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             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Full 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)
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Full 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)
+
+ALTER TABLE c ADD COLUMN x INT;
+-- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+               QUERY PLAN                
+-----------------------------------------
+ Merge Anti Join
+   Merge Cond: (a.id = b.x)
+   ->  Index Only Scan using a_pkey on a
+   ->  Materialize
+         ->  Merge Join
+               Merge Cond: (b.x = c.x)
+               ->  Sort
+                     Sort Key: b.x
+                     ->  Seq Scan on b
+               ->  Sort
+                     Sort Key: c.x
+                     ->  Seq Scan on c
+(12 rows)
+
+ROLLBACK;
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index b3fb03c..be748db 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -435,3 +435,95 @@ select * from
   order by 1;
 
 select nextval('ts1');
+
+--
+-- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+-- in the target list of the subquery.
+--
+
+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 a left 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 not from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+
+-- No ANTI JOIN, b.x is from an outer join
+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
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z);
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL 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);
+
+ALTER TABLE c ADD COLUMN x INT;
+
+-- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+
+
+ROLLBACK;

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 3e7dc85..4b44662 100644
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
*************** SS_process_ctes(PlannerInfo *root)
*** 1195,1205 ****
   * If so, form a JoinExpr and return it.  Return NULL if the SubLink cannot
   * be converted to a join.
   *
!  * The only non-obvious input parameter is available_rels: this is the set
!  * of query rels that can safely be referenced in the sublink expression.
!  * (We must restrict this to avoid changing the semantics when a sublink
!  * is present in an outer join's ON qual.)  The conversion must fail if
!  * the converted qual would reference any but these parent-query relids.
   *
   * On success, the returned JoinExpr has larg = NULL and rarg = the jointree
   * item representing the pulled-up subquery.  The caller must set larg to
--- 1195,1208 ----
   * If so, form a JoinExpr and return it.  Return NULL if the SubLink cannot
   * be converted to a join.
   *
!  * If under_not is true, the caller actually found NOT (ANY SubLink),
!  * so that what we must try to build is an ANTI not SEMI join.
!  *
!  * available_rels is the set of query rels that can safely be referenced
!  * in the sublink expression.  (We must restrict this to avoid changing the
!  * semantics when a sublink is present in an outer join's ON qual.)
!  * The conversion must fail if the converted qual would reference any but
!  * these parent-query relids.
   *
   * On success, the returned JoinExpr has larg = NULL and rarg = the jointree
   * item representing the pulled-up subquery.  The caller must set larg to
*************** SS_process_ctes(PlannerInfo *root)
*** 1222,1228 ****
   */
  JoinExpr *
  convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
! 							Relids available_rels)
  {
  	JoinExpr   *result;
  	Query	   *parse = root->parse;
--- 1225,1231 ----
   */
  JoinExpr *
  convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
! 							bool under_not, Relids available_rels)
  {
  	JoinExpr   *result;
  	Query	   *parse = root->parse;
*************** convert_ANY_sublink_to_join(PlannerInfo 
*** 1237,1242 ****
--- 1240,1254 ----
  	Assert(sublink->subLinkType == ANY_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.
+ 	 */
+ 	if (under_not && !query_outputs_are_not_nullable(subselect))
+ 		return NULL;
+ 
+ 	/*
  	 * The sub-select must not refer to any Vars of the parent query. (Vars of
  	 * higher levels should be okay, though.)
  	 */
*************** convert_ANY_sublink_to_join(PlannerInfo 
*** 1302,1308 ****
  	 * And finally, build the JoinExpr node.
  	 */
  	result = makeNode(JoinExpr);
! 	result->jointype = JOIN_SEMI;
  	result->isNatural = false;
  	result->larg = NULL;		/* caller must fill this in */
  	result->rarg = (Node *) rtr;
--- 1314,1320 ----
  	 * And finally, build the JoinExpr node.
  	 */
  	result = makeNode(JoinExpr);
! 	result->jointype = under_not ? JOIN_ANTI : JOIN_SEMI;
  	result->isNatural = false;
  	result->larg = NULL;		/* caller must fill this in */
  	result->rarg = (Node *) rtr;
*************** convert_ANY_sublink_to_join(PlannerInfo 
*** 1317,1325 ****
  /*
   * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
   *
!  * The API of this function is identical to convert_ANY_sublink_to_join's,
!  * except that we also support the case where the caller has found NOT EXISTS,
!  * so we need an additional input parameter "under_not".
   */
  JoinExpr *
  convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
--- 1329,1335 ----
  /*
   * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
   *
!  * The API of this function is identical to convert_ANY_sublink_to_join's.
   */
  JoinExpr *
  convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 9cb1378..3a116c7 100644
*** a/src/backend/optimizer/prep/prepjointree.c
--- b/src/backend/optimizer/prep/prepjointree.c
*************** pull_up_sublinks_qual_recurse(PlannerInf
*** 334,340 ****
  		/* Is it a convertible ANY or EXISTS clause? */
  		if (sublink->subLinkType == ANY_SUBLINK)
  		{
! 			if ((j = convert_ANY_sublink_to_join(root, sublink,
  												 available_rels1)) != NULL)
  			{
  				/* Yes; insert the new join node into the join tree */
--- 334,340 ----
  		/* Is it a convertible ANY or EXISTS clause? */
  		if (sublink->subLinkType == ANY_SUBLINK)
  		{
! 			if ((j = convert_ANY_sublink_to_join(root, sublink, false,
  												 available_rels1)) != NULL)
  			{
  				/* Yes; insert the new join node into the join tree */
*************** pull_up_sublinks_qual_recurse(PlannerInf
*** 360,366 ****
  				return NULL;
  			}
  			if (available_rels2 != NULL &&
! 				(j = convert_ANY_sublink_to_join(root, sublink,
  												 available_rels2)) != NULL)
  			{
  				/* Yes; insert the new join node into the join tree */
--- 360,366 ----
  				return NULL;
  			}
  			if (available_rels2 != NULL &&
! 				(j = convert_ANY_sublink_to_join(root, sublink, false,
  												 available_rels2)) != NULL)
  			{
  				/* Yes; insert the new join node into the join tree */
*************** pull_up_sublinks_qual_recurse(PlannerInf
*** 445,458 ****
  	}
  	if (not_clause(node))
  	{
! 		/* If the immediate argument of NOT is EXISTS, try to convert */
  		SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
  		JoinExpr   *j;
  		Relids		child_rels;
  
  		if (sublink && IsA(sublink, SubLink))
  		{
! 			if (sublink->subLinkType == EXISTS_SUBLINK)
  			{
  				if ((j = convert_EXISTS_sublink_to_join(root, sublink, true,
  												   available_rels1)) != NULL)
--- 445,512 ----
  	}
  	if (not_clause(node))
  	{
! 		/* If the immediate argument of NOT is ANY or EXISTS, try to convert */
  		SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
  		JoinExpr   *j;
  		Relids		child_rels;
  
  		if (sublink && IsA(sublink, 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)
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 19b5cf7..f8e3eaa 100644
*** a/src/backend/optimizer/util/clauses.c
--- b/src/backend/optimizer/util/clauses.c
***************
*** 40,45 ****
--- 40,46 ----
  #include "parser/parse_agg.h"
  #include "parser/parse_coerce.h"
  #include "parser/parse_func.h"
+ #include "parser/parsetree.h"
  #include "rewrite/rewriteManip.h"
  #include "tcop/tcopprot.h"
  #include "utils/acl.h"
*************** static bool contain_nonstrict_functions_
*** 100,105 ****
--- 101,108 ----
  static bool contain_leaky_functions_walker(Node *node, void *context);
  static Relids find_nonnullable_rels_walker(Node *node, bool top_level);
  static List *find_nonnullable_vars_walker(Node *node, bool top_level);
+ static void find_innerjoined_rels(Node *jtnode,
+ 					  Relids *innerjoined_rels, List **usable_quals);
  static bool is_strict_saop(ScalarArrayOpExpr *expr, bool falseOK);
  static Node *eval_const_expressions_mutator(Node *node,
  							   eval_const_expressions_context *context);
*************** contain_leaky_functions_walker(Node *nod
*** 1459,1464 ****
--- 1462,1471 ----
  								  context);
  }
  
+ /*****************************************************************************
+  *		  Nullability analysis
+  *****************************************************************************/
+ 
  /*
   * find_nonnullable_rels
   *		Determine which base rels are forced nonnullable by given clause.
*************** find_nonnullable_rels_walker(Node *node,
*** 1685,1691 ****
   * but here we assume that the input is a Boolean expression, and wish to
   * see if NULL inputs will provably cause a FALSE-or-NULL result.  We expect
   * the expression to have been AND/OR flattened and converted to implicit-AND
!  * format.
   *
   * The result is a palloc'd List, but we have not copied the member Var nodes.
   * Also, we don't bother trying to eliminate duplicate entries.
--- 1692,1698 ----
   * but here we assume that the input is a Boolean expression, and wish to
   * see if NULL inputs will provably cause a FALSE-or-NULL result.  We expect
   * the expression to have been AND/OR flattened and converted to implicit-AND
!  * format (but the results are still good if it wasn't AND/OR flattened).
   *
   * The result is a palloc'd List, but we have not copied the member Var nodes.
   * Also, we don't bother trying to eliminate duplicate entries.
*************** find_forced_null_var(Node *node)
*** 1987,1992 ****
--- 1994,2241 ----
  }
  
  /*
+  * 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.
+  *
+  * 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
+  * not return nulls.
+  *
+  * In current usage, the passed sub-Query hasn't yet been through any planner
+  * processing.  This means that applying find_nonnullable_vars() to its WHERE
+  * clauses isn't really ideal: for lack of const-simplification, we might be
+  * unable to prove not-nullness in some cases where we could have proved it
+  * afterwards.  However, we should not get any false positive results.
+  *
+  * Like the other forms of nullability analysis above, we can err on the
+  * side of conservatism: if we're not sure, it's okay to return FALSE.
+  */
+ bool
+ query_outputs_are_not_nullable(Query *query)
+ {
+ 	PlannerInfo subroot;
+ 	Relids		innerjoined_rels = NULL;
+ 	bool		computed_innerjoined_rels = false;
+ 	List	   *usable_quals = NIL;
+ 	List	   *nonnullable_vars = NIL;
+ 	bool		computed_nonnullable_vars = false;
+ 	ListCell   *tl;
+ 
+ 	/*
+ 	 * If the query contains set operations, punt.  The set ops themselves
+ 	 * couldn't introduce nulls that weren't in their inputs, but the tlist
+ 	 * present in the top-level query is just dummy and won't give us useful
+ 	 * info.  We could get an answer by recursing to examine each leaf query,
+ 	 * but for the moment it doesn't seem worth the extra complication.
+ 	 *
+ 	 * Note that we needn't consider other top-level operators such as
+ 	 * DISTINCT, GROUP BY, etc, as those will not introduce nulls either.
+ 	 */
+ 	if (query->setOperations)
+ 		return false;
+ 
+ 	/*
+ 	 * We need a PlannerInfo to pass to flatten_join_alias_vars.  Fortunately,
+ 	 * we can cons up an entirely dummy one, because only the "parse" link in
+ 	 * the struct is used by flatten_join_alias_vars.
+ 	 */
+ 	MemSet(&subroot, 0, sizeof(subroot));
+ 	subroot.parse = query;
+ 
+ 	/*
+ 	 * Examine each targetlist entry to prove that it can't produce NULL.
+ 	 */
+ 	foreach(tl, query->targetList)
+ 	{
+ 		TargetEntry *tle = (TargetEntry *) lfirst(tl);
+ 		Expr	   *expr = tle->expr;
+ 
+ 		/* Resjunk columns can be ignored: they don't produce output values */
+ 		if (tle->resjunk)
+ 			continue;
+ 
+ 		/*
+ 		 * For the most part we don't try to deal with anything more complex
+ 		 * than Consts and Vars; but it seems worthwhile to look through
+ 		 * binary relabelings, since we know those don't introduce nulls.
+ 		 */
+ 		while (expr && IsA(expr, RelabelType))
+ 			expr = ((RelabelType *) expr)->arg;
+ 
+ 		if (expr == NULL)		/* paranoia */
+ 			return false;
+ 
+ 		if (IsA(expr, Const))
+ 		{
+ 			/* Consts are easy: they're either null or not. */
+ 			if (((Const *) expr)->constisnull)
+ 				return false;
+ 		}
+ 		else if (IsA(expr, Var))
+ 		{
+ 			Var		   *var = (Var *) expr;
+ 
+ 			/* Currently, we punt for any nonlocal Vars */
+ 			if (var->varlevelsup != 0)
+ 				return false;
+ 
+ 			/*
+ 			 * Since the subquery hasn't yet been through expression
+ 			 * preprocessing, we must apply flatten_join_alias_vars to the
+ 			 * given Var, and to any Vars found by find_nonnullable_vars, to
+ 			 * avoid being fooled by join aliases.  If we get something other
+ 			 * than a plain Var out of the substitution, punt.
+ 			 */
+ 			var = (Var *) flatten_join_alias_vars(&subroot, (Node *) var);
+ 
+ 			if (!IsA(var, Var))
+ 				return false;
+ 			Assert(var->varlevelsup == 0);
+ 
+ 			/*
+ 			 * We don't bother to compute innerjoined_rels and usable_quals
+ 			 * until we've found a Var we must analyze.
+ 			 */
+ 			if (!computed_innerjoined_rels)
+ 			{
+ 				find_innerjoined_rels((Node *) query->jointree,
+ 									  &innerjoined_rels, &usable_quals);
+ 				computed_innerjoined_rels = true;
+ 			}
+ 
+ 			/*
+ 			 * If Var is from a plain relation, and that relation is not on
+ 			 * the nullable side of any outer join, and its column is marked
+ 			 * NOT NULL according to the catalogs, it can't produce NULL.
+ 			 */
+ 			if (bms_is_member(var->varno, innerjoined_rels))
+ 			{
+ 				RangeTblEntry *rte = rt_fetch(var->varno, query->rtable);
+ 
+ 				if (rte->rtekind == RTE_RELATION &&
+ 					get_attnotnull(rte->relid, var->varattno))
+ 					continue;	/* cannot produce NULL */
+ 			}
+ 
+ 			/*
+ 			 * Even if that didn't work, we can conclude that the Var is not
+ 			 * nullable if find_nonnullable_vars can find a "var IS NOT NULL"
+ 			 * or similarly strict condition among the usable_quals.  Compute
+ 			 * the list of Vars having such quals if we didn't already.
+ 			 */
+ 			if (!computed_nonnullable_vars)
+ 			{
+ 				nonnullable_vars = find_nonnullable_vars((Node *) usable_quals);
+ 				nonnullable_vars = (List *)
+ 					flatten_join_alias_vars(&subroot,
+ 											(Node *) nonnullable_vars);
+ 				/* We don't bother removing any non-Vars from the result */
+ 				computed_nonnullable_vars = true;
+ 			}
+ 
+ 			if (!list_member(nonnullable_vars, var))
+ 				return false;	/* we failed to prove the Var non-null */
+ 		}
+ 		else
+ 		{
+ 			/* Not a Const or Var; punt */
+ 			return false;
+ 		}
+ 	}
+ 
+ 	return true;				/* query cannot emit NULLs */
+ }
+ 
+ /*
+  * find_innerjoined_rels
+  *		Traverse jointree to locate non-outerjoined-rels and quals above them
+  *
+  * We fill innerjoined_rels with the relids of all rels that are not below
+  * the nullable side of any outer join (which would cause their Vars to be
+  * possibly NULL regardless of what's in the catalogs).  In the same scan,
+  * we locate all WHERE and JOIN/ON quals that constrain these rels, and add
+  * them to the usable_quals list (forming a list with implicit-AND semantics).
+  *
+  * Top-level caller must initialize innerjoined_rels/usable_quals to NULL/NIL.
+  */
+ static void
+ find_innerjoined_rels(Node *jtnode,
+ 					  Relids *innerjoined_rels, List **usable_quals)
+ {
+ 	if (jtnode == NULL)
+ 		return;
+ 	if (IsA(jtnode, RangeTblRef))
+ 	{
+ 		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+ 
+ 		*innerjoined_rels = bms_add_member(*innerjoined_rels, varno);
+ 	}
+ 	else if (IsA(jtnode, FromExpr))
+ 	{
+ 		FromExpr   *f = (FromExpr *) jtnode;
+ 		ListCell   *lc;
+ 
+ 		/* All elements of the FROM list are allowable */
+ 		foreach(lc, f->fromlist)
+ 			find_innerjoined_rels((Node *) lfirst(lc),
+ 								  innerjoined_rels, usable_quals);
+ 		/* ... and its WHERE quals are too */
+ 		if (f->quals)
+ 			*usable_quals = lappend(*usable_quals, f->quals);
+ 	}
+ 	else if (IsA(jtnode, JoinExpr))
+ 	{
+ 		JoinExpr   *j = (JoinExpr *) jtnode;
+ 
+ 		switch (j->jointype)
+ 		{
+ 			case JOIN_INNER:
+ 				/* visit both children */
+ 				find_innerjoined_rels(j->larg,
+ 									  innerjoined_rels, usable_quals);
+ 				find_innerjoined_rels(j->rarg,
+ 									  innerjoined_rels, usable_quals);
+ 				/* and grab the ON quals too */
+ 				if (j->quals)
+ 					*usable_quals = lappend(*usable_quals, j->quals);
+ 				break;
+ 
+ 			case JOIN_LEFT:
+ 			case JOIN_SEMI:
+ 			case JOIN_ANTI:
+ 
+ 				/*
+ 				 * Only the left input is possibly non-nullable; furthermore,
+ 				 * the quals of this join don't constrain the left input.
+ 				 * Note: we probably can't see SEMI or ANTI joins at this
+ 				 * point, but if we do, we can treat them like LEFT joins.
+ 				 */
+ 				find_innerjoined_rels(j->larg,
+ 									  innerjoined_rels, usable_quals);
+ 				break;
+ 
+ 			case JOIN_RIGHT:
+ 				/* Reverse of the above case */
+ 				find_innerjoined_rels(j->rarg,
+ 									  innerjoined_rels, usable_quals);
+ 				break;
+ 
+ 			case JOIN_FULL:
+ 				/* Neither side is non-nullable, so stop descending */
+ 				break;
+ 
+ 			default:
+ 				elog(ERROR, "unrecognized join type: %d",
+ 					 (int) j->jointype);
+ 		}
+ 	}
+ 	else
+ 		elog(ERROR, "unrecognized node type: %d",
+ 			 (int) nodeTag(jtnode));
+ }
+ 
+ /*
   * Can we treat a ScalarArrayOpExpr as strict?
   *
   * If "falseOK" is true, then a "false" result can be considered strict,
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 4b5ef99..1d581a8 100644
*** a/src/backend/utils/cache/lsyscache.c
--- b/src/backend/utils/cache/lsyscache.c
*************** get_atttypetypmodcoll(Oid relid, AttrNum
*** 972,977 ****
--- 972,1004 ----
  	ReleaseSysCache(tp);
  }
  
+ /*
+  * get_attnotnull
+  *
+  *		Given the relation id and the attribute number,
+  *		return the "attnotnull" field from the attribute relation.
+  */
+ 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;
+ 
+ 		result = att_tup->attnotnull;
+ 		ReleaseSysCache(tp);
+ 		return result;
+ 	}
+ 	else
+ 		return false;
+ }
+ 
  /*				---------- COLLATION CACHE ----------					 */
  
  /*
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index dd991b1..5b25d01 100644
*** a/src/include/optimizer/clauses.h
--- b/src/include/optimizer/clauses.h
*************** extern Relids find_nonnullable_rels(Node
*** 69,74 ****
--- 69,75 ----
  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 is_pseudo_constant_clause(Node *clause);
  extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids);
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,23 ****
--- 18,24 ----
  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/utils/lsyscache.h b/src/include/utils/lsyscache.h
index f46460a..3ec200a 100644
*** a/src/include/utils/lsyscache.h
--- b/src/include/utils/lsyscache.h
*************** extern Oid	get_atttype(Oid relid, AttrNu
*** 70,75 ****
--- 70,76 ----
  extern int32 get_atttypmod(Oid relid, AttrNumber attnum);
  extern void get_atttypetypmodcoll(Oid relid, AttrNumber attnum,
  					  Oid *typid, int32 *typmod, Oid *collid);
+ extern bool get_attnotnull(Oid relid, AttrNumber attnum);
  extern char *get_collation_name(Oid colloid);
  extern char *get_constraint_name(Oid conoid);
  extern Oid	get_opclass_family(Oid opclass);
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d85a717..b63f7ac 100644
*** a/src/test/regress/expected/subselect.out
--- b/src/test/regress/expected/subselect.out
*************** select nextval('ts1');
*** 803,805 ****
--- 803,1103 ----
        11
  (1 row)
  
+ --
+ -- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+ -- in the target list of the subquery.
+ --
+ 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 a left 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 not from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+                      QUERY PLAN                      
+ -----------------------------------------------------
+  Merge Left Join
+    Merge Cond: (c.z = b.x)
+    ->  Sort
+          Sort Key: c.z
+          ->  Merge Anti Join
+                Merge Cond: (a.id = c.z)
+                ->  Index Only Scan using a_pkey on a
+                ->  Sort
+                      Sort Key: c.z
+                      ->  Seq Scan on c
+    ->  Sort
+          Sort Key: b.x
+          ->  Seq Scan on b
+ (13 rows)
+ 
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
+              QUERY PLAN             
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Right 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)
+ 
+ -- No ANTI JOIN, c.z is not 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             
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Full 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)
+ 
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z);
+              QUERY PLAN             
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Full 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)
+ 
+ ALTER TABLE c ADD COLUMN x INT;
+ -- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+                QUERY PLAN                
+ -----------------------------------------
+  Merge Anti Join
+    Merge Cond: (a.id = b.x)
+    ->  Index Only Scan using a_pkey on a
+    ->  Materialize
+          ->  Merge Join
+                Merge Cond: (b.x = c.x)
+                ->  Sort
+                      Sort Key: b.x
+                      ->  Seq Scan on b
+                ->  Sort
+                      Sort Key: c.x
+                      ->  Seq Scan on c
+ (12 rows)
+ 
+ ROLLBACK;
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index c3b4773..c3ca67f 100644
*** a/src/test/regress/sql/subselect.sql
--- b/src/test/regress/sql/subselect.sql
*************** select * from
*** 444,446 ****
--- 444,538 ----
    order by 1;
  
  select nextval('ts1');
+ 
+ --
+ -- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+ -- in the target list of the subquery.
+ --
+ 
+ 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 a left 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 not from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+ 
+ -- No ANTI JOIN, b.x is from an outer join
+ 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
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z);
+ 
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL 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);
+ 
+ ALTER TABLE c ADD COLUMN x INT;
+ 
+ -- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+ 
+ 
+ ROLLBACK;

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;

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 3e7dc85..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
@@ -1195,11 +1308,14 @@ SS_process_ctes(PlannerInfo *root)
  * If so, form a JoinExpr and return it.  Return NULL if the SubLink cannot
  * be converted to a join.
  *
- * The only non-obvious input parameter is available_rels: this is the set
- * of query rels that can safely be referenced in the sublink expression.
- * (We must restrict this to avoid changing the semantics when a sublink
- * is present in an outer join's ON qual.)  The conversion must fail if
- * the converted qual would reference any but these parent-query relids.
+ * If under_not is true, the caller actually found NOT (ANY SubLink),
+ * so that what we must try to build is an ANTI not SEMI join.
+ *
+ * available_rels is the set of query rels that can safely be referenced
+ * in the sublink expression.  (We must restrict this to avoid changing the
+ * semantics when a sublink is present in an outer join's ON qual.)
+ * The conversion must fail if the converted qual would reference any but
+ * these parent-query relids.
  *
  * On success, the returned JoinExpr has larg = NULL and rarg = the jointree
  * item representing the pulled-up subquery.  The caller must set larg to
@@ -1222,7 +1338,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 +1353,16 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	Assert(sublink->subLinkType == ANY_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 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 && !is_NOTANY_compatible_with_antijoin(parse, sublink))
+		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 +1428,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;
@@ -1317,9 +1443,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 /*
  * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
  *
- * The API of this function is identical to convert_ANY_sublink_to_join's,
- * except that we also support the case where the caller has found NOT EXISTS,
- * so we need an additional input parameter "under_not".
+ * The API of this function is identical to convert_ANY_sublink_to_join's.
  */
 JoinExpr *
 convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 9cb1378..3a116c7 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 */
@@ -445,14 +445,68 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 	}
 	if (not_clause(node))
 	{
-		/* If the immediate argument of NOT is EXISTS, try to convert */
+		/* If the immediate argument of NOT is ANY or EXISTS, try to convert */
 		SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
 		JoinExpr   *j;
 		Relids		child_rels;
 
 		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)
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 19b5cf7..dd02327 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -40,6 +40,7 @@
 #include "parser/parse_agg.h"
 #include "parser/parse_coerce.h"
 #include "parser/parse_func.h"
+#include "parser/parsetree.h"
 #include "rewrite/rewriteManip.h"
 #include "tcop/tcopprot.h"
 #include "utils/acl.h"
@@ -100,6 +101,8 @@ static bool contain_nonstrict_functions_walker(Node *node, void *context);
 static bool contain_leaky_functions_walker(Node *node, void *context);
 static Relids find_nonnullable_rels_walker(Node *node, bool top_level);
 static List *find_nonnullable_vars_walker(Node *node, bool top_level);
+static void find_innerjoined_rels(Node *jtnode,
+					  Relids *innerjoined_rels, List **usable_quals);
 static bool is_strict_saop(ScalarArrayOpExpr *expr, bool falseOK);
 static Node *eval_const_expressions_mutator(Node *node,
 							   eval_const_expressions_context *context);
@@ -1459,6 +1462,10 @@ contain_leaky_functions_walker(Node *node, void *context)
 								  context);
 }
 
+/*****************************************************************************
+ *		  Nullability analysis
+ *****************************************************************************/
+
 /*
  * find_nonnullable_rels
  *		Determine which base rels are forced nonnullable by given clause.
@@ -1685,7 +1692,7 @@ find_nonnullable_rels_walker(Node *node, bool top_level)
  * but here we assume that the input is a Boolean expression, and wish to
  * see if NULL inputs will provably cause a FALSE-or-NULL result.  We expect
  * the expression to have been AND/OR flattened and converted to implicit-AND
- * format.
+ * format (but the results are still good if it wasn't AND/OR flattened).
  *
  * The result is a palloc'd List, but we have not copied the member Var nodes.
  * Also, we don't bother trying to eliminate duplicate entries.
@@ -1987,6 +1994,243 @@ find_forced_null_var(Node *node)
 }
 
 /*
+ * 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
+ * not return nulls.
+ *
+ * In current usage, the passed sub-Query hasn't yet been through any planner
+ * processing.  This means that applying find_nonnullable_vars() to its WHERE
+ * clauses isn't really ideal: for lack of const-simplification, we might be
+ * unable to prove not-nullness in some cases where we could have proved it
+ * afterwards.  However, we should not get any false positive results.
+ *
+ * Like the other forms of nullability analysis above, we can err on the
+ * side of conservatism: if we're not sure, it's okay to return FALSE.
+ */
+bool
+expressions_are_not_nullable(Query *query, List *exprlist)
+{
+	PlannerInfo subroot;
+	Relids		innerjoined_rels = NULL;
+	bool		computed_innerjoined_rels = false;
+	List	   *usable_quals = NIL;
+	List	   *nonnullable_vars = NIL;
+	bool		computed_nonnullable_vars = false;
+	ListCell   *lc;
+
+	/*
+	 * If the query contains set operations, punt.  The set ops themselves
+	 * couldn't introduce nulls that weren't in their inputs, but the tlist
+	 * present in the top-level query is just dummy and won't give us useful
+	 * info.  We could get an answer by recursing to examine each leaf query,
+	 * but for the moment it doesn't seem worth the extra complication.
+	 *
+	 * Note that we needn't consider other top-level operators such as
+	 * DISTINCT, GROUP BY, etc, as those will not introduce nulls either.
+	 */
+	if (query->setOperations)
+		return false;
+
+	/*
+	 * We need a PlannerInfo to pass to flatten_join_alias_vars.  Fortunately,
+	 * we can cons up an entirely dummy one, because only the "parse" link in
+	 * the struct is used by flatten_join_alias_vars.
+	 */
+	MemSet(&subroot, 0, sizeof(subroot));
+	subroot.parse = query;
+
+	/*
+	 * Examine each Expr to prove that it can't produce NULL.
+	 */
+	foreach(lc, exprlist)
+	{
+		Expr *expr = (Expr *) lfirst(lc);
+
+		/*
+		 * For the most part we don't try to deal with anything more complex
+		 * than Consts and Vars; but it seems worthwhile to look through
+		 * binary relabelings, since we know those don't introduce nulls.
+		 */
+		while (expr && IsA(expr, RelabelType))
+			expr = ((RelabelType *) expr)->arg;
+
+		if (expr == NULL)		/* paranoia */
+			return false;
+
+		if (IsA(expr, Const))
+		{
+			/* Consts are easy: they're either null or not. */
+			if (((Const *) expr)->constisnull)
+				return false;
+		}
+		else if (IsA(expr, Var))
+		{
+			Var		   *var = (Var *) expr;
+
+			/* Currently, we punt for any nonlocal Vars */
+			if (var->varlevelsup != 0)
+				return false;
+
+			/*
+			 * Since the subquery hasn't yet been through expression
+			 * preprocessing, we must apply flatten_join_alias_vars to the
+			 * given Var, and to any Vars found by find_nonnullable_vars, to
+			 * avoid being fooled by join aliases.  If we get something other
+			 * than a plain Var out of the substitution, punt.
+			 */
+			var = (Var *) flatten_join_alias_vars(&subroot, (Node *) var);
+
+			if (!IsA(var, Var))
+				return false;
+			Assert(var->varlevelsup == 0);
+
+			/*
+			 * We don't bother to compute innerjoined_rels and usable_quals
+			 * until we've found a Var we must analyze.
+			 */
+			if (!computed_innerjoined_rels)
+			{
+				find_innerjoined_rels((Node *) query->jointree,
+									  &innerjoined_rels, &usable_quals);
+				computed_innerjoined_rels = true;
+			}
+
+			/*
+			 * If Var is from a plain relation, and that relation is not on
+			 * the nullable side of any outer join, and its column is marked
+			 * NOT NULL according to the catalogs, it can't produce NULL.
+			 */
+			if (bms_is_member(var->varno, innerjoined_rels))
+			{
+				RangeTblEntry *rte = rt_fetch(var->varno, query->rtable);
+
+				if (rte->rtekind == RTE_RELATION &&
+					get_attnotnull(rte->relid, var->varattno))
+					continue;	/* cannot produce NULL */
+			}
+
+			/*
+			 * Even if that didn't work, we can conclude that the Var is not
+			 * nullable if find_nonnullable_vars can find a "var IS NOT NULL"
+			 * or similarly strict condition among the usable_quals.  Compute
+			 * the list of Vars having such quals if we didn't already.
+			 */
+			if (!computed_nonnullable_vars)
+			{
+				nonnullable_vars = find_nonnullable_vars((Node *) usable_quals);
+				nonnullable_vars = (List *)
+					flatten_join_alias_vars(&subroot,
+											(Node *) nonnullable_vars);
+				/* We don't bother removing any non-Vars from the result */
+				computed_nonnullable_vars = true;
+			}
+
+			if (!list_member(nonnullable_vars, var))
+				return false;	/* we failed to prove the Var non-null */
+		}
+		else
+		{
+			/* Not a Const or Var; punt */
+			return false;
+		}
+	}
+
+	return true;				/* query cannot emit NULLs */
+}
+
+/*
+ * find_innerjoined_rels
+ *		Traverse jointree to locate non-outerjoined-rels and quals above them
+ *
+ * We fill innerjoined_rels with the relids of all rels that are not below
+ * the nullable side of any outer join (which would cause their Vars to be
+ * possibly NULL regardless of what's in the catalogs).  In the same scan,
+ * we locate all WHERE and JOIN/ON quals that constrain these rels, and add
+ * them to the usable_quals list (forming a list with implicit-AND semantics).
+ *
+ * Top-level caller must initialize innerjoined_rels/usable_quals to NULL/NIL.
+ */
+static void
+find_innerjoined_rels(Node *jtnode,
+					  Relids *innerjoined_rels, List **usable_quals)
+{
+	if (jtnode == NULL)
+		return;
+	if (IsA(jtnode, RangeTblRef))
+	{
+		int			varno = ((RangeTblRef *) jtnode)->rtindex;
+
+		*innerjoined_rels = bms_add_member(*innerjoined_rels, varno);
+	}
+	else if (IsA(jtnode, FromExpr))
+	{
+		FromExpr   *f = (FromExpr *) jtnode;
+		ListCell   *lc;
+
+		/* All elements of the FROM list are allowable */
+		foreach(lc, f->fromlist)
+			find_innerjoined_rels((Node *) lfirst(lc),
+								  innerjoined_rels, usable_quals);
+		/* ... and its WHERE quals are too */
+		if (f->quals)
+			*usable_quals = lappend(*usable_quals, f->quals);
+	}
+	else if (IsA(jtnode, JoinExpr))
+	{
+		JoinExpr   *j = (JoinExpr *) jtnode;
+
+		switch (j->jointype)
+		{
+			case JOIN_INNER:
+				/* visit both children */
+				find_innerjoined_rels(j->larg,
+									  innerjoined_rels, usable_quals);
+				find_innerjoined_rels(j->rarg,
+									  innerjoined_rels, usable_quals);
+				/* and grab the ON quals too */
+				if (j->quals)
+					*usable_quals = lappend(*usable_quals, j->quals);
+				break;
+
+			case JOIN_LEFT:
+			case JOIN_SEMI:
+			case JOIN_ANTI:
+
+				/*
+				 * Only the left input is possibly non-nullable; furthermore,
+				 * the quals of this join don't constrain the left input.
+				 * Note: we probably can't see SEMI or ANTI joins at this
+				 * point, but if we do, we can treat them like LEFT joins.
+				 */
+				find_innerjoined_rels(j->larg,
+									  innerjoined_rels, usable_quals);
+				break;
+
+			case JOIN_RIGHT:
+				/* Reverse of the above case */
+				find_innerjoined_rels(j->rarg,
+									  innerjoined_rels, usable_quals);
+				break;
+
+			case JOIN_FULL:
+				/* Neither side is non-nullable, so stop descending */
+				break;
+
+			default:
+				elog(ERROR, "unrecognized join type: %d",
+					 (int) j->jointype);
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d",
+			 (int) nodeTag(jtnode));
+}
+
+/*
  * Can we treat a ScalarArrayOpExpr as strict?
  *
  * If "falseOK" is true, then a "false" result can be considered strict,
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 4b5ef99..1d581a8 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -972,6 +972,33 @@ get_atttypetypmodcoll(Oid relid, AttrNumber attnum,
 	ReleaseSysCache(tp);
 }
 
+/*
+ * get_attnotnull
+ *
+ *		Given the relation id and the attribute number,
+ *		return the "attnotnull" field from the attribute relation.
+ */
+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;
+
+		result = att_tup->attnotnull;
+		ReleaseSysCache(tp);
+		return result;
+	}
+	else
+		return false;
+}
+
 /*				---------- COLLATION CACHE ----------					 */
 
 /*
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index dd991b1..90f745c 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -69,6 +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 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/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/utils/lsyscache.h b/src/include/utils/lsyscache.h
index f46460a..3ec200a 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -70,6 +70,7 @@ extern Oid	get_atttype(Oid relid, AttrNumber attnum);
 extern int32 get_atttypmod(Oid relid, AttrNumber attnum);
 extern void get_atttypetypmodcoll(Oid relid, AttrNumber attnum,
 					  Oid *typid, int32 *typmod, Oid *collid);
+extern bool get_attnotnull(Oid relid, AttrNumber attnum);
 extern char *get_collation_name(Oid colloid);
 extern char *get_constraint_name(Oid conoid);
 extern Oid	get_opclass_family(Oid opclass);
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d85a717..610c175 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -803,3 +803,372 @@ select nextval('ts1');
       11
 (1 row)
 
+--
+-- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+-- 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);
+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);
+             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
+               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)
+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 a left 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 not from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+                     QUERY PLAN                      
+-----------------------------------------------------
+ Merge Left Join
+   Merge Cond: (c.z = b.x)
+   ->  Sort
+         Sort Key: c.z
+         ->  Merge Anti Join
+               Merge Cond: (a.id = c.z)
+               ->  Index Only Scan using a_pkey on a
+               ->  Sort
+                     Sort Key: c.z
+                     ->  Seq Scan on c
+   ->  Sort
+         Sort Key: b.x
+         ->  Seq Scan on b
+(13 rows)
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Right 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)
+
+-- 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             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Full 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)
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z);
+             QUERY PLAN             
+------------------------------------
+ Seq Scan on a
+   Filter: (NOT (hashed SubPlan 1))
+   SubPlan 1
+     ->  Merge Full 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)
+
+-- 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 b.y FROM b INNER JOIN c ON b.y = c.z);
+               QUERY PLAN                
+-----------------------------------------
+ Merge Anti Join
+   Merge Cond: (a.id = b.y)
+   ->  Index Only Scan using a_pkey on a
+   ->  Materialize
+         ->  Merge Join
+               Merge Cond: (b.y = c.z)
+               ->  Sort
+                     Sort Key: b.y
+                     ->  Seq Scan on b
+               ->  Sort
+                     Sort Key: c.z
+                     ->  Seq Scan on c
+(12 rows)
+
+ROLLBACK;
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index c3b4773..c4f9102 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -444,3 +444,123 @@ select * from
   order by 1;
 
 select nextval('ts1');
+
+--
+-- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+-- 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);
+
+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
+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)
+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 a left 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 not from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+
+-- No ANTI JOIN, b.x is from an outer join
+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 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);
+
+-- No ANTI JOIN, b.x is from an outer join
+EXPLAIN (COSTS OFF)
+SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL 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);
+
+-- 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 b.y FROM b INNER JOIN c ON b.y = c.z);
+
+ROLLBACK;