Subject: Re: Convert NOT IN sublinks to anti-joins when safe

From: David Geier <[email-masked]>
Date: Wed, 4 Feb 2026 15:59:22 +0100

Hi!

On 04.02.2026 10:47, Richard Guo wrote:
> On Tue, Feb 3, 2026 at 4:12 PM Richard Guo <[email-masked]> wrote:
>> This topic has been discussed several times in the past.  Due to the
>> semantic mismatch regarding NULL handling, NOT IN is not ordinarily
>> equivalent to an anti-join.  However, if we can prove that neither the
>> outer expressions nor the subquery outputs can yield NULL values, it
>> should be safe to convert NOT IN to an anti-join.

I used to play around with query rewrites of the same form, turning NOT
IN into NOT EXISTS. As you rightfully pointed out, the straight forward
rewrite only works if neither the outer expression nor the sub-query
cannot yield NULLs, limiting the optimization considerably. Both cases
can be fixed by amending the basic form of the rewrite.

Basic form:

SELECT t1.c1 FROM t1 WHERE t1.c1 NOT IN (SELECT t2.c1 FROM t2)

=>

SELECT t1.c1 FROM t1 WHERE
  NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1)

If the sub-select can yield NULLs, the rewrite can be fixed by adding an
OR t2.c1 IS NULL clause, such as:

SELECT t1.c1 FROM t1 WHERE
  NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1 OR t2.c1 IS NULL)

which is equivalent to the following SQL which avoids the OR:

SELECT t1.c1 FROM t1 WHERE
  NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1) AND
  NOT EXISTS (SELECT 1 FROM t2 WHERE t2.c1 IS NULL)

If the outer expression can yield NULLs, the rewrite can be fixed by
adding a t1.c1 IS NOT NULL clause, such as:

SELECT t1.c1 FROM T1 WHERE
  t1.c1 IS NOT NULL AND
  NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1)

Both fixes can of course be combined yielding:

SELECT t1.c1 FROM T1 WHERE
  t1.c1 IS NOT NULL AND
  NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1) AND
  NOT EXISTS (SELECT 1 FROM t2 WHERE t2.c1 IS NULL)

What's our today's take on doing more involved transformations inside
the planner to support such cases? It would greatly open up the scope of
the optimization.

> I've noticed a loose end in the v1 patch.
> 
> The semantic gap between NOT IN and anti-join actually exists whenever
> the operator returns NULL.  For NOT IN, if (A op B) returns NULL, then
> NOT (NULL) evaluates to NULL (effectively false), and the row is
> discarded.  In contrast, for an anti-join, if (A op B) returns NULL,
> it implies no match was found, and the anti-join logic dictates that
> the row should be kept.
> 
> To guarantee that (A op B) never returns NULL, the current patch
> verifies that both A and B are non-nullable.  However, this is not
> sufficient.  The "op" might be an operator that returns NULL on
> non-null inputs.
> 
> On the other hand, if "op" does not return NULL on NULL inputs, like
> IS DISTINCT FROM, we technically would not even need to require that A
> and B are non-nullable.
> 
> Is there a convenient way to verify that an operator never returns
> NULL on non-null inputs?  Would it be sufficient to insist that the
> operator belongs to btree opclass (assuming that the strict ordering
> requirements of btree imply this safety)?

There's lots of code that e.g. calls FunctionCall2[Coll]() on operators,
where that function raises an ERROR in case the returned value is NULL.
Hence, I would say it's safe to make that assumption.

Otherwise, you could restrict the check to only builtin operators. For
those we know they have the expected semantics.

--
David Geier

---

From: Richard Guo <[email-masked]>
Date: Thu, 5 Feb 2026 15:09:17 +0900

>   NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1 OR t2.c1 IS NULL)

I'm not sure if this rewrite results in a better plan.  The OR clause
would force a nested loop join, which could be much slower than a
hashed-subplan plan.

>   NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1)

This rewrite doesn't seem correct to me.  If t2 is empty, you would
incorrectly lose the NULL rows from t1 in the final result.

> the planner to support such cases? It would greatly open up the scope of

As mentioned in my initial email, the goal of this patch is not to
handle every possible case, but rather only to handle the basic form
where both sides of NOT IN are provably non-nullable.  This keeps the
code complexity to a minimum, and I believe this would cover the most
common use cases in real world.

- Richard

---

From: wenhui qiu <[email-masked]>
Date: Thu, 5 Feb 2026 15:29:54 +0800

HI Richard
> common use cases in real world.
Agree +1  ,The current path already covers common scenarios and is no less
comprehensive than other databases.I'm already quite pleased that it can be
merged.
Having tested a certain widely used open-source database, I found it unable
to process the following query: `SELECT * FROM join1 WHERE id NOT IN
(SELECT id FROM join2 WHERE id IS NOT NULL);` Note that join2 allows null
values for id.

Thanks

---

From: Richard Guo <[email-masked]>
Date: Wed, 4 Mar 2026 18:33:24 +0900

On Mon, Mar 2, 2026 at 9:50 PM David Geier <[email-masked]> wrote:
> The very last rewrite combines both cases. The rewritten query then
> looks like:
>

I'm still not convinced this rewrite is correct.  As I mentioned
earlier, it breaks down if t2 is empty while t1 contains NULL rows.
For example:

CREATE TABLE t1 (c1 int);
CREATE TABLE t2 (c1 int);
INSERT INTO t1 VALUES (1), (NULL);

SELECT t1.c1 FROM t1 WHERE t1.c1 NOT IN (SELECT t2.c1 FROM t2);
 c1
----
  1

(2 rows)

SELECT t1.c1 FROM T1 WHERE
  t1.c1 IS NOT NULL AND
  NOT EXISTS (SELECT 1 FROM t2 WHERE t1.c1 = t2.c1) AND
  NOT EXISTS (SELECT 1 FROM t2 WHERE t2.c1 IS NULL);
 c1
----
  1
(1 row)

> Seems reasonable to start with the non-NULL variant, though there are
> certainly cases where there's no PK / unique index on the relevant columns.

Yeah.  I don't know how to optimize nullable NOT IN clauses.  It seems
quite difficult to handle safely purely via query transformations.
Maybe we can explore adding a dedicated Null-Aware Anti-Join execution
node, much like Oracle's approach.  But that is definitely beyond the
scope of this current patch.

- Richard

---

From: Richard Guo <[email-masked]>
Date: Wed, 4 Mar 2026 18:52:07 +0900

On Sat, Feb 14, 2026 at 4:37 PM Richard Guo <[email-masked]> wrote:
> On Thu, Feb 5, 2026 at 3:51 PM Richard Guo <[email-masked]> wrote:
> > Attached is the updated patch, which adds the check requiring the
> > operator to be a member of a btree or hash opfamily.

> Attached is another updated patch rebased on current master, with the
> addition of support for RowCompareExpr to handle multi-column ordering
> operations; otherwise unchanged.

Attached is another updated patch rebased on current master, with some
minor cosmetic adjustments; nothing essential has changed.

- Richard

---

From: Japin Li <[email-masked]>
Date: Thu, 05 Mar 2026 09:57:48 +0800

Hi, Richard

> minor cosmetic adjustments; nothing essential has changed.

Thank you for working on this!

Just a quick note: I think `foreach_ptr` is more appropriate here than `foreach`.

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 299b3354f6d..0d31861da7f 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1484,7 +1484,6 @@ sublink_testexpr_is_not_nullable(PlannerInfo *root, SubLink *sublink)
 {
 	Node	   *testexpr = sublink->testexpr;
 	List	   *outer_exprs = NIL;
-	ListCell   *lc;
 
 	/* Punt if sublink is not in the expected format */
 	if (sublink->subLinkType != ANY_SUBLINK || testexpr == NULL)
@@ -1514,10 +1513,8 @@ sublink_testexpr_is_not_nullable(PlannerInfo *root, SubLink *sublink)
 		/* multi-column equality or inequality checks */
 		BoolExpr   *bexpr = (BoolExpr *) testexpr;
 
-		foreach(lc, bexpr->args)
+		foreach_ptr(OpExpr, opexpr, bexpr->args)
 		{
-			OpExpr	   *opexpr = (OpExpr *) lfirst(lc);
-
 			if (!IsA(opexpr, OpExpr))
 				return false;
 
@@ -1537,10 +1534,8 @@ sublink_testexpr_is_not_nullable(PlannerInfo *root, SubLink *sublink)
 		/* multi-column ordering checks */
 		RowCompareExpr *rcexpr = (RowCompareExpr *) testexpr;
 
-		foreach(lc, rcexpr->opnos)
+		foreach_oid(opno, rcexpr->opnos)
 		{
-			Oid			opno = lfirst_oid(lc);
-
 			/* verify operator safety; see comment above */
 			if (!op_is_safe_index_member(opno))
 				return false;
@@ -1566,10 +1561,8 @@ sublink_testexpr_is_not_nullable(PlannerInfo *root, SubLink *sublink)
 		flatten_join_alias_vars(root, root->parse, (Node *) outer_exprs);
 
 	/* Check that every outer expression is non-nullable */
-	foreach(lc, outer_exprs)
+	foreach_ptr(Expr, expr, outer_exprs)
 	{
-		Expr	   *expr = (Expr *) lfirst(lc);
-
 		/*
 		 * We have already collected relation-level not-null constraints for
 		 * the outer query, so we can consult the global hash table for
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index c47c9da4a9b..3f3baf2149a 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -2052,7 +2052,6 @@ query_outputs_are_not_nullable(Query *query)
 	List	   *safe_quals = NIL;
 	List	   *nonnullable_vars = NIL;
 	bool		computed_nonnullable_vars = false;
-	ListCell   *tl;
 
 	/*
 	 * If the query contains set operations, punt.  The set ops themselves
@@ -2083,9 +2082,8 @@ query_outputs_are_not_nullable(Query *query)
 	/*
 	 * Examine each targetlist entry to prove that it can't produce NULL.
 	 */
-	foreach(tl, query->targetList)
+	foreach_ptr(TargetEntry, tle, query->targetList)
 	{
-		TargetEntry *tle = (TargetEntry *) lfirst(tl);
 		Expr	   *expr = tle->expr;
 
 		/* Resjunk columns can be ignored: they don't produce output values */
@@ -2194,11 +2192,10 @@ find_subquery_safe_quals(Node *jtnode, List **safe_quals)
 	else if (IsA(jtnode, FromExpr))
 	{
 		FromExpr   *f = (FromExpr *) jtnode;
-		ListCell   *lc;
 
 		/* All elements of the FROM list are allowable */
-		foreach(lc, f->fromlist)
-			find_subquery_safe_quals((Node *) lfirst(lc), safe_quals);
+		foreach_ptr(Node, node, f->fromlist)
+			find_subquery_safe_quals(node, safe_quals);
 		/* ... and its WHERE quals are too */
 		if (f->quals)
 			*safe_quals = lappend(*safe_quals, f->quals);

> - Richard
>
> [2. text/x-diff; v4-0001-Convert-NOT-IN-sublinks-to-anti-joins-when-safe.patch]...

-- 
Regards,
Japin Li
ChengDu WenWu Information Technology Co., Ltd.

---

From: wenhui qiu <[email-masked]>
Date: Thu, 5 Mar 2026 11:40:13 +0800

HI Japin
> Just a quick note: I think `foreach_ptr` is more appropriate here than
`foreach`.

Thank you review this path , I think using foreach_node should be safe
```
#define foreach_ptr(type, var, lst) foreach_internal(type, *, var, lst,
lfirst)
#define foreach_int(var, lst) foreach_internal(int, , var, lst, lfirst_int)
#define foreach_oid(var, lst) foreach_internal(Oid, , var, lst, lfirst_oid)
#define foreach_xid(var, lst) foreach_internal(TransactionId, , var, lst,
lfirst_xid)

/*
* The internal implementation of the above macros. Do not use directly.
*
* This macro actually generates two loops in order to declare two variables
of
* different types. The outer loop only iterates once, so we expect
optimizing
* compilers will unroll it, thereby optimizing it away.
*/
#define foreach_internal(type, pointer, var, lst, func) \
for (type pointer var = 0, pointer var##__outerloop = (type pointer) 1; \
var##__outerloop; \
var##__outerloop = 0) \
for (ForEachState var##__state = {(lst), 0}; \
(var##__state.l != NIL && \
var##__state.i < var##__state.l->length && \
(var = (type pointer) func(&var##__state.l->elements[var##__state.i]), true));
\
var##__state.i++)

/*
* foreach_node -
* The same as foreach_ptr, but asserts that the element is of the specified
* node type.
*/
#define foreach_node(type, var, lst) \
for (type * var = 0, *var##__outerloop = (type *) 1; \
var##__outerloop; \
var##__outerloop = 0) \
for (ForEachState var##__state = {(lst), 0}; \
(var##__state.l != NIL && \
var##__state.i < var##__state.l->length && \
(var = lfirst_node(type, &var##__state.l->elements[var##__state.i]), true));
\
var##__state.i++)

```

On Thu, Mar 5, 2026 at 9:58 AM Japin Li <[email-masked]> wrote:

> > [2. text/x-diff;
> v4-0001-Convert-NOT-IN-sublinks-to-anti-joins-when-safe.patch]...
>
> --
> Regards,
> Japin Li

---

From: Richard Guo <[email-masked]>
Date: Sun, 8 Mar 2026 17:16:58 +0900

> Just a quick note: I think `foreach_ptr` is more appropriate here than `foreach`.

Agreed.

For homogeneous lists, it is better to use foreach_node so we get the
additional type-safety assertions in dev builds.  For heterogeneous
lists, we should use foreach_ptr.

Attached is an updated version of the patch that replaces foreach with
foreach_ptr or foreach_node accordingly.  Nothing else has changed.

I plan to do one more round of self-review on this.  Unless there are
any further thoughts or concerns, I'm hoping to commit this in a week
or two.  Please let me know if anyone spots anything else I might have
missed.

- Richard

---

From: Richard Guo <[email-masked]>
Date: Mon, 9 Mar 2026 13:01:14 +0900

> or two.  Please let me know if anyone spots anything else I might have

I just finished a final self-review and noticed a subtle issue in
query_outputs_are_not_nullable().  When preparing a target expression
for the non-nullability check, the previous code flattened join
aliases Vars before grouping Vars.  However, because the parser
processes FROM/JOIN clauses before the GROUP BY clause, a grouping Var
can actually wrap a join alias Var, not the reverse.  So we should
flatten grouping Vars first.

Attached is an updated patch that fixes that issue.  I plan to commit
this in a week or two, barring any objections.

- Richard

---

From: Japin Li <[email-masked]>
Date: Mon, 09 Mar 2026 13:14:38 +0800

> or two.  Please let me know if anyone spots anything else I might have

Thanks for updating the patch. LGTM.

---

From: wenhui qiu <[email-masked]>
Date: Mon, 9 Mar 2026 15:38:11 +0800

HI

> this in a week or two, barring any objections.

Thanks for updating the patch. v6 path LGTM.

Thanks

---

From: Richard Guo <[email-masked]>
Date: Thu, 12 Mar 2026 11:14:46 +0900

> Thanks for updating the patch. v6 path LGTM.

Thanks!  Committed with a few minor cosmetic tweaks.

- Richard