agora inbox for pgsql-bugs@postgresql.org
help / color / mirror / Atom feedDO NOT pull up a sublink when it has no join condition with the upper relation
3+ messages / 2 participants
[nested] [flat]
* DO NOT pull up a sublink when it has no join condition with the upper relation
@ 2026-07-30 16:15 ld_zju <ld_zju@126.com>
2026-07-31 02:52 ` Re: DO NOT pull up a sublink when it has no join condition with the upper relation Tender Wang <tndrwang@gmail.com>
0 siblings, 1 reply; 3+ messages in thread
From: ld_zju @ 2026-07-30 16:15 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org
Hi,
I've encountered a scenario where pulling up a sublink not only brings no benefit but actually degrades the final plan significantly.
Here is the test case:
create table t1(a int,b int,c int,d int);
create table t2(a int,b int,c int,d int);
create table t3(a int,b int,c int,d int);
insert into t1 select i,i,i,i from generate_series(1,1000) i;
insert into t2 select i,i,i,i from generate_series(1,1000) i;
insert into t3 select i,i,i,i from generate_series(1,10) i;
explain select * from t1 where exists(select 1 from t2 where t2.a in(select t3.a from t3 where t3.b=t1.b));
QUERY PLAN
-------------------------------------------------------------------
Nested Loop Semi Join (cost=0.00..28418232.67 rows=925 width=16)
Join Filter: (ANY (t2.a = (SubPlan any_1).col1))
-> Seq Scan on t1 (cost=0.00..28.50 rows=1850 width=16)
-> Materialize (cost=0.00..37.75 rows=1850 width=4)
-> Seq Scan on t2 (cost=0.00..28.50 rows=1850 width=4)
SubPlan any_1
-> Seq Scan on t3 (cost=0.00..33.12 rows=9 width=4)
Filter: (b = t1.b)
(8 rows)
The EXISTS sublink is pulled up and joined with t1 via a Nested Loop Semi Join. However, since there is no join condition between t1 and the sublink (the condition t3.b = t1.b is inside the subplan), this results in a Cartesian product between t1 and t2, followed by filtering through the subplan. With t1 and t2 both having 1000 rows, this produces a large intermediate result set (1,000,000 rows) when the actual result set is much smaller.
Would it be possible that the sublink is pulled up only when it has any join conditions with the upper relation? If no such conditions exist, a Cartesian product is likely and pulling up should be avoided.
Any thoughts or suggestions would be appreciated!
Best regards,
Deng, LU
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: DO NOT pull up a sublink when it has no join condition with the upper relation
2026-07-30 16:15 DO NOT pull up a sublink when it has no join condition with the upper relation ld_zju <ld_zju@126.com>
@ 2026-07-31 02:52 ` Tender Wang <tndrwang@gmail.com>
2026-07-31 14:54 ` Re:Re: DO NOT pull up a sublink when it has no join condition with the upper relation ld_zju <ld_zju@126.com>
0 siblings, 1 reply; 3+ messages in thread
From: Tender Wang @ 2026-07-31 02:52 UTC (permalink / raw)
To: ld_zju <ld_zju@126.com>; +Cc: pgsql-bugs@lists.postgresql.org, Tom Lane <tgl@sss.pgh.pa.us>
ld_zju <ld_zju@126.com> 于2026年7月31日周五 00:16写道：
>
> Hi,
>
> I've encountered a scenario where pulling up a sublink not only brings no benefit but actually degrades the final plan significantly.
>
> Here is the test case:
>
> create table t1(a int,b int,c int,d int);
> create table t2(a int,b int,c int,d int);
> create table t3(a int,b int,c int,d int);
> insert into t1 select i,i,i,i from generate_series(1,1000) i;
> insert into t2 select i,i,i,i from generate_series(1,1000) i;
> insert into t3 select i,i,i,i from generate_series(1,10) i;
>
> explain select * from t1 where exists(select 1 from t2 where t2.a in(select t3.a from t3 where t3.b=t1.b));
> QUERY PLAN
> -------------------------------------------------------------------
> Nested Loop Semi Join (cost=0.00..28418232.67 rows=925 width=16)
> Join Filter: (ANY (t2.a = (SubPlan any_1).col1))
> -> Seq Scan on t1 (cost=0.00..28.50 rows=1850 width=16)
> -> Materialize (cost=0.00..37.75 rows=1850 width=4)
> -> Seq Scan on t2 (cost=0.00..28.50 rows=1850 width=4)
> SubPlan any_1
> -> Seq Scan on t3 (cost=0.00..33.12 rows=9 width=4)
> Filter: (b = t1.b)
> (8 rows)
>
> The EXISTS sublink is pulled up and joined with t1 via a Nested Loop Semi Join. However, since there is no join condition between t1 and the sublink (the condition t3.b = t1.b is inside the subplan), this results in a Cartesian product between t1 and t2, followed by filtering through the subplan. With t1 and t2 both having 1000 rows, this produces a large intermediate result set (1,000,000 rows) when the actual result set is much smaller.
>
> Would it be possible that the sublink is pulled up only when it has any join conditions with the upper relation? If no such conditions exist, a Cartesian product is likely and pulling up should be avoided.
>
> Any thoughts or suggestions would be appreciated!
You can add "offset 0" into the subquery; then the plan should be what you want.
postgres=# explain select * from t1 where exists(select 1 from t2
where t2.a in(select t1.b from t3 where t3.b=t1.b) offset 0);
QUERY PLAN
------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..19651.00 rows=500 width=16)
Filter: EXISTS(SubPlan exists_1)
SubPlan exists_1
-> Nested Loop Semi Join (cost=0.00..19.64 rows=1 width=4)
-> Seq Scan on t2 (cost=0.00..18.50 rows=1 width=0)
Filter: (a = t1.b)
-> Seq Scan on t3 (cost=0.00..1.12 rows=1 width=0)
Filter: (b = t1.b)
(8 rows)
And the Execution Time: 178.877 ms; without "offset 0", it is 4048.970
ms on my machine.
In convert_EXISTS_sublink_to_join(), we have:
/*
* On the other hand, the WHERE clause must contain some Vars of the
* parent query, else it's not gonna be a join.
*/
if (!contain_vars_of_level(whereClause, 1))
return NULL;
When we recurse into the third sublink in
contain_vars_of_level_walker(), the levelsup was +1(i.e. 2)
t1.b in "t3.b = t1.b" is Var [varno=1 varattno=2 vartype=23
varlevelsup=2 varreturningtype=VAR_RETURNING_DEFAULT varnosyn=1
varattnosyn=2]
You can see that varlevelsup is 2, so
contain_vars_of_level(whereClause, 1) returns true. Then the sublink
is pulled up.
I made some attempts.
#1
We can't simply remove the"(*sublevels_up)++; " in
contain_vars_of_level_walker(); because some other places also call
this function.
If you do this, the regression will crash.
#2
I rewrote a separate version based on the current implementation
specifically for SubLink pull-up. My goal was simply to see whether it
would cause any regression test failures.
The attached is my test. It's only for testing.
To my surprise, all the regression tests passed.
I'm not sure it is a bug. The code was committed 17 years ago by Tom.
And I'm not sure you're the first to report this issue.
I feel that in most cases, the second query will refer to the top
query's column, and the third query will refer to the second query's
column.
--
Thanks,
Tender Wang
Attachments:
[application/octet-stream] 0001-Only-test-for-sublink-pullup.patch (3.8K, ../../CAHewXN=80HJz8fBiQpf9vFh1NK1vdEHMdSEb6BYV9toZikooPA@mail.gmail.com/2-0001-Only-test-for-sublink-pullup.patch)
download | inline diff:
From 38a7ace1082e8a668007b800f6df379c38a37747 Mon Sep 17 00:00:00 2001
From: Ubuntu <ubuntu@localhost.localdomain>
Date: Fri, 31 Jul 2026 10:26:54 +0800
Subject: [PATCH] Only test for sublink pullup
---
src/backend/optimizer/plan/subselect.c | 2 +-
src/backend/optimizer/util/var.c | 49 ++++++++++++++++++++++++++
src/include/optimizer/optimizer.h | 1 +
3 files changed, 51 insertions(+), 1 deletion(-)
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 6aa8971c95d..03a37421bce 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1650,7 +1650,7 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
* On the other hand, the WHERE clause must contain some Vars of the
* parent query, else it's not gonna be a join.
*/
- if (!contain_vars_of_level(whereClause, 1))
+ if (!contain_vars_of_level_parent(whereClause, 1))
return NULL;
/*
diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c
index 907a255c36f..7a20c6ca021 100644
--- a/src/backend/optimizer/util/var.c
+++ b/src/backend/optimizer/util/var.c
@@ -76,6 +76,7 @@ static bool pull_varattnos_walker(Node *node, pull_varattnos_context *context);
static bool pull_vars_walker(Node *node, pull_vars_context *context);
static bool contain_var_clause_walker(Node *node, void *context);
static bool contain_vars_of_level_walker(Node *node, int *sublevels_up);
+static bool contain_vars_of_level_walker2(Node *node, int *sublevels_up);
static bool contain_vars_returning_old_or_new_walker(Node *node, void *context);
static bool locate_var_of_level_walker(Node *node,
locate_var_of_level_context *context);
@@ -492,7 +493,55 @@ contain_vars_of_level_walker(Node *node, int *sublevels_up)
sublevels_up);
}
+bool
+contain_vars_of_level_parent(Node *node, int levelsup)
+{
+ int sublevels_up = levelsup;
+ return query_or_expression_tree_walker(node,
+ contain_vars_of_level_walker2,
+ &sublevels_up,
+ 0);
+}
+
+static bool
+contain_vars_of_level_walker2(Node *node, int *sublevels_up)
+{
+ if (node == NULL)
+ return false;
+ if (IsA(node, Var))
+ {
+ if (((Var *) node)->varlevelsup == *sublevels_up)
+ return true; /* abort tree traversal and return true */
+ return false;
+ }
+ if (IsA(node, CurrentOfExpr))
+ {
+ if (*sublevels_up == 0)
+ return true;
+ return false;
+ }
+ if (IsA(node, PlaceHolderVar))
+ {
+ if (((PlaceHolderVar *) node)->phlevelsup == *sublevels_up)
+ return true; /* abort the tree traversal and return true */
+ /* else fall through to check the contained expr */
+ }
+ if (IsA(node, Query))
+ {
+ /* Recurse into subselects */
+ bool result;
+
+ result = query_tree_walker((Query *) node,
+ contain_vars_of_level_walker2,
+ sublevels_up,
+ 0);
+ return result;
+ }
+ return expression_tree_walker(node,
+ contain_vars_of_level_walker2,
+ sublevels_up);
+}
/*
* contain_vars_returning_old_or_new
* Recursively scan a clause to discover whether it contains any Var nodes
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index cb6241e2bdd..cd17ffc92bf 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -209,6 +209,7 @@ extern void pull_varattnos(Node *node, Index varno, Bitmapset **varattnos);
extern List *pull_vars_of_level(Node *node, int levelsup);
extern bool contain_var_clause(Node *node);
extern bool contain_vars_of_level(Node *node, int levelsup);
+extern bool contain_vars_of_level_parent(Node *node, int levelsup);
extern bool contain_vars_returning_old_or_new(Node *node);
extern int locate_var_of_level(Node *node, int levelsup);
extern List *pull_var_clause(Node *node, int flags);
--
2.43.0
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re:Re: DO NOT pull up a sublink when it has no join condition with the upper relation
2026-07-30 16:15 DO NOT pull up a sublink when it has no join condition with the upper relation ld_zju <ld_zju@126.com>
2026-07-31 02:52 ` Re: DO NOT pull up a sublink when it has no join condition with the upper relation Tender Wang <tndrwang@gmail.com>
@ 2026-07-31 14:54 ` ld_zju <ld_zju@126.com>
0 siblings, 0 replies; 3+ messages in thread
From: ld_zju @ 2026-07-31 14:54 UTC (permalink / raw)
To: Tender Wang <tndrwang@gmail.com>; +Cc: pgsql-bugs@lists.postgresql.org, "Tom Lane" <tgl@sss.pgh.pa.us>
Thank you for your quick response.
The reason why I thought it was a bug is only because oracle optimizer can generate a plan seems to be more reasonable. Its execution plan goes like "select * from t1 where exists(select 1 from t2, t3 where t3.b=t1.b and t2.a=t3.a);"
I have tested the suggested approach with "offset 0" in our test environment. It does resolve the immediate issue we encountered, and the performance impact is acceptable.
At 2026-07-31 10:52:55, "Tender Wang" <tndrwang@gmail.com> wrote:
>ld_zju <ld_zju@126.com> 于2026年7月31日周五 00:16写道：
>>
>> Hi,
>>
>> I've encountered a scenario where pulling up a sublink not only brings no benefit but actually degrades the final plan significantly.
>>
>> Here is the test case:
>>
>> create table t1(a int,b int,c int,d int);
>> create table t2(a int,b int,c int,d int);
>> create table t3(a int,b int,c int,d int);
>> insert into t1 select i,i,i,i from generate_series(1,1000) i;
>> insert into t2 select i,i,i,i from generate_series(1,1000) i;
>> insert into t3 select i,i,i,i from generate_series(1,10) i;
>>
>> explain select * from t1 where exists(select 1 from t2 where t2.a in(select t3.a from t3 where t3.b=t1.b));
>> QUERY PLAN
>> -------------------------------------------------------------------
>> Nested Loop Semi Join (cost=0.00..28418232.67 rows=925 width=16)
>> Join Filter: (ANY (t2.a = (SubPlan any_1).col1))
>> -> Seq Scan on t1 (cost=0.00..28.50 rows=1850 width=16)
>> -> Materialize (cost=0.00..37.75 rows=1850 width=4)
>> -> Seq Scan on t2 (cost=0.00..28.50 rows=1850 width=4)
>> SubPlan any_1
>> -> Seq Scan on t3 (cost=0.00..33.12 rows=9 width=4)
>> Filter: (b = t1.b)
>> (8 rows)
>>
>> The EXISTS sublink is pulled up and joined with t1 via a Nested Loop Semi Join. However, since there is no join condition between t1 and the sublink (the condition t3.b = t1.b is inside the subplan), this results in a Cartesian product between t1 and t2, followed by filtering through the subplan. With t1 and t2 both having 1000 rows, this produces a large intermediate result set (1,000,000 rows) when the actual result set is much smaller.
>>
>> Would it be possible that the sublink is pulled up only when it has any join conditions with the upper relation? If no such conditions exist, a Cartesian product is likely and pulling up should be avoided.
>>
>> Any thoughts or suggestions would be appreciated!
>
>You can add "offset 0" into the subquery; then the plan should be what you want.
>postgres=# explain select * from t1 where exists(select 1 from t2
>where t2.a in(select t1.b from t3 where t3.b=t1.b) offset 0);
> QUERY PLAN
>------------------------------------------------------------------
> Seq Scan on t1 (cost=0.00..19651.00 rows=500 width=16)
> Filter: EXISTS(SubPlan exists_1)
> SubPlan exists_1
> -> Nested Loop Semi Join (cost=0.00..19.64 rows=1 width=4)
> -> Seq Scan on t2 (cost=0.00..18.50 rows=1 width=0)
> Filter: (a = t1.b)
> -> Seq Scan on t3 (cost=0.00..1.12 rows=1 width=0)
> Filter: (b = t1.b)
>(8 rows)
>
>And the Execution Time: 178.877 ms; without "offset 0", it is 4048.970
>ms on my machine.
>
>In convert_EXISTS_sublink_to_join(), we have:
> /*
> * On the other hand, the WHERE clause must contain some Vars of the
> * parent query, else it's not gonna be a join.
> */
> if (!contain_vars_of_level(whereClause, 1))
> return NULL;
>
>When we recurse into the third sublink in
>contain_vars_of_level_walker(), the levelsup was +1(i.e. 2)
>t1.b in "t3.b = t1.b" is Var [varno=1 varattno=2 vartype=23
>varlevelsup=2 varreturningtype=VAR_RETURNING_DEFAULT varnosyn=1
>varattnosyn=2]
>You can see that varlevelsup is 2, so
>contain_vars_of_level(whereClause, 1) returns true. Then the sublink
>is pulled up.
>
>I made some attempts.
>
>#1
>We can't simply remove the"(*sublevels_up)++; " in
>contain_vars_of_level_walker(); because some other places also call
>this function.
>If you do this, the regression will crash.
>#2
>I rewrote a separate version based on the current implementation
>specifically for SubLink pull-up. My goal was simply to see whether it
>would cause any regression test failures.
>The attached is my test. It's only for testing.
>To my surprise, all the regression tests passed.
>
>I'm not sure it is a bug. The code was committed 17 years ago by Tom.
>And I'm not sure you're the first to report this issue.
>I feel that in most cases, the second query will refer to the top
>query's column, and the third query will refer to the second query's
>column.
>
>--
>Thanks,
>Tender Wang
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2026-07-31 14:54 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-07-30 16:15 DO NOT pull up a sublink when it has no join condition with the upper relation ld_zju <ld_zju@126.com>
2026-07-31 02:52 ` Tender Wang <tndrwang@gmail.com>
2026-07-31 14:54 ` ld_zju <ld_zju@126.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox