Wrong results from an antijoin
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
This thread has been committed, so CI has stopped here. Anything below is the last result it produced.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t254117psql -h localhost -U postgresBuilt from patchset v5 (message #5), October 14, 2026 at 02:44 AM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t254117_5 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t254117_5 && git checkout t254117_5Patchset v5 (message #5) is on t254117_5
This query gives wrong results on v16 to master:
create table t1 (a int);
create table t2 (a int primary key);
insert into t1 values (1), (10000);
insert into t2 select generate_series(1, 10000);
analyze t1, t2;
select s.* from t1 left join
(select 2 as c, t1.a as x from t1
where not exists (select 1 from t2 where t2.a = t1.a)) s on true
where s.x = s.c;
c | x
---+-------
2 | 1
2 | 1
2 | 10000
2 | 10000
(4 rows)
Note that the returned rows do not even satisfy the WHERE clause.
This scares me because it seems very easy to hit, and the result is
obviously wrong.
Nested Loop
-> Nested Loop Anti Join
-> Seq Scan on t1 t1_1
-> Index Only Scan using t2_pkey on t2
Index Cond: (a = t1_1.a)
Filter: (t1_1.a = 2)
-> Seq Scan on t1
The qual "s.x = s.c" ends up in the inner side of the antijoin, where
it does the opposite of what it should: an outer row that fails it
finds no match and gets emitted.
The cause is the PHV for s.c. When we pull up the subquery, we set
its phrels to all the relids in the subquery's jointree, and that
includes t2, the RHS of the antijoin made from the NOT EXISTS. Since
the PHV is variable-free, that is also where it is evaluated, so the
qual looks like it references t2 and is taken as a join clause movable
to a parameterized scan of t2.
Compare that with the same query written with a left join that gets
reduced to an antijoin:
select s.* from t1 left join
(select 2 as c, t1.a as x from t1
left join t2 on t1.a = t2.a where t2.a is null) s on true
where s.x = s.c;
Nested Loop
-> Nested Loop Anti Join
Filter: (t1_1.a = 2)
-> Seq Scan on t1 t1_1
-> Index Only Scan using t2_pkey on t2
Index Cond: (a = t1_1.a)
-> Seq Scan on t1
This one is correct. The antijoin has the left join's relid, which is
in phrels and so in the qual's relids, and that keeps the qual above
the join. An antijoin built by pull_up_sublinks() has rtindex 0, on
the assumption that nothing above it can reference its RHS, so there
is nothing to stop the qual.
This goes back to v16. v15 is not affected, although the PHV has the
same phrels there. In v15 check_outerjoin_delay() sees that the qual
overlaps the antijoin's RHS and puts t2 into its nullable_relids, and
join_clause_is_movable_into() then refuses to move it into t2. Both
went away in v16 along with nullable_relids, on the grounds that
clause_relids now mentions any nulling outer join. That doesn't cover
an antijoin with no relid.
We could band-aid the PHVs, by trimming the RHS of such an antijoin
from phrels or ph_eval_at (and maybe ph_lateral too). But we have
enough band-aids on PHVs already. And it's not clear to me that PHVs
are the only thing affected by an antijoin having no relid.
So I think a more principled way is to give the antijoin a relid, just
like an antijoin reduced from a left join has, so that we can leverage
the well-established outer-join relid machinery to keep quals above
it.
I'm writing a patch along these lines, but I'd like to hear what
others think before going too far.
- Richard
On Fri, Oct 9, 2026 at 12:21 PM Richard Guo <guofenglinux@gmail.com> wrote:
So I think a more principled way is to give the antijoin a relid, just
like an antijoin reduced from a left join has, so that we can leverage
the well-established outer-join relid machinery to keep quals above
it.
I'm writing a patch along these lines, but I'd like to hear what
others think before going too far.
Here is the patch I end up with.
Of the join types that IS_OUTER_JOIN() covers, ANTI was the only one
that could lack a relid, and only when it came from a sublink. Now
every outer join has one, so we no longer need the "if (j->rtindex !=
0)" checks in the code.
Any thoughts?
- Richard
Richard Guo <guofenglinux@gmail.com> writes:
On Fri, Oct 9, 2026 at 12:21 PM Richard Guo <guofenglinux@gmail.com> wrote:
So I think a more principled way is to give the antijoin a relid, just
like an antijoin reduced from a left join has, so that we can leverage
the well-established outer-join relid machinery to keep quals above
it.
+1
Here is the patch I end up with.
I'm on board with this solution, and the only real quibble I have with
this patch is that add_antijoin_rte() uses addRangeTableEntryForJoin.
I think that's a substantial abuse of the parser and it's lucky that
it works at all. I realize that convert_ANY_sublink_to_join does
something comparable, but addRangeTableEntryForSubquery feels less
dependent on the state of the parse data structures. In any case
it might be cleaner in the long run for both of those places to build
a RangeTblEntry for themselves (or maybe they could share a function
that does that?)
regards, tom lane
Hi Richard,
Thanks for the patch. I agree that giving sublink-derived antijoins an
RTE and relid is the right and most principled way to prevent improper qual
pushdown into the RHS.
I also agree with Tom's point regarding add_antijoin_rte(): building a dummy
ParseState just to call addRangeTableEntryForJoin() feels like an abuse of
the parser machinery. It would be much cleaner and less fragile to construct
the RangeTblEntry directly via makeNode(RangeTblEntry) in the planner (or
share a helper).
In addition, looking at the regression tests: the patch updates both
convert_EXISTS_sublink_to_join() and convert_ANY_sublink_to_join(), but the
added tests only cover the NOT EXISTS case. It would be great to also add a
test case for NOT IN (which exercises the convert_ANY_sublink_to_join() code
path with under_not = true).
Something like this in src/test/regress/sql/join.sql:
sql
-- Also test NOT IN (convert_ANY_sublink_to_join)
EXPLAIN (COSTS OFF)
SELECT s.*
FROM (VALUES (1)) AS v(z) LEFT JOIN
(SELECT 123456 AS c, t1.f1 AS x FROM int4_tbl t1
WHERE t1.f1 NOT IN (SELECT t2.unique1 FROM tenk1 t2)) s ON true
WHERE s.x = s.c;
SELECT s.*
FROM (VALUES (1)) AS v(z) LEFT JOIN
(SELECT 123456 AS c, t1.f1 AS x FROM int4_tbl t1
WHERE t1.f1 NOT IN (SELECT t2.unique1 FROM tenk1 t2)) s ON true
WHERE s.x = s.c;
Thanks
On Mon, Oct 12, 2026 at 12:56 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm on board with this solution, and the only real quibble I have with
this patch is that add_antijoin_rte() uses addRangeTableEntryForJoin.
I think that's a substantial abuse of the parser and it's lucky that
it works at all. I realize that convert_ANY_sublink_to_join does
something comparable, but addRangeTableEntryForSubquery feels less
dependent on the state of the parse data structures. In any case
it might be cleaner in the long run for both of those places to build
a RangeTblEntry for themselves (or maybe they could share a function
that does that?)
Thanks for looking! Yeah, I chose to use addRangeTableEntryForJoin in
add_antijoin_rte() because I noticed that convert_ANY_sublink_to_join
is using addRangeTableEntryForSubquery. But I agree that this is
abuse of the parser and we should avoid that.
In v2, I updated add_antijoin_rte() to build the RTE by hand, much as
transform_MERGE_to_join() does for its join RTE.
I left convert_ANY_sublink_to_join alone in this patch, since the fix
needs to go back to v16 and that change isn't needed for it. We can
do it as a follow-up cleanup on master.
(I'm not sure about a shared function though. The subquery RTE needs
the subquery, the lateral flag and column names taken from its
targetlist, while the join RTE needs nothing but the jointype, so
about all the two have in common is the makeNode and the lappend.)
- Richard
On Mon, Oct 12, 2026 at 10:57 AM wenhui qiu <qiuwenhuifx@gmail.com> wrote:
In addition, looking at the regression tests: the patch updates both convert_EXISTS_sublink_to_join() and convert_ANY_sublink_to_join(), but the added tests only cover the NOT EXISTS case. It would be great to also add a test case for NOT IN (which exercises the convert_ANY_sublink_to_join() code path with under_not = true).
Makes sense. But the query you suggested doesn't not work.
int4_tbl.f1 and tenk1.unique1 are both nullable, so the NOT IN is not
converted to an antijoin. In v2 I added a NOT IN test that works.
(That test won't be in the back-patches for v16 to v18.)
- Richard
HI Richard
Makes sense. But the query you suggested doesn't not work.
int4_tbl.f1 and tenk1.unique1 are both nullable, so the NOT IN is not
converted to an antijoin. In v2 I added a NOT IN test that works.
(That test won't be in the back-patches for v16 to v18.)Thank you for pointing out the mistake. the v2 path LGTM
Thanks
Richard Guo <guofenglinux@gmail.com> writes:
Thanks for looking! Yeah, I chose to use addRangeTableEntryForJoin in
add_antijoin_rte() because I noticed that convert_ANY_sublink_to_join
is using addRangeTableEntryForSubquery. But I agree that this is
abuse of the parser and we should avoid that.
In v2, I updated add_antijoin_rte() to build the RTE by hand, much as
transform_MERGE_to_join() does for its join RTE.
v2 works for me.
I left convert_ANY_sublink_to_join alone in this patch, since the fix
needs to go back to v16 and that change isn't needed for it. We can
do it as a follow-up cleanup on master.
(I'm not sure about a shared function though. The subquery RTE needs
the subquery, the lateral flag and column names taken from its
targetlist, while the join RTE needs nothing but the jointype, so
about all the two have in common is the makeNode and the lappend.)
Fair enough on both points. convert_ANY_sublink_to_join has been like
that for a long time and hasn't caused trouble, so I'm not in a huge
hurry to change it.
regards, tom lane
On Wed, Oct 14, 2026 at 4:40 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Richard Guo <guofenglinux@gmail.com> writes:
In v2, I updated add_antijoin_rte() to build the RTE by hand, much as
transform_MERGE_to_join() does for its join RTE.
v2 works for me.
Thanks! Pushed and back-patched to v16.
- Richard