Planner : anti-join on left joins

Nicolas Adenis-Lamarre <nicolas.adenis.lamarre@gmail.com> writes:

- detect anti join on "a left join b where x is null" where x is a non null
var b (b being a rte)
this is the object of the attached patched.

This is a perfectly reasonable thing to do, especially now that we've
built out some infrastructure that would help. It doesn't look like
your patch is using that though. Take a look at commits 904f6a593
and e2debb643.

BTW, it is not a good look for even a draft patch to not bother
updating adjacent comments that it falsifies, such as this in
reduce_outer_joins_pass2:

* See if we can reduce JOIN_LEFT to JOIN_ANTI. This is the case if
* the join's own quals are strict for any var that was forced null by
* higher qual levels. NOTE: there are other ways that we could
* detect an anti-join, in particular if we were to check whether Vars
* coming from the RHS must be non-null because of table constraints.
* That seems complicated and expensive though (in particular, one
* would have to be wary of lower outer joins). For the moment this
* seems sufficient.

In the long run, the comments are as important as the code, if not
even more so. Keeping them accurate is not optional.

- remove unrequirered distinct, group by (select distinct id_unique from
people;)

Perhaps. Not sure it's worth the trouble.

- remove double order (select * from (select * from a order by x) order by
y) (where * doesn't containt functions based on row nums)

I'd be inclined to think this is a bad idea. If someone wrote that
they probably had a reason to want a double sort.

regards, tom lane

On Wed, 31 Dec 2025 at 22:59, Nicolas Adenis-Lamarre
<nicolas.adenis.lamarre@gmail.com> wrote:

I'm a beginner about postgresql code (but i patched a lot of opensource programs while working on a linux distro).

Welcome.

There are some optimisations at the planner level that are not mandatory when you know how it works, but all the year, i get query to optimize because people doesn't know the pg internals or write not well written queries. So, the patches i would like to suggest are more "non mandatory optimisations".

like:
- detect anti join on "a left join b where x is null" where x is a non null var b (b being a rte)
this is the object of the attached patched.
it is not finished, but working for a demonstation (this is a quick and dirty patch just to try if i were able to do it).
it shows me that it has drawbacks : for example : it requires to know the details on some tables sooner on the planner, (and thus, sometimes, before we detect that we could just remove a table => so we build some tables for nothing except optimisations)

Please look at find_relation_notnullatts(). You may be able to check
the forced_null_vars against that Bitmapset, with care to offset by
FirstLowInvalidHeapAttributeNumber.

- remove unrequirered distinct, group by (select distinct id_unique from people;)

There's been work in that area before. Please search the archives for
UniqueKeys ([1]https://www.postgresql.org/search/?m=1&amp;q=UniqueKeys&amp;l=1&amp;d=-1&amp;s=d).

- remove double order (select * from (select * from a order by x) order by y) (where * doesn't containt functions based on row nums)

I think you risk breaking quite a few things there. There'd be quite a
large number of reasons to not do this and it seems quite difficult to
think of all of them upfront, which you'd need to do.

- detect anti join on "not in(...)"

A few people have worked in that area before (some of it in [2]/messages/by-id/3793.1565689764@linux-edt6, but I
think there was a more recent effort too). It might be worth reviewing
those discussions. Keep in mind that since then, the planner has more
infrastructure to know if Vars or Exprs can be NULL.

- have a way to view the rewritten query ? (like explain)

I don't know what that means. It's not like there's a way to express
all the optimisations that were applied back into SQL.

David

[1]: https://www.postgresql.org/search/?m=1&amp;q=UniqueKeys&amp;l=1&amp;d=-1&amp;s=d
[2]: /messages/by-id/3793.1565689764@linux-edt6

Tom Lane <tgl@sss.pgh.pa.us> 于2026年1月1日周四 07:37写道：

Nicolas Adenis-Lamarre <nicolas.adenis.lamarre@gmail.com> writes:

- detect anti join on "a left join b where x is null" where x is a non

null

var b (b being a rte)
this is the object of the attached patched.

This is a perfectly reasonable thing to do, especially now that we've
built out some infrastructure that would help. It doesn't look like
your patch is using that though. Take a look at commits 904f6a593
and e2debb643.

Yes, after commits 904f6a593 and e2debb643, we have some infrastructure to
use.
I provided a patch to implement this reduction using these infrastructure
codes.
Please check the attached patch.

BTW, it is not a good look for even a draft patch to not bother
updating adjacent comments that it falsifies, such as this in
reduce_outer_joins_pass2:

* See if we can reduce JOIN_LEFT to JOIN_ANTI. This is the case
if
* the join's own quals are strict for any var that was forced
null by
* higher qual levels. NOTE: there are other ways that we could
* detect an anti-join, in particular if we were to check whether
Vars
* coming from the RHS must be non-null because of table
constraints.
* That seems complicated and expensive though (in particular, one
* would have to be wary of lower outer joins). For the moment this
* seems sufficient.

In the long run, the comments are as important as the code, if not
even more so. Keeping them accurate is not optional.

I updated the comments in the attached patch as well.
And I test the regression in the src, all tests pass.
Any thoughts?

--
Thanks,
Tender Wang

Thanks a lot for your answers.

In the long run, the comments are as important as the code

Reading postgresql comments as a book is something i really enjoy. it
increases the learning curve by two orders of magnitude.

@Tender Wang
thanks a lot. about, the patch, i've some points:

- 1
in my original patch, i added the following test to avoid computing things
like find_nonnullable_vars
it is a minor improvement, i don't know if that should be kept.
+ if(forced_null_vars != NIL)

- 2
i added locally some regressions tests for such detection, but i needed to
add cols to tenk1 cause tenk1 has no "not null" columns nor primary keys.
i'm too new to tell if that's the correct way to do. however, i think that
such regression tests must be added as it was already the case for the
existing anti join detection (and it were on the tenk1 table).

- 3
your patch seems to not work on 2 of my tests (the 2nd one is not working
with my patch too)
* when rhl is a subquery

select p.firstname
from people p
left join (select 5 aa, id_husband, divorce_place from mariages left join
people on mariages.id_wife = people.id) m on m.id_husband = p.id
where divorce_place is not null -- divorce_place was set not null for my
tests

* when b.z is a constant from a subquery (but while the previous one
didn't, in your case, i guess it is normal)
select p.firstname
from people p
left join (select 5 aa, id_husband, divorce_place from mariages left join
people on mariages.id_wife = people.id) m on m.id_husband = p.id
where aa is not null

I will review the commits and suggestions you told me to continue to learn,
I will reanalyze your patch more carefully to see why my tests are not ok.
but i'm new, i need more time.

Le jeu. 1 janv. 2026 à 07:24, Tender Wang <tndrwang@gmail.com> a écrit :

Hi

čt 1. 1. 2026 v 10:34 odesílatel Nicolas Adenis-Lamarre <
nicolas.adenis.lamarre@gmail.com> napsal:

Thanks a lot for your answers.

In the long run, the comments are as important as the code

Reading postgresql comments as a book is something i really enjoy. it
increases the learning curve by two orders of magnitude.

@Tender Wang
thanks a lot. about, the patch, i've some points:

- 1
in my original patch, i added the following test to avoid computing things
like find_nonnullable_vars
it is a minor improvement, i don't know if that should be kept.
+ if(forced_null_vars != NIL)

- 2
i added locally some regressions tests for such detection, but i needed to
add cols to tenk1 cause tenk1 has no "not null" columns nor primary keys.
i'm too new to tell if that's the correct way to do. however, i think that
such regression tests must be added as it was already the case for the
existing anti join detection (and it were on the tenk1 table).

- 3
your patch seems to not work on 2 of my tests (the 2nd one is not working
with my patch too)
* when rhl is a subquery

select p.firstname
from people p
left join (select 5 aa, id_husband, divorce_place from mariages left join
people on mariages.id_wife = people.id) m on m.id_husband = p.id
where divorce_place is not null -- divorce_place was set not null for my
tests

* when b.z is a constant from a subquery (but while the previous one
didn't, in your case, i guess it is normal)
select p.firstname
from people p
left join (select 5 aa, id_husband, divorce_place from mariages left join
people on mariages.id_wife = people.id) m on m.id_husband = p.id
where aa is not null

I will review the commits and suggestions you told me to continue to learn,
I will reanalyze your patch more carefully to see why my tests are not ok.
but i'm new, i need more time.

Please, don't use top posting style here
https://web.archive.org/web/20230608210806/idallen.com/topposting.html

https://wiki.postgresql.org/wiki/Mailing_Lists

Regards

Pavel

Nicolas Adenis-Lamarre <nicolas.adenis.lamarre@gmail.com> writes:

i added locally some regressions tests for such detection, but i needed to
add cols to tenk1 cause tenk1 has no "not null" columns nor primary keys.
i'm too new to tell if that's the correct way to do.

It is absolutely not. In general, modifying the properties of any
of the commonly-used objects made by test_setup.sql is a bad idea.
There's too much risk of side-effects on other tests. Even if they
don't show visible output changes, the code might now be following
some other code path and thus not testing what was intended. This
seems particularly risky for changes in constraints, which might
change planner decisions.

If you need a table that's not like any existing test table, make a
new one. But in this case it seems like there are probably existing
tests that cover behavior adjacent to what you want to test. Maybe
you can re-use some of their tables and not have to expend test cycles
on building a whole new table.

regards, tom lane

Tender,
sorry, you patch is perfect. I badly tested it this morning. My fault.
There is just the case with the constant that is not handled (select *
from a left join (select 1 const1 from b) x where x.const1 is null)
but i don't think it worth handling it.
I added 2 regresssion tests in case you want to add them to your patch.
The first one is important, the second one is just to confirm that
subqueries are working.
I've added 3 new tables because in test_setup.sql and join.sql there
were no table with not null constraints.

Again, thanks a lot.

Nicolas Adenis-Lamarre <nicolas.adenis.lamarre@gmail.com> 于2026年1月2日周五
06:28写道：

Tender,
sorry, you patch is perfect. I badly tested it this morning. My fault.
There is just the case with the constant that is not handled (select *
from a left join (select 1 const1 from b) x where x.const1 is null)
but i don't think it worth handling it.
I added 2 regresssion tests in case you want to add them to your patch.
The first one is important, the second one is just to confirm that
subqueries are working.
I've added 3 new tables because in test_setup.sql and join.sql there
were no table with not null constraints.

Again, thanks a lot.

Thanks for your provided test cases. I had added it to the v3 patch.
Please have a look at the attached patches.
--
Thanks,
Tender Wang

Tender,

not sure you see one suggestion i did.
just in case you think it may be interesting, i modified for you 0001.

it just add (and reindent) ' if(forced_null_vars != NIL) ' around the
optimisation while most of left join have probably no forced nulls,
and thus it avoids to compute find_nonnullable_vars and
have_var_is_notnull for them.

Nicolas

Hi,

Nicolas Adenis-Lamarre <nicolas.adenis.lamarre@gmail.com> 于2026年1月2日周五
17:19写道：

Tender,

not sure you see one suggestion i did.
just in case you think it may be interesting, i modified for you 0001.

it just add (and reindent) ' if(forced_null_vars != NIL) ' around the
optimisation while most of left join have probably no forced nulls,
and thus it avoids to compute find_nonnullable_vars and
have_var_is_notnull for them.

Nicolas

Yeah, I forgot to add your suggestion. Please check the v4 patch.
I combined the code and tests into one patch and also added it to [1]https://commitfest.postgresql.org/patch/6375/ -- Thanks, Tender Wang
commitfest.

[1]: https://commitfest.postgresql.org/patch/6375/ -- Thanks, Tender Wang
--
Thanks,
Tender Wang

On Mon, Jan 5, 2026 at 7:59 PM Tender Wang <tndrwang@gmail.com> wrote:

Yeah, I forgot to add your suggestion. Please check the v4 patch.
I combined the code and tests into one patch and also added it to [1] commitfest.

I looked through the patch and I like the idea. This is a very nice
optimization opportunity.

Regarding the implementation, I'm afraid that this patch can be wrong
in a couple of cases.

* When checking NOT NULL constraints to see if a var is non-nullable,
this patch overlooks cases where the var can be nullable due to
lower-level outer joins. For example, given tables t1, t2, t3 with
schema (a NOT NULL, b, c), this patch would produce an incorrect plan
for the query below.

explain (costs off)
select * from t1 left join
(t2 left join t3 on t2.c = t3.c) on t1.b = t2.b
where t3.a is null;
QUERY PLAN
----------------------------------------
Hash Anti Join
Hash Cond: (t1.b = t2.b)
-> Seq Scan on t1
-> Hash
-> Hash Left Join
Hash Cond: (t2.c = t3.c)
-> Seq Scan on t2
-> Hash
-> Seq Scan on t3
(9 rows)

Although t3.a references a not-null column, it can become null due to
the t2/t3 join. So the upper left join should not be reduced to an
anti join.

* This patch doesn't account for inheritance parent tables, where some
child tables might have a NOT NULL constraint for a column while
others do not.

The second point is straightforward to fix, but the first is more
tricky since we did not record varnullingrels in forced_null_vars.
One simple fix would be to only perform this optimization when
right_state->contains_outer is false (meaning no outer joins exist in
the RHS). However, this would be too restrictive and miss many
optimization opportunities.

Instead, I'm considering recording the relids of base rels that are
nullable within each subtree in reduce_outer_joins_pass1_state. This
would allow us to skip Vars that come from those rels when checking
NOT NULL constraints. Something like attached.

- Richard

Richard Guo <guofenglinux@gmail.com> 于2026年1月5日周一 21:26写道：

On Mon, Jan 5, 2026 at 7:59 PM Tender Wang <tndrwang@gmail.com> wrote:

Yeah, I forgot to add your suggestion. Please check the v4 patch.
I combined the code and tests into one patch and also added it to [1]

commitfest.

I looked through the patch and I like the idea. This is a very nice
optimization opportunity.

Regarding the implementation, I'm afraid that this patch can be wrong
in a couple of cases.

* When checking NOT NULL constraints to see if a var is non-nullable,
this patch overlooks cases where the var can be nullable due to
lower-level outer joins. For example, given tables t1, t2, t3 with
schema (a NOT NULL, b, c), this patch would produce an incorrect plan
for the query below.

explain (costs off)
select * from t1 left join
(t2 left join t3 on t2.c = t3.c) on t1.b = t2.b
where t3.a is null;
QUERY PLAN
----------------------------------------
Hash Anti Join
Hash Cond: (t1.b = t2.b)
-> Seq Scan on t1
-> Hash
-> Hash Left Join
Hash Cond: (t2.c = t3.c)
-> Seq Scan on t2
-> Hash
-> Seq Scan on t3
(9 rows)

Although t3.a references a not-null column, it can become null due to
the t2/t3 join. So the upper left join should not be reduced to an
anti join.

Yes, you're right.
I forgot to handle this case. Good example.

* This patch doesn't account for inheritance parent tables, where some
child tables might have a NOT NULL constraint for a column while
others do not.

Yeah, another case I forgot to handle.

The second point is straightforward to fix, but the first is more
tricky since we did not record varnullingrels in forced_null_vars.
One simple fix would be to only perform this optimization when
right_state->contains_outer is false (meaning no outer joins exist in
the RHS). However, this would be too restrictive and miss many
optimization opportunities.

Instead, I'm considering recording the relids of base rels that are
nullable within each subtree in reduce_outer_joins_pass1_state. This
would allow us to skip Vars that come from those rels when checking
NOT NULL constraints. Something like attached.

I looked through the v5 patch. I don't think there's any objection from me.
To nitpick,
...
SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.z IS NULL;
* If we can prove that b.z must be non-null for any matching row, either
* because the join clause is strict for b.z, or because b.z is defined NOT
* NULL by table constraints,
...
How can the strict join clause influence b.z?
...
SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.y IS NULL;
...
The original query in the comments, I can understand. If the join clause is
strict, the b.y of the matched row can't be null.

--
Thanks,
Tender Wang

On Tue, Jan 6, 2026 at 10:47 AM Tender Wang <tndrwang@gmail.com> wrote:

...
SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.z IS NULL;
* If we can prove that b.z must be non-null for any matching row, either
* because the join clause is strict for b.z, or because b.z is defined NOT
* NULL by table constraints,
...
How can the strict join clause influence b.z?

The logic 'strict for b.z' effectively applies only if b.z happens to
be the join key b.y. To avoid confusion, I have rephrased the comment
to make this distinction clear.

I've also included a commit message, refined the comments throughout,
and added test cases in the updated patch.

Feedback and testing are very welcome.

- Richard

HI Richard

The logic 'strict for b.z' effectively applies only if b.z happens to
be the join key b.y. To avoid confusion, I have rephrased the comment
to make this distinction clear.

I've also included a commit message, refined the comments throughout,
and added test cases in the updated patch.

Feedback and testing are very welcome.

The v6 path correctly extends LEFT→ANTI join reduction using NOT NULL
constraints, carefully accounting for nullability introduced by lower-level
outer joins; the approach is sound, well-contained, and adequately covered
by regression tests. LGTM

Thanks

On Tue, Jan 6, 2026 at 4:24 PM Richard Guo <guofenglinux@gmail.com> wrote:

On Tue, Jan 6, 2026 at 5:23 PM Richard Guo <guofenglinux@gmail.com> wrote:

The logic 'strict for b.z' effectively applies only if b.z happens to
be the join key b.y. To avoid confusion, I have rephrased the comment
to make this distinction clear.

I've also included a commit message, refined the comments throughout,
and added test cases in the updated patch.

Feedback and testing are very welcome.

I've pushed this patch.

- Richard

Richard Guo <guofenglinux@gmail.com> 于2026年2月12日周四 14:43写道：

On Tue, Jan 6, 2026 at 5:23 PM Richard Guo <guofenglinux@gmail.com> wrote:

The logic 'strict for b.z' effectively applies only if b.z happens to
be the join key b.y. To avoid confusion, I have rephrased the comment
to make this distinction clear.

I've also included a commit message, refined the comments throughout,
and added test cases in the updated patch.

Feedback and testing are very welcome.

I've pushed this patch.

- Richard

Thanks for making this optimization workable and pushing.

--
Thanks,
Tender Wang