pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedOptimization issue of branching UNION ALL
7+ messages / 3 participants
[nested] [flat]
Commits from this thread:
2022-12-22 e42e312430 Avoid O(N^2) cost when pulling up lots of UNION ALL subqueries.
2022-12-22 97431d6739 1a3daa5bb2 5beb7881fb d572003f74 8cd700cc5a 4fceb454f2 Add some recursion and looping defenses in prepjointree.c.
* Optimization issue of branching UNION ALL
@ 2022-12-21 04:14 Andrey Lepikhov <a.lepikhov@postgrespro.ru>
0 siblings, 1 reply; 7+ messages in thread
From: Andrey Lepikhov @ 2022-12-21 04:14 UTC (permalink / raw)
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hi,
Client report on a corner case have shown up possible minor
non-optimality in procedure of transformation of simple UNION ALL
statement tree.
Complaint is about auto-generated query with 1E4 simple union all's (see
t.sh to generate a demo script). The reason: in REL_11_STABLE it is
planned and executed in a second, but REL_12_STABLE and beyond makes
matters worse: planning of such a query needs tons of gigabytes of RAM.
Superficial study revealed possibly unnecessary operations that could be
avoided:
1. Walking across a query by calling substitute_phv_relids() even if
lastPHId shows that no one phv is presented.
2. Iterative passes along the append_rel_list for replacing vars in the
translated_vars field. I can't grasp real necessity of passing all the
append_rel_list during flattening of an union all leaf subquery. No one
can reference this leaf, isn't it?
In attachment you can see some sketch that reduces a number of planner
cycles/copyings.
--
Regards
Andrey Lepikhov
Postgres Professional
Attachments:
t.sh (application/x-shellscript, 187B) download
union_all_optimization.patch (text/x-patch, 3.7K) download
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 08a73fb9d86..3739e3fe7ba 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -131,7 +131,7 @@ static bool find_dependent_phvs_in_jointree(PlannerInfo *root,
Node *node, int varno);
static void substitute_phv_relids(Node *node,
int varno, Relids subrelids);
-static void fix_append_rel_relids(List *append_rel_list, int varno,
+static void fix_append_rel_relids(PlannerInfo *root, int varno,
Relids subrelids);
static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
@@ -1156,8 +1156,9 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
Relids subrelids;
subrelids = get_relids_in_jointree((Node *) subquery->jointree, false);
- substitute_phv_relids((Node *) parse, varno, subrelids);
- fix_append_rel_relids(root->append_rel_list, varno, subrelids);
+ if (root->glob->lastPHId != 0)
+ substitute_phv_relids((Node *) parse, varno, subrelids);
+ fix_append_rel_relids(root, varno, subrelids);
}
/*
@@ -2064,17 +2065,25 @@ perform_pullup_replace_vars(PlannerInfo *root,
* use PHVs for safety. (This analysis could be made tighter but it seems
* unlikely to be worth much trouble.)
*/
- foreach(lc, root->append_rel_list)
+ if (containing_appendrel)
{
- AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
- bool save_need_phvs = rvcontext->need_phvs;
+ bool save_need_phvs = rvcontext->need_phvs;
- if (appinfo == containing_appendrel)
- rvcontext->need_phvs = false;
- appinfo->translated_vars = (List *)
- pullup_replace_vars((Node *) appinfo->translated_vars, rvcontext);
+ rvcontext->need_phvs = false;
+ containing_appendrel->translated_vars = (List *)
+ pullup_replace_vars((Node *) containing_appendrel->translated_vars,
+ rvcontext);
rvcontext->need_phvs = save_need_phvs;
}
+ else
+ {
+ foreach(lc, root->append_rel_list)
+ {
+ AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
+ appinfo->translated_vars = (List *)
+ pullup_replace_vars((Node *) appinfo->translated_vars, rvcontext);
+ }
+ }
/*
* Replace references in the joinaliasvars lists of join RTEs.
@@ -3273,7 +3282,7 @@ remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc)
subrelids = get_relids_in_jointree(newjtloc, false);
Assert(!bms_is_empty(subrelids));
substitute_phv_relids((Node *) root->parse, varno, subrelids);
- fix_append_rel_relids(root->append_rel_list, varno, subrelids);
+ fix_append_rel_relids(root, varno, subrelids);
}
/*
@@ -3492,7 +3501,7 @@ substitute_phv_relids(Node *node, int varno, Relids subrelids)
* We assume we may modify the AppendRelInfo nodes in-place.
*/
static void
-fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
+fix_append_rel_relids(PlannerInfo *root, int varno, Relids subrelids)
{
ListCell *l;
int subvarno = -1;
@@ -3503,7 +3512,7 @@ fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
* AppendRelInfo nodes refer to it. So compute it on first use. Note that
* bms_singleton_member will complain if set is not singleton.
*/
- foreach(l, append_rel_list)
+ foreach(l, root->append_rel_list)
{
AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
@@ -3518,8 +3527,9 @@ fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
}
/* Also fix up any PHVs in its translated vars */
- substitute_phv_relids((Node *) appinfo->translated_vars,
- varno, subrelids);
+ if (root->glob->lastPHId != 0)
+ substitute_phv_relids((Node *) appinfo->translated_vars,
+ varno, subrelids);
}
}
* Re: Optimization issue of branching UNION ALL
@ 2022-12-22 01:50 Tom Lane <tgl@sss.pgh.pa.us>
parent: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
0 siblings, 2 replies; 7+ messages in thread
From: Tom Lane @ 2022-12-22 01:50 UTC (permalink / raw)
To: Andrey Lepikhov <a.lepikhov@postgrespro.ru>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> Complaint is about auto-generated query with 1E4 simple union all's (see
> t.sh to generate a demo script). The reason: in REL_11_STABLE it is
> planned and executed in a second, but REL_12_STABLE and beyond makes
> matters worse: planning of such a query needs tons of gigabytes of RAM.
v11 (and prior versions) sucks just as badly. In this example it
accidentally escapes trouble because it doesn't know how to pull up
a subquery with empty FROM. But if you make the query look like
SELECT 1,1 FROM dual
UNION ALL
SELECT 2,2 FROM dual
UNION ALL
SELECT 3,3 FROM dual
...
then v11 chokes as well. (Seems like we've overlooked the need
for check_stack_depth() and CHECK_FOR_INTERRUPTS() here ...)
> Superficial study revealed possibly unnecessary operations that could be
> avoided:
> 1. Walking across a query by calling substitute_phv_relids() even if
> lastPHId shows that no one phv is presented.
Yeah, we could do that, and it'd help some.
> 2. Iterative passes along the append_rel_list for replacing vars in the
> translated_vars field. I can't grasp real necessity of passing all the
> append_rel_list during flattening of an union all leaf subquery. No one
> can reference this leaf, isn't it?
After thinking about that for awhile, I believe we can go further:
the containing_appendrel is actually the *only* part of the upper
query that needs to be adjusted. So we could do something like
the attached.
This passes check-world, but I don't have quite enough confidence
in it to just commit it.
regards, tom lane
Attachments:
union_all_optimization-v2.patch (text/x-diff, 5.8K) download
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index c2239d18b4..cb2c1ef5e0 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -27,6 +27,7 @@
#include "catalog/pg_type.h"
#include "funcapi.h"
+#include "miscadmin.h"
#include "nodes/makefuncs.h"
#include "nodes/multibitmapset.h"
#include "nodes/nodeFuncs.h"
@@ -127,7 +128,7 @@ static bool find_dependent_phvs_in_jointree(PlannerInfo *root,
Node *node, int varno);
static void substitute_phv_relids(Node *node,
int varno, Relids subrelids);
-static void fix_append_rel_relids(List *append_rel_list, int varno,
+static void fix_append_rel_relids(PlannerInfo *root, int varno,
Relids subrelids);
static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
@@ -805,6 +806,11 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
JoinExpr *lowest_nulling_outer_join,
AppendRelInfo *containing_appendrel)
{
+ /* Since this function recurses, it could be driven to stack overflow. */
+ check_stack_depth();
+ /* Also, since it's a bit expensive, let's check for query cancel. */
+ CHECK_FOR_INTERRUPTS();
+
Assert(jtnode != NULL);
if (IsA(jtnode, RangeTblRef))
{
@@ -1229,8 +1235,9 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
Relids subrelids;
subrelids = get_relids_in_jointree((Node *) subquery->jointree, false);
- substitute_phv_relids((Node *) parse, varno, subrelids);
- fix_append_rel_relids(root->append_rel_list, varno, subrelids);
+ if (root->glob->lastPHId != 0)
+ substitute_phv_relids((Node *) parse, varno, subrelids);
+ fix_append_rel_relids(root, varno, subrelids);
}
/*
@@ -1409,7 +1416,10 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
/*
* Recursively apply pull_up_subqueries to the new child RTE. (We
- * must build the AppendRelInfo first, because this will modify it.)
+ * must build the AppendRelInfo first, because this will modify it;
+ * indeed, that's the only part of the upper query where Vars
+ * referencing childRTindex can exist at this point.)
+ *
* Note that we can pass NULL for containing-join info even if we're
* actually under an outer join, because the child's expressions
* aren't going to propagate up to the join. Also, we ignore the
@@ -2107,6 +2117,25 @@ perform_pullup_replace_vars(PlannerInfo *root,
Query *parse = root->parse;
ListCell *lc;
+ /*
+ * If we are considering an appendrel child subquery (that is, a UNION ALL
+ * member query that we're pulling up), then the only part of the upper
+ * query that could reference the child yet is the translated_vars list of
+ * the containing appendrel. Furthermore, we do not need to insert PHVs
+ * in the appendrel --- there isn't any outer join between.
+ */
+ if (containing_appendrel)
+ {
+ bool save_need_phvs = rvcontext->need_phvs;
+
+ rvcontext->need_phvs = false;
+ containing_appendrel->translated_vars = (List *)
+ pullup_replace_vars((Node *) containing_appendrel->translated_vars,
+ rvcontext);
+ rvcontext->need_phvs = save_need_phvs;
+ return;
+ }
+
/*
* Replace all of the top query's references to the subquery's outputs
* with copies of the adjusted subtlist items, being careful not to
@@ -2160,22 +2189,14 @@ perform_pullup_replace_vars(PlannerInfo *root,
parse->havingQual = pullup_replace_vars(parse->havingQual, rvcontext);
/*
- * Replace references in the translated_vars lists of appendrels. When
- * pulling up an appendrel member, we do not need PHVs in the list of the
- * parent appendrel --- there isn't any outer join between. Elsewhere,
- * use PHVs for safety. (This analysis could be made tighter but it seems
- * unlikely to be worth much trouble.)
+ * Replace references in the translated_vars lists of appendrels.
*/
foreach(lc, root->append_rel_list)
{
AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
- bool save_need_phvs = rvcontext->need_phvs;
- if (appinfo == containing_appendrel)
- rvcontext->need_phvs = false;
appinfo->translated_vars = (List *)
pullup_replace_vars((Node *) appinfo->translated_vars, rvcontext);
- rvcontext->need_phvs = save_need_phvs;
}
/*
@@ -3345,8 +3366,9 @@ remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc)
subrelids = get_relids_in_jointree(newjtloc, false);
Assert(!bms_is_empty(subrelids));
- substitute_phv_relids((Node *) root->parse, varno, subrelids);
- fix_append_rel_relids(root->append_rel_list, varno, subrelids);
+ if (root->glob->lastPHId != 0)
+ substitute_phv_relids((Node *) root->parse, varno, subrelids);
+ fix_append_rel_relids(root, varno, subrelids);
}
/*
@@ -3565,7 +3587,7 @@ substitute_phv_relids(Node *node, int varno, Relids subrelids)
* We assume we may modify the AppendRelInfo nodes in-place.
*/
static void
-fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
+fix_append_rel_relids(PlannerInfo *root, int varno, Relids subrelids)
{
ListCell *l;
int subvarno = -1;
@@ -3576,7 +3598,7 @@ fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
* AppendRelInfo nodes refer to it. So compute it on first use. Note that
* bms_singleton_member will complain if set is not singleton.
*/
- foreach(l, append_rel_list)
+ foreach(l, root->append_rel_list)
{
AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
@@ -3591,8 +3613,9 @@ fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
}
/* Also fix up any PHVs in its translated vars */
- substitute_phv_relids((Node *) appinfo->translated_vars,
- varno, subrelids);
+ if (root->glob->lastPHId != 0)
+ substitute_phv_relids((Node *) appinfo->translated_vars,
+ varno, subrelids);
}
}
=
* Re: Optimization issue of branching UNION ALL
@ 2022-12-22 02:37 Richard Guo <guofenglinux@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 7+ messages in thread
From: Richard Guo @ 2022-12-22 02:37 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andrey Lepikhov <a.lepikhov@postgrespro.ru>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Thu, Dec 22, 2022 at 9:50 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> > Superficial study revealed possibly unnecessary operations that could be
> > avoided:
> > 1. Walking across a query by calling substitute_phv_relids() even if
> > lastPHId shows that no one phv is presented.
>
> Yeah, we could do that, and it'd help some.
I noticed we also check 'parse->hasSubLinks' when we fix PHVs and
AppendRelInfos in pull_up_simple_subquery. I'm not sure why we have
this check. It seems not necessary.
In remove_result_refs, I don't think we need to check 'lastPHId' again
before calling substitute_phv_relids, since it has been checked a few
lines earlier.
Thanks
Richard
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Optimization issue of branching UNION ALL
@ 2022-12-22 03:48 Tom Lane <tgl@sss.pgh.pa.us>
parent: Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 7+ messages in thread
From: Tom Lane @ 2022-12-22 03:48 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: Andrey Lepikhov <a.lepikhov@postgrespro.ru>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Richard Guo <guofenglinux@gmail.com> writes:
> I noticed we also check 'parse->hasSubLinks' when we fix PHVs and
> AppendRelInfos in pull_up_simple_subquery. I'm not sure why we have
> this check. It seems not necessary.
Yeah, I was wondering about that too ... maybe it was important
in some previous state of the code? I didn't do any archeology
though.
> In remove_result_refs, I don't think we need to check 'lastPHId' again
> before calling substitute_phv_relids, since it has been checked a few
> lines earlier.
Oh, duh ...
regards, tom lane
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Optimization issue of branching UNION ALL
@ 2022-12-22 04:14 Tom Lane <tgl@sss.pgh.pa.us>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 7+ messages in thread
From: Tom Lane @ 2022-12-22 04:14 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: Andrey Lepikhov <a.lepikhov@postgrespro.ru>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
I wrote:
> Richard Guo <guofenglinux@gmail.com> writes:
>> I noticed we also check 'parse->hasSubLinks' when we fix PHVs and
>> AppendRelInfos in pull_up_simple_subquery. I'm not sure why we have
>> this check. It seems not necessary.
> Yeah, I was wondering about that too ... maybe it was important
> in some previous state of the code? I didn't do any archeology
> though.
After a bit of "git blame"-ing, it appears that that hasSubLinks
check was introduced in e006a24ad, which added a FlattenedSubLink
node type and needed to fix them up here:
+ * We also have to fix the relid sets of any FlattenedSubLink nodes in
+ * the parent query. (This could perhaps be done by ResolveNew, but it
Then when I got rid of FlattenedSubLink in e549722a8, I neglected
to remove that check. So I think maybe we don't need it, but I've
not tested.
regards, tom lane
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Optimization issue of branching UNION ALL
@ 2022-12-22 11:59 Andrey Lepikhov <a.lepikhov@postgrespro.ru>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 7+ messages in thread
From: Andrey Lepikhov @ 2022-12-22 11:59 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On 22/12/2022 06:50, Tom Lane wrote:
>> 2. Iterative passes along the append_rel_list for replacing vars in the
>> translated_vars field. I can't grasp real necessity of passing all the
>> append_rel_list during flattening of an union all leaf subquery. No one
>> can reference this leaf, isn't it?
>
> After thinking about that for awhile, I believe we can go further:
> the containing_appendrel is actually the *only* part of the upper
> query that needs to be adjusted. So we could do something like
> the attached.
>
> This passes check-world, but I don't have quite enough confidence
> in it to just commit it.
Thanks, I have written the letter because of some doubts too. But only
one weak point I could imagine - if someday sql standard will be changed.
Your code looks better, than previous attempt.
--
regards,
Andrey Lepikhov
Postgres Professional
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: Optimization issue of branching UNION ALL
@ 2022-12-22 16:05 Tom Lane <tgl@sss.pgh.pa.us>
parent: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
0 siblings, 0 replies; 7+ messages in thread
From: Tom Lane @ 2022-12-22 16:05 UTC (permalink / raw)
To: Andrey Lepikhov <a.lepikhov@postgrespro.ru>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Andrey Lepikhov <a.lepikhov@postgrespro.ru> writes:
> Thanks, I have written the letter because of some doubts too. But only
> one weak point I could imagine - if someday sql standard will be changed.
Yeah, if they ever decide that LATERAL should be allowed to reference a
previous sub-query of UNION ALL, that'd probably break this. But it'd
break a lot of other code too, so I'm not going to worry about it.
I pushed the main fix to HEAD only, and the recursion checks to
all branches.
regards, tom lane
^ permalink raw reply [nested|flat] 7+ messages in thread
end of thread, other threads:[~2022-12-22 16:05 UTC | newest]
Thread overview: 7+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2022-12-21 04:14 Optimization issue of branching UNION ALL Andrey Lepikhov <a.lepikhov@postgrespro.ru>
2022-12-22 01:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-12-22 02:37 ` Richard Guo <guofenglinux@gmail.com>
2022-12-22 03:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-12-22 04:14 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-12-22 11:59 ` Andrey Lepikhov <a.lepikhov@postgrespro.ru>
2022-12-22 16:05 ` Tom Lane <tgl@sss.pgh.pa.us>
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