Hi Tom, On Sat, Oct 31, 2026 at 2:35 PM Tom Lane <[email protected]> wrote: > I still don't like this patch too much: it is complicated and not > clearly correct. For example, consider the case where we've > generated "expr_1" through "expr_3", and then we encounter a > user-written name "expr_5". It looks to me like we will consider > that *not* to match the SubplanNameSuffix for "expr", so we will > enter "expr_5" as a simple base name in the other list. I think > that the right things happen afterwards because subplan_name_in_use > always searches both lists, but this situation is hard to reason > about and utterly undocumented in the comments. The business about > strtoul overflow somehow didn't make it into the comments either.
v4, attached, is simpler. It stores all names, as master does, keeps a suffix counter per base name, and checks a generated name only against names used as given; not storing the generated names is what made v3 complicated. The comment says why this is unique, your "expr_5" case included, and why a counter cannot wrap. > I still wonder if we couldn't simplify this a great deal by > abandoning the constraint that the generated names should match > what the existing code does, along the lines Heikki mentioned. > I wouldn't want to change that behavior post-19.0, but it's not > quite too late to consider it now. I tried that too, with one counter for all names. Robert: then a sublink that a custom plan folds away renumbers every later subplan, not only those of its kind, so one prepared statement with SEQ_SCAN(t2@expr_2) seq-scans different subplans in its custom and generic plans, and pg_plan_advice's own "alternatives" test no longer matches. v4 keeps today's names: no existing expected output changes, and a 4000-arm UNION plans in 22 ms (v18 18.6 ms, master 16.9 s) with the same planner memory as master. If you would still rather have the single counter, that version is ready too. Regards, Manu
From c8fcd54a844bd14ec91bcbc64dab77a102595490 Mon Sep 17 00:00:00 2001 From: Manu <[email protected]> Date: Sat, 31 Oct 2026 21:02:52 -0300 Subject: [PATCH v4] Avoid O(N^3) planning time in choose_plan_name() Since commit 8c49a484e8e, choose_plan_name() found the smallest free numeric suffix by trying 1, 2, 3, ... and scanning every name assigned so far for each candidate, so planning a statement with N subplans of one kind took O(N^3) time: about 17 s for a 4000-arm UNION, against 19 ms on v18. Keep a suffix counter for each base name instead, and check generated names only against the names used as given. The names chosen are the same as before. --- src/backend/optimizer/plan/planner.c | 118 ++++++++++++++---------- src/include/nodes/pathnodes.h | 6 ++ src/test/regress/expected/subselect.out | 67 ++++++++++++++ src/test/regress/sql/subselect.sql | 24 +++++ src/tools/pgindent/typedefs.list | 1 + 5 files changed, 167 insertions(+), 49 deletions(-) diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index edaa42d..15598b0 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -9249,69 +9249,89 @@ create_partial_unique_paths(PlannerInfo *root, RelOptInfo *input_rel, } } +/* + * The last numeric suffix given to subplan names built on one base name; see + * choose_plan_name(). + */ +typedef struct SubplanNameSuffix +{ + const char *base; /* the base name */ + uint32 last_suffix; /* the last suffix given to it */ +} SubplanNameSuffix; + +/* + * Is "name" in "names", a list of C strings? + */ +static bool +plan_name_is_in(List *names, const char *name) +{ + foreach_ptr(char, n, names) + { + if (strcmp(n, name) == 0) + return true; + } + return false; +} + /* * Choose a unique name for some subroot. * - * Modifies glob->subplanNames to track names already used. + * If always_number is false and the name is not taken yet, it is used as + * given. Otherwise we append "_N", where N is the next value of a counter + * kept for each base name. So no two generated names are equal: N's digits + * contain no "_", so a generated name determines its base name and N (they + * are what comes before and after its last "_"), and no base name gets the + * same N twice. A generated name can still equal a name used as given, such + * as a CTE called "expr_5", and either of the two can come first. So a name + * to be used as given is checked against all the names taken so far, and a + * generated one against the names used as given, moving on to the next N if + * it is taken. + * + * Names are never released, so every N up to the counter is taken, and this + * gives the smallest N that is free. A name used as given makes us skip at + * most one N, so a counter never exceeds the number of names assigned and + * cannot wrap around. The names depend only on the order of the calls, so + * planning the same query again gives the same names. */ char * choose_plan_name(PlannerGlobal *glob, const char *name, bool always_number) { - unsigned n; + SubplanNameSuffix *suffix = NULL; + char *chosen_name; - /* - * If a numeric suffix is not required, then search the list of - * previously-assigned names for a match. If none is found, then we can - * use the provided name without modification. - */ - if (!always_number) + if (!always_number && !plan_name_is_in(glob->subplanNames, name)) { - bool found = false; - - foreach_ptr(char, subplan_name, glob->subplanNames) - { - if (strcmp(subplan_name, name) == 0) - { - found = true; - break; - } - } - - if (!found) - { - /* pstrdup here is just to avoid cast-away-const */ - char *chosen_name = pstrdup(name); - - glob->subplanNames = lappend(glob->subplanNames, chosen_name); - return chosen_name; - } + /* pstrdup here is just to avoid cast-away-const */ + chosen_name = pstrdup(name); + glob->givenSubplanNames = lappend(glob->givenSubplanNames, + chosen_name); + glob->subplanNames = lappend(glob->subplanNames, chosen_name); + return chosen_name; } - /* - * If a numeric suffix is required or if the un-suffixed name is already - * in use, then loop until we find a positive integer that produces a - * novel name. - */ - for (n = 1; true; ++n) + foreach_ptr(SubplanNameSuffix, s, glob->subplanNameSuffixes) { - char *proposed_name = psprintf("%s_%u", name, n); - bool found = false; - - foreach_ptr(char, subplan_name, glob->subplanNames) + if (strcmp(s->base, name) == 0) { - if (strcmp(subplan_name, proposed_name) == 0) - { - found = true; - break; - } - } - - if (!found) - { - glob->subplanNames = lappend(glob->subplanNames, proposed_name); - return proposed_name; + suffix = s; + break; } + } + if (suffix == NULL) + { + suffix = palloc0_object(SubplanNameSuffix); + suffix->base = pstrdup(name); + glob->subplanNameSuffixes = lappend(glob->subplanNameSuffixes, suffix); + } - pfree(proposed_name); + for (;;) + { + chosen_name = psprintf("%s_%u", name, ++suffix->last_suffix); + if (!plan_name_is_in(glob->givenSubplanNames, chosen_name)) + break; + pfree(chosen_name); } + + glob->subplanNames = lappend(glob->subplanNames, chosen_name); + return chosen_name; } diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index ff46a9f..71ec3f5 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -186,6 +186,12 @@ typedef struct PlannerGlobal /* names already used for subplans (list of C strings) */ List *subplanNames pg_node_attr(read_write_ignore); + /* the subset of subplanNames used without a numeric suffix */ + List *givenSubplanNames pg_node_attr(read_write_ignore); + + /* last numeric suffix for each base name; see choose_plan_name() */ + List *subplanNameSuffixes pg_node_attr(read_write_ignore); + /* indices of subplans that require REWIND */ Bitmapset *rewindPlanIDs; diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index 6379bd6..3fe06e5 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -4075,3 +4075,70 @@ WHERE COALESCE(t1.id, -1) NOT IN (0 rows) ROLLBACK; +-- +-- Numbered subplan names must not collide with names used as given, such as +-- CTE names, whichever comes first +-- +EXPLAIN (COSTS OFF) +WITH expr_1 AS MATERIALIZED (SELECT 1 AS x) +SELECT (SELECT x FROM expr_1), (SELECT 2 WHERE random() >= 0); + QUERY PLAN +---------------------------------------------------------------- + Result + CTE expr_1 + -> Result + InitPlan expr_2 + -> CTE Scan on expr_1 + InitPlan expr_3 + -> Result + One-Time Filter: (random() >= '0'::double precision) +(8 rows) + +-- expr_5 is used as given after expr_1 .. expr_4, so the next one is expr_6 +EXPLAIN (COSTS OFF) +SELECT (SELECT 1 WHERE random() >= 0), (SELECT 2 WHERE random() >= 0), + (SELECT 3 WHERE random() >= 0), + (WITH expr_5 AS MATERIALIZED (SELECT 4 AS x) SELECT x FROM expr_5), + (SELECT 5 WHERE random() >= 0); + QUERY PLAN +---------------------------------------------------------------- + Result + InitPlan expr_1 + -> Result + One-Time Filter: (random() >= '0'::double precision) + InitPlan expr_2 + -> Result + One-Time Filter: (random() >= '0'::double precision) + InitPlan expr_3 + -> Result + One-Time Filter: (random() >= '0'::double precision) + InitPlan expr_4 + -> CTE Scan on expr_5 + CTE expr_5 + -> Result + InitPlan expr_6 + -> Result + One-Time Filter: (random() >= '0'::double precision) +(17 rows) + +-- a name of NAMEDATALEN - 1 bytes, used twice +EXPLAIN (COSTS OFF) +WITH nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn + AS MATERIALIZED (SELECT 1 AS x) +SELECT (SELECT x FROM nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn), + (WITH nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn + AS MATERIALIZED (SELECT 2 AS x) + SELECT x FROM nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn); + QUERY PLAN +----------------------------------------------------------------------------------------------------------------------------------------------------- + Result + CTE nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn + -> Result + InitPlan expr_1 + -> CTE Scan on nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn + InitPlan expr_2 + -> CTE Scan on nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn_1 + CTE nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn_1 + -> Result +(9 rows) + diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index c6cd275..55b2d24 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -1790,3 +1790,27 @@ WHERE COALESCE(t1.id, -1) NOT IN (SELECT t1.val FROM not_null_tab t2 WHERE t2.val IS NOT NULL); ROLLBACK; + +-- +-- Numbered subplan names must not collide with names used as given, such as +-- CTE names, whichever comes first +-- +EXPLAIN (COSTS OFF) +WITH expr_1 AS MATERIALIZED (SELECT 1 AS x) +SELECT (SELECT x FROM expr_1), (SELECT 2 WHERE random() >= 0); + +-- expr_5 is used as given after expr_1 .. expr_4, so the next one is expr_6 +EXPLAIN (COSTS OFF) +SELECT (SELECT 1 WHERE random() >= 0), (SELECT 2 WHERE random() >= 0), + (SELECT 3 WHERE random() >= 0), + (WITH expr_5 AS MATERIALIZED (SELECT 4 AS x) SELECT x FROM expr_5), + (SELECT 5 WHERE random() >= 0); + +-- a name of NAMEDATALEN - 1 bytes, used twice +EXPLAIN (COSTS OFF) +WITH nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn + AS MATERIALIZED (SELECT 1 AS x) +SELECT (SELECT x FROM nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn), + (WITH nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn + AS MATERIALIZED (SELECT 2 AS x) + SELECT x FROM nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn); diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index b964e5e..e10966d 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -3021,6 +3021,7 @@ SubXactCallback SubXactCallbackItem SubXactEvent SubXactInfo +SubplanNameSuffix SubqueryScan SubqueryScanPath SubqueryScanState -- 2.56.0
