Wrong results with right-semi-joins
I ran into $subject and it can be reproduced with the query below.
create temp table tbl_rs(a int, b int);
insert into tbl_rs select i, i from generate_series(1,10)i;
analyze tbl_rs;
set enable_nestloop to off;
set enable_hashagg to off;
select * from tbl_rs t1
where (select a from tbl_rs t2
where exists (select 1 from
(select (b in (select b from tbl_rs t3)) as c
from tbl_rs t4 where t4.a = 1) s
where c in
(select t1.a = 1 from tbl_rs t5 union all select true))
order by a limit 1) >= 0;
a | b
---+---
1 | 1
(1 row)
The expected output should be 10 rows, not 1.
I've traced the root cause to ExecReScanHashJoin, where we neglect to
reset the inner-tuple match flags in the hash table for right-semi
joins when reusing the hash table. It was my oversight in commit
aa86129e1. Attached is patch to fix it.
Thanks
Richard
Attachments:
v1-0001-Fix-right-semi-joins-in-HashJoin-rescans.patchapplication/octet-stream; name=v1-0001-Fix-right-semi-joins-in-HashJoin-rescans.patchDownload
From 9e2883eae1b88f3199a27ba4e90857988ff62d2b Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 3 Dec 2024 17:27:35 +0900
Subject: [PATCH v1] Fix right-semi-joins in HashJoin rescans
When resetting a HashJoin node for rescans, if it is a single-batch
join and there are no parameter changes for the inner subnode, we can
just reuse the existing hash table without rebuilding it. However,
for join types that depend on the inner-tuple match flags in the hash
table, we need to reset these match flags to avoid incorrect results.
This applies to right, right-anti, right-semi, and full joins.
When I introduced "Right Semi Join" plan shapes in aa86129e1, I failed
to reset the match flags in the hash table for right-semi joins in
rescans. This oversight has been shown to produce incorrect results.
This patch fixes it.
---
src/backend/executor/nodeHashjoin.c | 7 ++--
src/test/regress/expected/join.out | 63 +++++++++++++++++++++++++++++
src/test/regress/sql/join.sql | 30 ++++++++++++++
3 files changed, 97 insertions(+), 3 deletions(-)
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index 6c3009fba0..ea0045bc0f 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -1511,10 +1511,11 @@ ExecReScanHashJoin(HashJoinState *node)
/*
* Okay to reuse the hash table; needn't rescan inner, either.
*
- * However, if it's a right/right-anti/full join, we'd better
- * reset the inner-tuple match flags contained in the table.
+ * However, if it's a right/right-anti/right-semi/full join, we'd
+ * better reset the inner-tuple match flags contained in the
+ * table.
*/
- if (HJ_FILL_INNER(node))
+ if (HJ_FILL_INNER(node) || node->js.jointype == JOIN_RIGHT_SEMI)
ExecHashTableResetMatchFlags(node->hj_HashTable);
/*
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index ebf2e3f851..51aeb1dae6 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3036,6 +3036,69 @@ 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 with hash-right-semi join
+--
+create temp table tbl_rs(a int, b int);
+insert into tbl_rs select i, i from generate_series(1,10)i;
+analyze tbl_rs;
+set enable_nestloop to off;
+set enable_hashagg to off;
+-- ensure we get a hash right semi join with SubPlan in hash clauses
+explain (costs off)
+select * from tbl_rs t1
+where (select a from tbl_rs t2
+ where exists (select 1 from
+ (select (b in (select b from tbl_rs t3)) as c from tbl_rs t4 where t4.a = 1) s
+ where c in (select t1.a = 1 from tbl_rs t5 union all select true))
+ order by a limit 1) >= 0;
+ QUERY PLAN
+--------------------------------------------------------------------------------------
+ Seq Scan on tbl_rs t1
+ Filter: ((SubPlan 3) >= 0)
+ SubPlan 3
+ -> Limit
+ InitPlan 2
+ -> Hash Right Semi Join
+ Hash Cond: (((t1.a = 1)) = (ANY (t4.b = (hashed SubPlan 1).col1)))
+ -> Append
+ -> Seq Scan on tbl_rs t5
+ -> Result
+ -> Hash
+ -> Seq Scan on tbl_rs t4
+ Filter: (a = 1)
+ SubPlan 1
+ -> Seq Scan on tbl_rs t3
+ -> Sort
+ Sort Key: t2.a
+ -> Result
+ One-Time Filter: (InitPlan 2).col1
+ -> Seq Scan on tbl_rs t2
+(20 rows)
+
+-- and check we get the expected results
+select * from tbl_rs t1
+where (select a from tbl_rs t2
+ where exists (select 1 from
+ (select (b in (select b from tbl_rs t3)) as c from tbl_rs t4 where t4.a = 1) s
+ where c in (select t1.a = 1 from tbl_rs t5 union all select true))
+ order by a limit 1) >= 0;
+ a | b
+----+----
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+ 10 | 10
+(10 rows)
+
+reset enable_nestloop;
+reset enable_hashagg;
+--
-- regression test for bug #13908 (hash join with skew tuples & nbatch increase)
--
set work_mem to '64kB';
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 1004fc0355..1e9dafca57 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -738,6 +738,36 @@ 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 with hash-right-semi join
+--
+create temp table tbl_rs(a int, b int);
+insert into tbl_rs select i, i from generate_series(1,10)i;
+analyze tbl_rs;
+
+set enable_nestloop to off;
+set enable_hashagg to off;
+
+-- ensure we get a hash right semi join with SubPlan in hash clauses
+explain (costs off)
+select * from tbl_rs t1
+where (select a from tbl_rs t2
+ where exists (select 1 from
+ (select (b in (select b from tbl_rs t3)) as c from tbl_rs t4 where t4.a = 1) s
+ where c in (select t1.a = 1 from tbl_rs t5 union all select true))
+ order by a limit 1) >= 0;
+
+-- and check we get the expected results
+select * from tbl_rs t1
+where (select a from tbl_rs t2
+ where exists (select 1 from
+ (select (b in (select b from tbl_rs t3)) as c from tbl_rs t4 where t4.a = 1) s
+ where c in (select t1.a = 1 from tbl_rs t5 union all select true))
+ order by a limit 1) >= 0;
+
+reset enable_nestloop;
+reset enable_hashagg;
+
--
-- regression test for bug #13908 (hash join with skew tuples & nbatch increase)
--
--
2.43.0
On Tue, Dec 3, 2024 at 5:56 PM Richard Guo <guofenglinux@gmail.com> wrote:
I've traced the root cause to ExecReScanHashJoin, where we neglect to
reset the inner-tuple match flags in the hash table for right-semi
joins when reusing the hash table. It was my oversight in commit
aa86129e1. Attached is patch to fix it.
Pushed.
Thanks
Richard
On Tue, Dec 3, 2024 at 3:56 AM Richard Guo <guofenglinux@gmail.com> wrote:
I ran into $subject and it can be reproduced with the query below.
create temp table tbl_rs(a int, b int);
insert into tbl_rs select i, i from generate_series(1,10)i;
analyze tbl_rs;set enable_nestloop to off;
set enable_hashagg to off;select * from tbl_rs t1
where (select a from tbl_rs t2
where exists (select 1 from
(select (b in (select b from tbl_rs t3)) as c
from tbl_rs t4 where t4.a = 1) s
where c in
(select t1.a = 1 from tbl_rs t5 union all select true))
order by a limit 1) >= 0;
a | b
---+---
1 | 1
(1 row)The expected output should be 10 rows, not 1.
Thanks for finding and fixing this. Just for my own benefit, could you
explain more about the minimal repro? Specifically, if you just need a
subplan in the hash side of a right semi-join, why do you also need
the outer part of the query that produces the initplan?
Seq Scan on tbl_rs t1
Filter: ((SubPlan 3) >= 0)
SubPlan 3
-> Limit
InitPlan 2
-> Hash Right Semi Join
- Melanie
On Mon, Dec 9, 2024 at 11:01 PM Melanie Plageman
<melanieplageman@gmail.com> wrote:
Thanks for finding and fixing this. Just for my own benefit, could you
explain more about the minimal repro? Specifically, if you just need a
subplan in the hash side of a right semi-join, why do you also need
the outer part of the query that produces the initplan?Seq Scan on tbl_rs t1
Filter: ((SubPlan 3) >= 0)
SubPlan 3
-> Limit
InitPlan 2
-> Hash Right Semi Join
Upon further consideration, I believe the initplan is unnecessary.
What we really want from the plan is to reuse the hash table during
hash-right-semi-join rescans. To achieve this, we just need to ensure
that it's a single-batch join and that there are no parameter changes
on the inner side.
I spent some time on this and came up with a simpler query to
reproduce the issue.
explain (costs off)
select * from tbl_rs t1 join
lateral (select * from tbl_rs t2 where t2.a in
(select t1.a+t3.a from tbl_rs t3) and t2.a < 5)
on true;
QUERY PLAN
-------------------------------------------
Nested Loop
-> Seq Scan on tbl_rs t1
-> Hash Right Semi Join
Hash Cond: ((t1.a + t3.a) = t2.a)
-> Seq Scan on tbl_rs t3
-> Hash
-> Seq Scan on tbl_rs t2
Filter: (a < 5)
(8 rows)
Without the fix, this query returns 3 rows rather than the expected 6.
Maybe I should update the test case introduced in 5668a857d to this
one.
Thanks
Richard
On Wed, Dec 11, 2024 at 11:27 AM Richard Guo <guofenglinux@gmail.com> wrote:
I spent some time on this and came up with a simpler query to
reproduce the issue.explain (costs off)
select * from tbl_rs t1 join
lateral (select * from tbl_rs t2 where t2.a in
(select t1.a+t3.a from tbl_rs t3) and t2.a < 5)
on true;
QUERY PLAN
-------------------------------------------
Nested Loop
-> Seq Scan on tbl_rs t1
-> Hash Right Semi Join
Hash Cond: ((t1.a + t3.a) = t2.a)
-> Seq Scan on tbl_rs t3
-> Hash
-> Seq Scan on tbl_rs t2
Filter: (a < 5)
(8 rows)Without the fix, this query returns 3 rows rather than the expected 6.
Maybe I should update the test case introduced in 5668a857d to this
one.
Done.
Thanks
Richard
On Wed, Dec 11, 2024 at 9:44 PM Richard Guo <guofenglinux@gmail.com> wrote:
On Wed, Dec 11, 2024 at 11:27 AM Richard Guo <guofenglinux@gmail.com> wrote:
Maybe I should update the test case introduced in 5668a857d to this
one.Done.
Great, thanks. I think the new example is more clear.
- Melanie