pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedBUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
9+ messages / 3 participants
[nested] [flat]
Commits from this thread:
2024-07-08 0ffc0acaf3 cccab85c2b 507f2347e7 Fix right-anti-joins when the inner relation is proven unique
* BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
@ 2024-06-24 18:16 PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 9+ messages in thread
From: PG Bug reporting form @ 2024-06-24 18:16 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: antti@lampinen.eu
The following bug has been logged on the website:
Bug reference: 18522
Logged by: Antti Lampinen
Email address: antti@lampinen.eu
PostgreSQL version: 16.3
Operating system: AWS RDS + Macos
Description:
The following two queries result in different query plans and different
results, even though there is only a dummy condition change between them.
The
latter results are correct, there are two rows that match the conditions.
The following was run both in AWS RDS and after restoring database from
plain
SQL dump to local Macos system.
First query.
EXPLAIN (ANALYZE, SETTINGS, VERBOSE )
SELECT id, market_id
FROM "order"
WHERE "order"."deleted_at" IS NULL AND
"order"."archived_at" IS NULL AND
NOT EXISTS (SELECT
FROM "matchmaking_request"
WHERE ("matchmaking_request"."order_id" = "order"."id"
AND
"matchmaking_request"."started_at" IS NOT NULL
AND
"matchmaking_request"."cancelled_at" IS NULL))
AND
"order"."market_id" IN (1);
QUERY PLAN
Merge Right Anti Join (cost=415.85..527.39 rows=350 width=8) (actual
time=6.015..6.018 rows=1 loops=1)
Output: "order".id, "order".market_id
Inner Unique: true
Merge Cond: (matchmaking_request.order_id = "order".id)
-> Index Scan using matchmaking_request_order_id_idx on
public.matchmaking_request (cost=0.28..834.07 rows=5840 width=4) (actual
time=0.032..2.089 rows=702 loops=1)
Output: <retracted>
Filter: ((matchmaking_request.started_at IS NOT NULL) AND
(matchmaking_request.cancelled_at IS NULL))
Rows Removed by Filter: 301
-> Sort (cost=415.56..416.82 rows=503 width=8) (actual time=3.695..3.730
rows=493 loops=1)
Output: "order".id, "order".market_id
Sort Key: "order".id
Sort Method: quicksort Memory: 40kB
-> Index Scan using order_market_id_idx on public."order"
(cost=0.28..392.99 rows=503 width=8) (actual time=0.035..3.555 rows=493
loops=1)
Output: "order".id, "order".market_id
Index Cond: ("order".market_id = 1)
Filter: (("order".deleted_at IS NULL) AND ("order".archived_at
IS NULL))
Rows Removed by Filter: 871
Settings: random_page_cost = '1'
Planning Time: 0.643 ms
Execution Time: 6.301 ms
Second query. Note the dummy condition at the end.
EXPLAIN (ANALYZE, SETTINGS, VERBOSE )
SELECT id, market_id
FROM "order"
WHERE "order"."deleted_at" IS NULL AND
"order"."archived_at" IS NULL AND
NOT EXISTS (SELECT
FROM "matchmaking_request"
WHERE ("matchmaking_request"."order_id" = "order"."id"
AND
"matchmaking_request"."started_at" IS NOT NULL
AND
"matchmaking_request"."cancelled_at" IS NULL))
AND
"order"."market_id" IN (1, 1); -- dummy condition
QUERY PLAN
Merge Anti Join (cost=0.56..579.56 rows=503 width=8) (actual
time=6.622..6.773 rows=2 loops=1)
Output: "order".id, "order".market_id
Merge Cond: ("order".id = matchmaking_request.order_id)
-> Index Scan using order_pkey on public."order" (cost=0.28..467.77
rows=723 width=8) (actual time=0.078..4.435 rows=493 loops=1)
Output: <retracted>
Filter: (("order".deleted_at IS NULL) AND ("order".archived_at IS
NULL) AND ("order".market_id = ANY ('{1,1}'::integer[])))
Rows Removed by Filter: 1935
-> Index Scan using matchmaking_request_order_id_idx on
public.matchmaking_request (cost=0.28..834.07 rows=5840 width=4) (actual
time=0.017..1.996 rows=702 loops=1)
Output: <retracted>
Filter: ((matchmaking_request.started_at IS NOT NULL) AND
(matchmaking_request.cancelled_at IS NULL))
Rows Removed by Filter: 301
Settings: random_page_cost = '1'
Planning Time: 0.629 ms
Execution Time: 6.853 ms
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
@ 2024-06-25 02:07 ` Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Antti Lampinen <antti@lampinen.eu>
2024-07-01 02:55 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
0 siblings, 2 replies; 9+ messages in thread
From: Richard Guo @ 2024-06-25 02:07 UTC (permalink / raw)
To: antti@lampinen.eu; pgsql-bugs@lists.postgresql.org
On Tue, Jun 25, 2024 at 2:37 AM PG Bug reporting form
<noreply@postgresql.org> wrote:
> The following two queries result in different query plans and different
> results, even though there is only a dummy condition change between them.
> The
> latter results are correct, there are two rows that match the conditions.
Thank you for reporting. As far as I recall, this is the first
field-reported bug about the right anti join!
Could you please provide the schema and necessary data for the two
tables to reproduce this bug? If there is a self-contained repro, that
would be great.
Thanks
Richard
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
@ 2024-06-25 04:24 ` Antti Lampinen <antti@lampinen.eu>
2024-06-25 11:54 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
1 sibling, 1 reply; 9+ messages in thread
From: Antti Lampinen @ 2024-06-25 04:24 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, Jun 25, 2024 at 5:07 AM Richard Guo <guofenglinux@gmail.com> wrote:
>
> On Tue, Jun 25, 2024 at 2:37 AM PG Bug reporting form
> <noreply@postgresql.org> wrote:
> > The following two queries result in different query plans and different
> > results, even though there is only a dummy condition change between them.
> > The
> > latter results are correct, there are two rows that match the conditions.
>
> Could you please provide the schema and necessary data for the two
> tables to reproduce this bug? If there is a self-contained repro, that
> would be great.
I managed to create a self-contained repro:
https://gist.github.com/arlampin/0b86963694a936147383f3af3c83224c
This gives me consistently different results based on superfluous condition
change. See the two EXPLAIN queries in the sample.
Thanks,
Antti
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Antti Lampinen <antti@lampinen.eu>
@ 2024-06-25 11:54 ` Richard Guo <guofenglinux@gmail.com>
2024-06-25 14:45 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 9+ messages in thread
From: Richard Guo @ 2024-06-25 11:54 UTC (permalink / raw)
To: Antti Lampinen <antti@lampinen.eu>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, Jun 25, 2024 at 12:24 PM Antti Lampinen <antti@lampinen.eu> wrote:
> On Tue, Jun 25, 2024 at 5:07 AM Richard Guo <guofenglinux@gmail.com> wrote:
> > Could you please provide the schema and necessary data for the two
> > tables to reproduce this bug? If there is a self-contained repro, that
> > would be great.
> I managed to create a self-contained repro:
> https://gist.github.com/arlampin/0b86963694a936147383f3af3c83224c
>
> This gives me consistently different results based on superfluous condition
> change. See the two EXPLAIN queries in the sample.
Thank you so much for the repro script. I've found the root cause:
for an inner_unique join we assume that the executor will stop scanning
for matches after the first match. Therefore, we set skip_mark_restore
to true to indicate that we can skip mark/restore overhead. However,
merge right anti join does not get this memo and continues scanning the
inner side for matches after the first match, totally ignoring the
single_match flag, while still thinking that it can skip mark/restore.
Will fix this later.
Thanks
Richard
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Antti Lampinen <antti@lampinen.eu>
2024-06-25 11:54 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
@ 2024-06-25 14:45 ` Richard Guo <guofenglinux@gmail.com>
2024-06-26 07:31 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 9+ messages in thread
From: Richard Guo @ 2024-06-25 14:45 UTC (permalink / raw)
To: Antti Lampinen <antti@lampinen.eu>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, Jun 25, 2024 at 7:54 PM Richard Guo <guofenglinux@gmail.com> wrote:
> Thank you so much for the repro script. I've found the root cause:
> for an inner_unique join we assume that the executor will stop scanning
> for matches after the first match. Therefore, we set skip_mark_restore
> to true to indicate that we can skip mark/restore overhead. However,
> merge right anti join does not get this memo and continues scanning the
> inner side for matches after the first match, totally ignoring the
> single_match flag, while still thinking that it can skip mark/restore.
>
> Will fix this later.
I think we can fix this issue by ensuring that merge-right-anti-join
also advances to next outer tuple after the first match in inner_unique
cases. This can also help save cycles by avoiding unnecessary scanning
of inner tuples after the first match.
Although hash-right-anti-join does not suffer from this wrong results
issue, I think we can apply the same change to it as well, to help save
cycles for the same reason.
Please see attached patch for the fix. This patch still lacks a test
case. I'll try to see if I can come up with one.
Thanks
Richard
Attachments:
v1-0001-Fix-right-anti-joins-when-the-inner-relation-is-proven-unique.patch (application/octet-stream, 4.2K) download
From fa4b30cad222e474013d6fd03996d0e7c8c8520d Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 25 Jun 2024 23:21:10 +0900
Subject: [PATCH v1] Fix right-anti-joins when the inner relation is proven
unique
For an inner_unique join, we always assume that the executor will stop
scanning for matches after the first match. Therefore, for a mergejoin
that is inner_unique and whose mergeclauses are sufficient to identify a
match, we set the skip_mark_restore flag to true, indicating that the
executor need not do mark/restore calls. However, merge-right-anti-join
does not get this memo and continues scanning the inner side for matches
after the first match. If there are duplicates in the outer scan, we
may incorrectly skip matching some inner tuples, which can lead to wrong
results.
Here we fix this issue by ensuring that merge-right-anti-join also
advances to next outer tuple after the first match in inner_unique
cases. This also saves cycles by avoiding unnecessary scanning of inner
tuples after the first match.
Although hash-right-anti-join does not suffer from this wrong results
issue, we apply the same change to it as well, to help save cycles for
the same reason.
---
src/backend/executor/nodeHashjoin.c | 21 +++++++++++----------
src/backend/executor/nodeMergejoin.c | 21 +++++++++++----------
2 files changed, 22 insertions(+), 20 deletions(-)
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index dbf114cd5e..f7de96a368 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -565,20 +565,21 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
}
/*
- * In a right-antijoin, we never return a matched tuple.
- * And we need to stay on the current outer tuple to
- * continue scanning the inner side for matches.
+ * If we only need to consider the first matching inner
+ * tuple, then advance to next outer tuple after we've
+ * processed this one.
*/
- if (node->js.jointype == JOIN_RIGHT_ANTI)
- continue;
+ if (node->js.single_match)
+ node->hj_JoinState = HJ_NEED_NEW_OUTER;
/*
- * If we only need to join to the first matching inner
- * tuple, then consider returning this one, but after that
- * continue with next outer tuple.
+ * In a right-antijoin, we never return a matched tuple.
+ * If it's not an inner_unique join, we need to stay on the
+ * current outer tuple to continue scanning the inner side
+ * for matches.
*/
- if (node->js.single_match)
- node->hj_JoinState = HJ_NEED_NEW_OUTER;
+ if (node->js.jointype == JOIN_RIGHT_ANTI)
+ continue;
if (otherqual == NULL || ExecQual(otherqual, econtext))
return ExecProject(node->js.ps.ps_ProjInfo);
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 4fb34e3537..1ea962704e 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -805,20 +805,21 @@ ExecMergeJoin(PlanState *pstate)
}
/*
- * In a right-antijoin, we never return a matched tuple.
- * And we need to stay on the current outer tuple to
- * continue scanning the inner side for matches.
+ * If we only need to consider the first matching inner
+ * tuple, then advance to next outer tuple after we've
+ * processed this one.
*/
- if (node->js.jointype == JOIN_RIGHT_ANTI)
- break;
+ if (node->js.single_match)
+ node->mj_JoinState = EXEC_MJ_NEXTOUTER;
/*
- * If we only need to join to the first matching inner
- * tuple, then consider returning this one, but after that
- * continue with next outer tuple.
+ * In a right-antijoin, we never return a matched tuple.
+ * If it's not an inner_unique join, we need to stay on the
+ * current outer tuple to continue scanning the inner side
+ * for matches.
*/
- if (node->js.single_match)
- node->mj_JoinState = EXEC_MJ_NEXTOUTER;
+ if (node->js.jointype == JOIN_RIGHT_ANTI)
+ break;
qualResult = (otherqual == NULL ||
ExecQual(otherqual, econtext));
--
2.43.0
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Antti Lampinen <antti@lampinen.eu>
2024-06-25 11:54 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 14:45 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
@ 2024-06-26 07:31 ` Richard Guo <guofenglinux@gmail.com>
2024-07-02 10:22 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 9+ messages in thread
From: Richard Guo @ 2024-06-26 07:31 UTC (permalink / raw)
To: Antti Lampinen <antti@lampinen.eu>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, Jun 25, 2024 at 10:45 PM Richard Guo <guofenglinux@gmail.com> wrote:
> On Tue, Jun 25, 2024 at 7:54 PM Richard Guo <guofenglinux@gmail.com> wrote:
> > Thank you so much for the repro script. I've found the root cause:
> > for an inner_unique join we assume that the executor will stop scanning
> > for matches after the first match. Therefore, we set skip_mark_restore
> > to true to indicate that we can skip mark/restore overhead. However,
> > merge right anti join does not get this memo and continues scanning the
> > inner side for matches after the first match, totally ignoring the
> > single_match flag, while still thinking that it can skip mark/restore.
> >
> > Will fix this later.
>
> I think we can fix this issue by ensuring that merge-right-anti-join
> also advances to next outer tuple after the first match in inner_unique
> cases. This can also help save cycles by avoiding unnecessary scanning
> of inner tuples after the first match.
>
> Although hash-right-anti-join does not suffer from this wrong results
> issue, I think we can apply the same change to it as well, to help save
> cycles for the same reason.
>
> Please see attached patch for the fix. This patch still lacks a test
> case. I'll try to see if I can come up with one.
I've added a test case in the v2 patch. I'll park it in the July
commitfest.
Thanks
Richard
Attachments:
v2-0001-Fix-right-anti-joins-when-the-inner-relation-is-proven-unique.patch (application/octet-stream, 7.1K) download
From 4a197320db0bed586aab2fb7e656ce05bf71980c Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 25 Jun 2024 23:21:10 +0900
Subject: [PATCH v2] Fix right-anti-joins when the inner relation is proven
unique
For an inner_unique join, we always assume that the executor will stop
scanning for matches after the first match. Therefore, for a mergejoin
that is inner_unique and whose mergeclauses are sufficient to identify a
match, we set the skip_mark_restore flag to true, indicating that the
executor need not do mark/restore calls. However, merge-right-anti-join
does not get this memo and continues scanning the inner side for matches
after the first match. If there are duplicates in the outer scan, we
may incorrectly skip matching some inner tuples, which can lead to wrong
results.
Here we fix this issue by ensuring that merge-right-anti-join also
advances to next outer tuple after the first match in inner_unique
cases. This also saves cycles by avoiding unnecessary scanning of inner
tuples after the first match.
Although hash-right-anti-join does not suffer from this wrong results
issue, we apply the same change to it as well, to help save cycles for
the same reason.
---
src/backend/executor/nodeHashjoin.c | 21 +++++------
src/backend/executor/nodeMergejoin.c | 21 +++++------
src/test/regress/expected/join.out | 54 ++++++++++++++++++++++++++++
src/test/regress/sql/join.sql | 24 +++++++++++++
4 files changed, 100 insertions(+), 20 deletions(-)
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index dbf114cd5e..f7de96a368 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -565,20 +565,21 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
}
/*
- * In a right-antijoin, we never return a matched tuple.
- * And we need to stay on the current outer tuple to
- * continue scanning the inner side for matches.
+ * If we only need to consider the first matching inner
+ * tuple, then advance to next outer tuple after we've
+ * processed this one.
*/
- if (node->js.jointype == JOIN_RIGHT_ANTI)
- continue;
+ if (node->js.single_match)
+ node->hj_JoinState = HJ_NEED_NEW_OUTER;
/*
- * If we only need to join to the first matching inner
- * tuple, then consider returning this one, but after that
- * continue with next outer tuple.
+ * In a right-antijoin, we never return a matched tuple.
+ * If it's not an inner_unique join, we need to stay on the
+ * current outer tuple to continue scanning the inner side
+ * for matches.
*/
- if (node->js.single_match)
- node->hj_JoinState = HJ_NEED_NEW_OUTER;
+ if (node->js.jointype == JOIN_RIGHT_ANTI)
+ continue;
if (otherqual == NULL || ExecQual(otherqual, econtext))
return ExecProject(node->js.ps.ps_ProjInfo);
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 4fb34e3537..1ea962704e 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -805,20 +805,21 @@ ExecMergeJoin(PlanState *pstate)
}
/*
- * In a right-antijoin, we never return a matched tuple.
- * And we need to stay on the current outer tuple to
- * continue scanning the inner side for matches.
+ * If we only need to consider the first matching inner
+ * tuple, then advance to next outer tuple after we've
+ * processed this one.
*/
- if (node->js.jointype == JOIN_RIGHT_ANTI)
- break;
+ if (node->js.single_match)
+ node->mj_JoinState = EXEC_MJ_NEXTOUTER;
/*
- * If we only need to join to the first matching inner
- * tuple, then consider returning this one, but after that
- * continue with next outer tuple.
+ * In a right-antijoin, we never return a matched tuple.
+ * If it's not an inner_unique join, we need to stay on the
+ * current outer tuple to continue scanning the inner side
+ * for matches.
*/
- if (node->js.single_match)
- node->mj_JoinState = EXEC_MJ_NEXTOUTER;
+ if (node->js.jointype == JOIN_RIGHT_ANTI)
+ break;
qualResult = (otherqual == NULL ||
ExecQual(otherqual, econtext));
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 6b16c3a676..8d1d3ec1dc 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2923,6 +2923,60 @@ select tt1.*, tt2.* from tt2 right join tt1 on tt1.joincol = tt2.joincol;
2 | | |
(3 rows)
+reset enable_hashjoin;
+reset enable_nestloop;
+--
+-- regression test for bug #18522 (merge-right-anti-join in inner_unique cases)
+--
+create temp table tbl_ra(a int unique, b int);
+insert into tbl_ra select i, i%100 from generate_series(1,1000)i;
+create index on tbl_ra (b);
+analyze tbl_ra;
+set enable_hashjoin to off;
+set enable_nestloop to off;
+-- ensure we get a merge right anti join
+explain (costs off)
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+ QUERY PLAN
+-------------------------------------------------------
+ Merge Right Anti Join
+ Merge Cond: (t2.b = t1.a)
+ -> Index Only Scan using tbl_ra_b_idx on tbl_ra t2
+ -> Sort
+ Sort Key: t1.a
+ -> Bitmap Heap Scan on tbl_ra t1
+ Recheck Cond: (b < 2)
+ -> Bitmap Index Scan on tbl_ra_b_idx
+ Index Cond: (b < 2)
+(9 rows)
+
+-- and check we get the expected results
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+ a | b
+------+---
+ 100 | 0
+ 101 | 1
+ 200 | 0
+ 201 | 1
+ 300 | 0
+ 301 | 1
+ 400 | 0
+ 401 | 1
+ 500 | 0
+ 501 | 1
+ 600 | 0
+ 601 | 1
+ 700 | 0
+ 701 | 1
+ 800 | 0
+ 801 | 1
+ 900 | 0
+ 901 | 1
+ 1000 | 0
+(19 rows)
+
reset enable_hashjoin;
reset enable_nestloop;
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 8bfe3b7ba6..8281bbd8ef 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -693,6 +693,30 @@ select tt1.*, tt2.* from tt2 right join tt1 on tt1.joincol = tt2.joincol;
reset enable_hashjoin;
reset enable_nestloop;
+--
+-- regression test for bug #18522 (merge-right-anti-join in inner_unique cases)
+--
+
+create temp table tbl_ra(a int unique, b int);
+insert into tbl_ra select i, i%100 from generate_series(1,1000)i;
+create index on tbl_ra (b);
+analyze tbl_ra;
+
+set enable_hashjoin to off;
+set enable_nestloop to off;
+
+-- ensure we get a merge right anti join
+explain (costs off)
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+
+-- and check we get the expected results
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+
+reset enable_hashjoin;
+reset enable_nestloop;
+
--
-- regression test for bug #13908 (hash join with skew tuples & nbatch increase)
--
--
2.43.0
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Antti Lampinen <antti@lampinen.eu>
2024-06-25 11:54 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 14:45 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-26 07:31 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
@ 2024-07-02 10:22 ` Richard Guo <guofenglinux@gmail.com>
2024-07-08 02:33 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 9+ messages in thread
From: Richard Guo @ 2024-07-02 10:22 UTC (permalink / raw)
To: Antti Lampinen <antti@lampinen.eu>; +Cc: pgsql-bugs@lists.postgresql.org
On Wed, Jun 26, 2024 at 3:31 PM Richard Guo <guofenglinux@gmail.com> wrote:
> I've added a test case in the v2 patch. I'll park it in the July
> commitfest.
Here is an updated patch, with some tweaks suggested by pgindent, and
adjustments to the commit message suggested by Andrew (off-list).
Barring objections, I'm planning to push it next week.
Thanks
Richard
Attachments:
v3-0001-Fix-right-anti-joins-when-the-inner-relation-is-proven-unique.patch (application/octet-stream, 7.3K) download
From 2e763c2bd2006274a678c195db1373f4499f3114 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 25 Jun 2024 23:21:10 +0900
Subject: [PATCH v3] Fix right-anti-joins when the inner relation is proven
unique
For an inner_unique join, we always assume that the executor will stop
scanning for matches after the first match. Therefore, for a mergejoin
that is inner_unique and whose mergeclauses are sufficient to identify a
match, we set the skip_mark_restore flag to true, indicating that the
executor need not do mark/restore calls. However, merge-right-anti-join
did not get this memo and continues scanning the inner side for matches
after the first match. If there are duplicates in the outer scan, we
may incorrectly skip matching some inner tuples, which can lead to wrong
results.
Here we fix this issue by ensuring that merge-right-anti-join also
advances to next outer tuple after the first match in inner_unique
cases. This also saves cycles by avoiding unnecessary scanning of inner
tuples after the first match.
Although hash-right-anti-join does not suffer from this wrong results
issue, we apply the same change to it as well, to help save cycles for
the same reason.
Per bug #18522 from Antti Lampinen, and bug #18526 from Feliphe Pozzer.
Back-patch to v16 where right-anti-join was introduced.
Author: Richard Guo
Discussion: https://postgr.es/m/18522-c7a8956126afdfd0@postgresql.org
---
src/backend/executor/nodeHashjoin.c | 21 +++++------
src/backend/executor/nodeMergejoin.c | 21 +++++------
src/test/regress/expected/join.out | 54 ++++++++++++++++++++++++++++
src/test/regress/sql/join.sql | 24 +++++++++++++
4 files changed, 100 insertions(+), 20 deletions(-)
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index dbf114cd5e..5f4073eabd 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -565,20 +565,21 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
}
/*
- * In a right-antijoin, we never return a matched tuple.
- * And we need to stay on the current outer tuple to
- * continue scanning the inner side for matches.
+ * If we only need to consider the first matching inner
+ * tuple, then advance to next outer tuple after we've
+ * processed this one.
*/
- if (node->js.jointype == JOIN_RIGHT_ANTI)
- continue;
+ if (node->js.single_match)
+ node->hj_JoinState = HJ_NEED_NEW_OUTER;
/*
- * If we only need to join to the first matching inner
- * tuple, then consider returning this one, but after that
- * continue with next outer tuple.
+ * In a right-antijoin, we never return a matched tuple.
+ * If it's not an inner_unique join, we need to stay on
+ * the current outer tuple to continue scanning the inner
+ * side for matches.
*/
- if (node->js.single_match)
- node->hj_JoinState = HJ_NEED_NEW_OUTER;
+ if (node->js.jointype == JOIN_RIGHT_ANTI)
+ continue;
if (otherqual == NULL || ExecQual(otherqual, econtext))
return ExecProject(node->js.ps.ps_ProjInfo);
diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c
index 4fb34e3537..29c54fcd75 100644
--- a/src/backend/executor/nodeMergejoin.c
+++ b/src/backend/executor/nodeMergejoin.c
@@ -805,20 +805,21 @@ ExecMergeJoin(PlanState *pstate)
}
/*
- * In a right-antijoin, we never return a matched tuple.
- * And we need to stay on the current outer tuple to
- * continue scanning the inner side for matches.
+ * If we only need to consider the first matching inner
+ * tuple, then advance to next outer tuple after we've
+ * processed this one.
*/
- if (node->js.jointype == JOIN_RIGHT_ANTI)
- break;
+ if (node->js.single_match)
+ node->mj_JoinState = EXEC_MJ_NEXTOUTER;
/*
- * If we only need to join to the first matching inner
- * tuple, then consider returning this one, but after that
- * continue with next outer tuple.
+ * In a right-antijoin, we never return a matched tuple.
+ * If it's not an inner_unique join, we need to stay on
+ * the current outer tuple to continue scanning the inner
+ * side for matches.
*/
- if (node->js.single_match)
- node->mj_JoinState = EXEC_MJ_NEXTOUTER;
+ if (node->js.jointype == JOIN_RIGHT_ANTI)
+ break;
qualResult = (otherqual == NULL ||
ExecQual(otherqual, econtext));
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 6b16c3a676..8d1d3ec1dc 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2923,6 +2923,60 @@ select tt1.*, tt2.* from tt2 right join tt1 on tt1.joincol = tt2.joincol;
2 | | |
(3 rows)
+reset enable_hashjoin;
+reset enable_nestloop;
+--
+-- regression test for bug #18522 (merge-right-anti-join in inner_unique cases)
+--
+create temp table tbl_ra(a int unique, b int);
+insert into tbl_ra select i, i%100 from generate_series(1,1000)i;
+create index on tbl_ra (b);
+analyze tbl_ra;
+set enable_hashjoin to off;
+set enable_nestloop to off;
+-- ensure we get a merge right anti join
+explain (costs off)
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+ QUERY PLAN
+-------------------------------------------------------
+ Merge Right Anti Join
+ Merge Cond: (t2.b = t1.a)
+ -> Index Only Scan using tbl_ra_b_idx on tbl_ra t2
+ -> Sort
+ Sort Key: t1.a
+ -> Bitmap Heap Scan on tbl_ra t1
+ Recheck Cond: (b < 2)
+ -> Bitmap Index Scan on tbl_ra_b_idx
+ Index Cond: (b < 2)
+(9 rows)
+
+-- and check we get the expected results
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+ a | b
+------+---
+ 100 | 0
+ 101 | 1
+ 200 | 0
+ 201 | 1
+ 300 | 0
+ 301 | 1
+ 400 | 0
+ 401 | 1
+ 500 | 0
+ 501 | 1
+ 600 | 0
+ 601 | 1
+ 700 | 0
+ 701 | 1
+ 800 | 0
+ 801 | 1
+ 900 | 0
+ 901 | 1
+ 1000 | 0
+(19 rows)
+
reset enable_hashjoin;
reset enable_nestloop;
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 8bfe3b7ba6..8281bbd8ef 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -693,6 +693,30 @@ select tt1.*, tt2.* from tt2 right join tt1 on tt1.joincol = tt2.joincol;
reset enable_hashjoin;
reset enable_nestloop;
+--
+-- regression test for bug #18522 (merge-right-anti-join in inner_unique cases)
+--
+
+create temp table tbl_ra(a int unique, b int);
+insert into tbl_ra select i, i%100 from generate_series(1,1000)i;
+create index on tbl_ra (b);
+analyze tbl_ra;
+
+set enable_hashjoin to off;
+set enable_nestloop to off;
+
+-- ensure we get a merge right anti join
+explain (costs off)
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+
+-- and check we get the expected results
+select * from tbl_ra t1
+where not exists (select 1 from tbl_ra t2 where t2.b = t1.a) and t1.b < 2;
+
+reset enable_hashjoin;
+reset enable_nestloop;
+
--
-- regression test for bug #13908 (hash join with skew tuples & nbatch increase)
--
--
2.43.0
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Antti Lampinen <antti@lampinen.eu>
2024-06-25 11:54 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-25 14:45 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-06-26 07:31 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
2024-07-02 10:22 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
@ 2024-07-08 02:33 ` Richard Guo <guofenglinux@gmail.com>
0 siblings, 0 replies; 9+ messages in thread
From: Richard Guo @ 2024-07-08 02:33 UTC (permalink / raw)
To: Antti Lampinen <antti@lampinen.eu>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, Jul 2, 2024 at 6:22 PM Richard Guo <guofenglinux@gmail.com> wrote:
> Here is an updated patch, with some tweaks suggested by pgindent, and
> adjustments to the commit message suggested by Andrew (off-list).
>
> Barring objections, I'm planning to push it next week.
Pushed. Thank you for the report. The fix will appear in August's
minor releases.
Thanks
Richard
^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Re: BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join Richard Guo <guofenglinux@gmail.com>
@ 2024-07-01 02:55 ` Richard Guo <guofenglinux@gmail.com>
1 sibling, 0 replies; 9+ messages in thread
From: Richard Guo @ 2024-07-01 02:55 UTC (permalink / raw)
To: antti@lampinen.eu; pgsql-bugs@lists.postgresql.org
On Tue, Jun 25, 2024 at 10:07 AM Richard Guo <guofenglinux@gmail.com> wrote:
> Thank you for reporting. As far as I recall, this is the first
> field-reported bug about the right anti join!
Just for the record, this issue was reported again with BUG #18526 by
Feliphe Pozzer in
https://www.postgresql.org/message-id/flat/18526-bf89f27cb20d8a18%40postgresql.org
Thanks
Richard
^ permalink raw reply [nested|flat] 9+ messages in thread
end of thread, other threads:[~2024-07-08 02:33 UTC | newest]
Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2024-06-24 18:16 BUG #18522: Wrong results with Merge Right Anti Join, inconsistent with Merge Anti Join PG Bug reporting form <noreply@postgresql.org>
2024-06-25 02:07 ` Richard Guo <guofenglinux@gmail.com>
2024-06-25 04:24 ` Antti Lampinen <antti@lampinen.eu>
2024-06-25 11:54 ` Richard Guo <guofenglinux@gmail.com>
2024-06-25 14:45 ` Richard Guo <guofenglinux@gmail.com>
2024-06-26 07:31 ` Richard Guo <guofenglinux@gmail.com>
2024-07-02 10:22 ` Richard Guo <guofenglinux@gmail.com>
2024-07-08 02:33 ` Richard Guo <guofenglinux@gmail.com>
2024-07-01 02:55 ` Richard Guo <guofenglinux@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox