Hi,
Since commit 8c49a484e8e, which gives every subquery a unique name before
it is planned, planning time is O(N^3) in the number of subplans that
share a base name.
choose_plan_name() looks for a free numeric suffix by trying 1, 2, 3, ...
and, for each candidate, scanning the list of all names assigned so far.
The k-th subplan with a given base name costs O(k^2) comparisons, so a
statement with N of them makes (N^3 - N)/6 + N(N - 1)/2 strcmp() calls
while planning -- 93% of planning time here at N=250 and more than 98%
from N=1000 on.
Statements that reach this have many set-operation arms (setop_N), scalar
sublinks (expr_N), or same-named subqueries. For a UNION of N SELECTs,
planning only (EXPLAIN SUMMARY, nothing executed) on this machine: at
N=1000, v18 takes about 2 ms and master about 280 ms; at N=2000, about
5 ms vs 2.2 s; at N=4000, about 15 ms vs 17 s. The local exponent from
N=2000 to 4000 is about 3.0 on master and on 19beta4, against about 1.7
on v18. The change is at 8c49a484e8e itself: its parent plans like v18,
the commit like master. The attached script reproduces it (it shows the
expr_N names and the planning-time growth for both sublinks and
set-operation arms).
The attached patch keeps the assigned names in a hash table instead of a
list and remembers the next suffix to try for each base name. Names are
never released, so every smaller suffix is already taken and the chosen
names are identical to today's -- a byte-for-byte EXPLAIN diff over 19
cases and 756 names is empty -- while each call becomes constant
amortized time. The 4000-arm UNION drops to about 17 ms (v18: about
15 ms), and make check-world passes. The hash table alone is not
enough: without the per-name suffix counter the search is still
quadratic, about 390 ms for the same statement.
One cost worth noting: the hash table is created on the first subplan
name, which adds roughly 0.1-0.2 us to a statement that has exactly one
subplan (queries with none never call the function). If that is a
concern, the creation could be deferred to the second name; I kept it
simple here.
Regards,
Manu
From 768b1a180843b23602081272714f54853440ded6 Mon Sep 17 00:00:00 2001
From: Manuel Reyes Bravo <[email protected]>
Date: Sat, 10 Oct 2026 00:08:25 -0300
Subject: [PATCH v1] Avoid O(N^3) planning time in choose_plan_name()
Since commit 8c49a484e8e, every subquery is given a unique name before it
is planned. choose_plan_name() looked for a free numeric suffix by trying
1, 2, 3, ... and scanning the list of all names assigned so far for each
candidate. The k-th subplan with a given base name therefore cost O(k^2)
string comparisons, and planning a statement with N such subplans took
(N^3 - N)/6 + N(N - 1)/2 strcmp() calls in total. This affects
statements with many set-operation arms (setop_N), scalar sublinks
(expr_N) or same-named subqueries: a 4000-arm UNION takes about 17 s to
plan on master, against about 16 ms on v18.
Keep the assigned names in a hash table instead of a list, and remember
for each base name the next suffix to try. Names are never released, so
every smaller suffix is already taken and the chosen names are the same
as before, while each call now takes constant amortized time.
Discussion:
---
src/backend/optimizer/plan/planner.c | 120 ++++++++++++++++++---------
src/include/nodes/pathnodes.h | 4 +-
src/tools/pgindent/typedefs.list | 1 +
3 files changed, 82 insertions(+), 43 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index edaa42d713a..0973e359c95 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -60,6 +60,7 @@
#include "rewrite/rewriteManip.h"
#include "utils/acl.h"
#include "utils/backend_status.h"
+#include "utils/hsearch.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
@@ -9249,66 +9250,103 @@ create_partial_unique_paths(PlannerInfo *root, RelOptInfo *input_rel,
}
}
+/*
+ * Hash table key size for subplan names. Base names passed to
+ * choose_plan_name() are identifiers (subquery aliases, CTE names) or short
+ * fixed strings such as "setop" or "exists_to_any", so they are shorter than
+ * NAMEDATALEN; a numeric suffix adds at most "_" plus 10 digits.
+ */
+#define SUBPLAN_NAME_KEYSIZE (NAMEDATALEN + 11)
+
+/*
+ * An entry of glob->subplanNames. Every name handed out by
+ * choose_plan_name() has an entry with "used" set. A base name that has been
+ * given numeric suffixes also has an entry, whose next_suffix records where
+ * the next search for a free suffix should start; it has "used" set only if
+ * the base name itself was also handed out.
+ */
+typedef struct SubplanNameEntry
+{
+ char name[SUBPLAN_NAME_KEYSIZE]; /* hash key; must be first */
+ bool used; /* has this name been handed out? */
+ unsigned next_suffix; /* as a base name: first suffix to try */
+} SubplanNameEntry;
+
+/*
+ * Find or create the entry for a subplan name.
+ */
+static SubplanNameEntry *
+subplan_name_entry(PlannerGlobal *glob, const char *name)
+{
+ SubplanNameEntry *entry;
+ bool found;
+
+ /*
+ * Create the hash table on first use, so that queries without subplans
+ * don't pay for it. Allocate it alongside glob, since it has to live as
+ * long as glob does, whatever context the first caller happens to be in.
+ */
+ if (glob->subplanNames == NULL)
+ {
+ HASHCTL hash_ctl;
+
+ hash_ctl.keysize = SUBPLAN_NAME_KEYSIZE;
+ hash_ctl.entrysize = sizeof(SubplanNameEntry);
+ hash_ctl.hcxt = GetMemoryChunkContext(glob);
+ glob->subplanNames = hash_create("subplan names", 64, &hash_ctl,
+ HASH_ELEM | HASH_STRINGS | HASH_CONTEXT);
+ }
+
+ entry = (SubplanNameEntry *) hash_search(glob->subplanNames, name,
+ HASH_ENTER, &found);
+ if (!found)
+ {
+ entry->used = false;
+ entry->next_suffix = 1;
+ }
+ return entry;
+}
+
/*
* 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 already in use, it is used
+ * as-is; otherwise, it is suffixed with the smallest positive integer that
+ * yields an unused name. glob->subplanNames tracks the names already used.
*/
char *
choose_plan_name(PlannerGlobal *glob, const char *name, bool always_number)
{
+ SubplanNameEntry *base;
unsigned n;
- /*
- * 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)
- {
- bool found = false;
+ Assert(strlen(name) < NAMEDATALEN);
- 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);
+ base = subplan_name_entry(glob, name);
- glob->subplanNames = lappend(glob->subplanNames, chosen_name);
- return chosen_name;
- }
+ if (!always_number && !base->used)
+ {
+ base->used = true;
+ /* pstrdup here is just to avoid cast-away-const */
+ return pstrdup(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.
+ * Names are never released, so every suffix below next_suffix is known to
+ * be taken. Starting the search there rather than at 1 yields the same
+ * name, but keeps the cost per call constant instead of growing with the
+ * number of subplans that share this base name. (Entries do not move
+ * when the table grows, so "base" stays valid while we add entries.)
*/
- for (n = 1; true; ++n)
+ for (n = base->next_suffix; true; ++n)
{
char *proposed_name = psprintf("%s_%u", name, n);
- bool found = false;
-
- foreach_ptr(char, subplan_name, glob->subplanNames)
- {
- if (strcmp(subplan_name, proposed_name) == 0)
- {
- found = true;
- break;
- }
- }
+ SubplanNameEntry *entry = subplan_name_entry(glob, proposed_name);
- if (!found)
+ if (!entry->used)
{
- glob->subplanNames = lappend(glob->subplanNames, proposed_name);
+ entry->used = true;
+ base->next_suffix = n + 1;
return proposed_name;
}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 1c6d1fe3d04..599b646caed 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -183,8 +183,8 @@ typedef struct PlannerGlobal
/* PlannerInfos for SubPlan nodes */
List *subroots pg_node_attr(read_write_ignore);
- /* names already used for subplans (list of C strings) */
- List *subplanNames pg_node_attr(read_write_ignore);
+ /* names already used for subplans; see choose_plan_name() */
+ struct HTAB *subplanNames pg_node_attr(read_write_ignore);
/* indices of subplans that require REWIND */
Bitmapset *rewindPlanIDs;
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 3bed561f7f2..ef3c309d77e 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3019,6 +3019,7 @@ SubXactCallback
SubXactCallbackItem
SubXactEvent
SubXactInfo
+SubplanNameEntry
SubqueryScan
SubqueryScanPath
SubqueryScanState
-- Planning time grows as N^3 with the number of subqueries that share a base
name
-- (PostgreSQL 19 / master, since commit 8c49a484e8e). Self-contained; run with
-- psql -X -f repro.sql. Nothing is executed: EXPLAIN without ANALYZE only
plans.
-- 1. The names. Each uncorrelated scalar sublink becomes an InitPlan named by
-- choose_plan_name(glob, "expr", true): expr_1, expr_2, expr_3.
EXPLAIN (COSTS OFF)
SELECT ARRAY[(SELECT 1 WHERE random() >= 0),
(SELECT 2 WHERE random() >= 0),
(SELECT 3 WHERE random() >= 0)];
-- Planning time of a statement, from EXPLAIN (SUMMARY), without printing the
plan.
CREATE FUNCTION pg_temp.planning_ms(stmt text) RETURNS numeric
LANGUAGE plpgsql AS $$
DECLARE plan json;
BEGIN
EXECUTE 'EXPLAIN (SUMMARY, FORMAT JSON) ' || stmt INTO plan;
RETURN round((plan -> 0 ->> 'Planning Time')::numeric, 1);
END $$;
-- 2. The cost: N sublinks (names expr_1 .. expr_N) and an N-arm UNION (every
arm
-- planned as its own subquery, names setop_1 .. setop_N). Doubling N
multiplies
-- planning time by about 8.
SELECT n,
pg_temp.planning_ms((SELECT 'SELECT ARRAY[' ||
string_agg(format('(SELECT %s WHERE random() >= 0)', i), ', ') || ']'
FROM generate_series(1, n) AS i)) AS sublinks_ms,
pg_temp.planning_ms((SELECT string_agg(format('SELECT %s', i), ' UNION ')
FROM generate_series(1, n) AS i)) AS union_ms
FROM (VALUES (250), (500), (1000), (2000)) AS v(n);
