Hi Robert,
On Tue, Nov 3, 2026 at 11:17 AM Robert Haas <[email protected]>
wrote:
> - Use a hash table, but only bother building it when there are
> unusually many subplans (exact threshold TBD). We can build hash
> tables where the key is a cstring, rather than a fixed-length string
> limited by NAMEDATALEN, just by defining things correctly.
[...]
> - If we need to do better than O(N^2), then give the hash table
> entries two payload values: a Boolean indicating whether the exact
> value has been used as a name, and an unsigned value indicating the
> lowest value of n for which choose_plan_name's numeric suffix look
> could possibly succeed.
The attached v6 does that. Once a statement has 32 subplan names,
they also go into a simplehash keyed by the C string, as with
ec_derives_hash in equivclass.c; below that it searches the list as
before. Each entry has your two payloads, and the suffix search
starts from the stored value.
With the 4000-arm UNION, planning takes 16.6 s on master, 22 ms with
v5 or v6, and 19 ms on 18.6. With 4000 CTEs with different names it
takes 153 ms on master and v5, 126 ms with v6 and 128 ms on 18.6.
Below 32 names v6 only adds a pointer test or two per call. Small
statements plan 2-4% slower with default builds, but the same
(0.0%, 95% CI -0.9..+1.2) when both builds use -falign-functions=64,
so I take that to be code layout.
The middle option alone, the hash table only replacing the list
searches, is 43 lines shorter, but the UNION then takes 441 ms; I can
post that one instead if you prefer it. The hash table starts to win
at about 8 generated names or 40 different ones; 32 is what
ec_derives_hash uses.
check-world passes on master and REL_19_STABLE, and make check, four
contrib suites and 32 statements built to collide give master's
names, also with the threshold at 0. The details are in
measurements.txt.
Regards,
Manu
From b6c81dbdb80bb3522a7c30d4e83c56c3606dde8d Mon Sep 17 00:00:00 2001
From: Manuel Reyes Bravo <[email protected]>
Date: Wed, 4 Nov 2026 18:21:54 -0300
Subject: [PATCH v6] 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. Different names given by the user, such as CTE names,
still took O(N^2) time.
Once a statement has 32 subplan names, also keep them in a hash table
keyed by the name, and look names up there instead of in the list.
Each entry records whether the name itself is in use and, for a base
name, the suffix to start the search for a free "name_N" from: names
are never released, so every smaller N is known to be taken. Below 32
names, the code runs as before. The names chosen do not change.
Suggested-by: Robert Haas <[email protected]>
---
src/backend/optimizer/plan/planner.c | 149 +++++++++++++++++++-----
src/include/nodes/pathnodes.h | 3 +
src/test/regress/expected/subselect.out | 101 ++++++++++++++++
src/test/regress/sql/subselect.sql | 55 +++++++++
src/tools/pgindent/typedefs.list | 2 +
5 files changed, 281 insertions(+), 29 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index edaa42d..9148ee3 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -26,6 +26,7 @@
#include "catalog/pg_inherits.h"
#include "catalog/pg_proc.h"
#include "catalog/pg_type.h"
+#include "common/hashfn.h"
#include "executor/executor.h"
#include "foreign/fdwapi.h"
#include "jit/jit.h"
@@ -9249,42 +9250,128 @@ create_partial_unique_paths(PlannerInfo *root, RelOptInfo *input_rel,
}
}
+/* Hash table entry in glob->subplanNameHash. */
+typedef struct
+{
+ uint32 status;
+ const char *name;
+ bool used; /* is the name itself in use? */
+ unsigned next_suffix; /* name_N is taken for N < next_suffix */
+} SubplanNameEntry;
+
+/* Threshold for switching from list to hash table */
+#define SUBPLAN_NAME_HASH_THRESHOLD 32
+
+#define SH_PREFIX subplan_name
+#define SH_ELEMENT_TYPE SubplanNameEntry
+#define SH_KEY_TYPE const char *
+#define SH_KEY name
+#define SH_HASH_KEY(tb, key) \
+ hash_bytes((const unsigned char *) (key), strlen(key))
+#define SH_EQUAL(tb, a, b) (strcmp(a, b) == 0)
+#define SH_SCOPE static inline
+#define SH_DECLARE
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
+/*
+ * Enter "name", which is now in use, into the hash table.
+ */
+static void
+enter_subplan_name(subplan_name_hash *tb, char *name)
+{
+ SubplanNameEntry *entry;
+ bool found;
+
+ entry = subplan_name_insert(tb, name, &found);
+ if (!found)
+ entry->next_suffix = 1;
+ entry->used = true;
+}
+
+/*
+ * Is "name" in glob->subplanNames?
+ */
+static bool
+subplan_name_in_use(PlannerGlobal *glob, const char *name)
+{
+ if (glob->subplanNameHash)
+ {
+ SubplanNameEntry *entry;
+
+ entry = subplan_name_lookup(glob->subplanNameHash, name);
+ return entry != NULL && entry->used;
+ }
+
+ foreach_ptr(char, subplan_name, glob->subplanNames)
+ {
+ if (strcmp(subplan_name, name) == 0)
+ return true;
+ }
+ return false;
+}
+
+/*
+ * Add "name" to glob->subplanNames, and to glob->subplanNameHash if built.
+ */
+static void
+add_subplan_name(PlannerGlobal *glob, char *name)
+{
+ glob->subplanNames = lappend(glob->subplanNames, name);
+ if (glob->subplanNameHash)
+ enter_subplan_name(glob->subplanNameHash, name);
+}
+
/*
* Choose a unique name for some subroot.
*
- * Modifies glob->subplanNames to track names already used.
+ * Modifies glob->subplanNames to track names already used. Once there are
+ * many of them, they are also kept in glob->subplanNameHash, so that we
+ * don't have to search the list for each name we try.
+ *
+ * The hash table also remembers, for each base name, the smallest N
+ * that might give a free "name_N": since names are never released,
+ * every smaller N is known to be taken, and we start the search there.
*/
char *
choose_plan_name(PlannerGlobal *glob, const char *name, bool always_number)
{
unsigned n;
+ /* Switch to using hash lookup when the list grows "too long". */
+ if (!glob->subplanNameHash &&
+ list_length(glob->subplanNames) >= SUBPLAN_NAME_HASH_THRESHOLD)
+ {
+ glob->subplanNameHash =
+ subplan_name_create(CurrentMemoryContext,
+ list_length(glob->subplanNames), NULL);
+ foreach_ptr(char, subplan_name, glob->subplanNames)
+ enter_subplan_name(glob->subplanNameHash, subplan_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 && !subplan_name_in_use(glob, name))
{
- bool found = false;
+ /* pstrdup here is just to avoid cast-away-const */
+ char *chosen_name = pstrdup(name);
- foreach_ptr(char, subplan_name, glob->subplanNames)
- {
- if (strcmp(subplan_name, name) == 0)
- {
- found = true;
- break;
- }
- }
+ add_subplan_name(glob, chosen_name);
+ return chosen_name;
+ }
- if (!found)
- {
- /* pstrdup here is just to avoid cast-away-const */
- char *chosen_name = pstrdup(name);
+ /* With the hash table, start where the last search for this name ended. */
+ n = 1;
+ if (glob->subplanNameHash)
+ {
+ SubplanNameEntry *entry;
- glob->subplanNames = lappend(glob->subplanNames, chosen_name);
- return chosen_name;
- }
+ entry = subplan_name_lookup(glob->subplanNameHash, name);
+ if (entry)
+ n = entry->next_suffix;
}
/*
@@ -9292,23 +9379,27 @@ choose_plan_name(PlannerGlobal *glob, const char *name, bool always_number)
* in use, then loop until we find a positive integer that produces a
* novel name.
*/
- for (n = 1; true; ++n)
+ for (; true; ++n)
{
char *proposed_name = psprintf("%s_%u", name, n);
- bool found = false;
- foreach_ptr(char, subplan_name, glob->subplanNames)
+ if (!subplan_name_in_use(glob, proposed_name))
{
- if (strcmp(subplan_name, proposed_name) == 0)
+ add_subplan_name(glob, proposed_name);
+ if (glob->subplanNameHash)
{
- found = true;
- break;
+ SubplanNameEntry *entry;
+ bool found;
+
+ entry = subplan_name_insert(glob->subplanNameHash,
+ name, &found);
+ if (!found)
+ {
+ entry->name = pstrdup(name);
+ entry->used = false;
+ }
+ entry->next_suffix = n + 1;
}
- }
-
- if (!found)
- {
- glob->subplanNames = lappend(glob->subplanNames, proposed_name);
return proposed_name;
}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index ff46a9f..9922d9b 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -186,6 +186,9 @@ typedef struct PlannerGlobal
/* names already used for subplans (list of C strings) */
List *subplanNames pg_node_attr(read_write_ignore);
+ /* optional hash table for fast lookup; contains same names as list */
+ struct subplan_name_hash *subplanNameHash 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 c78267d..a37b76e 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -4126,3 +4126,104 @@ WHERE t NOT IN (SELECT id FROM not_null_tab);
(4 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_1 is generated first, so the CTE expr_1 that comes after is numbered
+EXPLAIN (COSTS OFF)
+SELECT (SELECT 1 WHERE random() >= 0),
+ (WITH expr_1 AS MATERIALIZED (SELECT 2 AS x) SELECT x FROM expr_1);
+ QUERY PLAN
+----------------------------------------------------------------
+ Result
+ InitPlan expr_1
+ -> Result
+ One-Time Filter: (random() >= '0'::double precision)
+ InitPlan expr_2
+ -> CTE Scan on expr_1
+ CTE expr_1_1
+ -> Result
+(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)
+
+-- Past 32 names, choose_plan_name() looks them up in a hash table. The CTEs
+-- c1 .. c40 keep their names, generated names still do not collide with
+-- expr_2 and expr_1 given by the user, and a CTE called expr after expr_N have
+-- been generated keeps its name (only the names other than cN are shown)
+CREATE FUNCTION subplan_names(query text) RETURNS text
+LANGUAGE plpgsql AS
+$$
+DECLARE
+ ln text;
+ names text[] := '{}';
+BEGIN
+ FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || query LOOP
+ IF ln ~ '^\s*(CTE|InitPlan|SubPlan) ' THEN
+ ln := regexp_replace(ln, '^\s*(CTE|InitPlan|SubPlan) ', '');
+ IF ln !~ '^c[0-9]+$' THEN
+ names := names || ln;
+ END IF;
+ END IF;
+ END LOOP;
+ RETURN array_to_string(names, ' ');
+END;
+$$;
+SELECT subplan_names(format(
+ 'WITH %s, expr_2 AS MATERIALIZED (SELECT 0 AS x) '
+ 'SELECT (SELECT x FROM expr_2), (SELECT 1 WHERE random() >= 0), '
+ '(WITH expr_1 AS MATERIALIZED (SELECT 2 AS x) SELECT x FROM expr_1), '
+ '(WITH expr AS MATERIALIZED (SELECT 3 AS x) SELECT x FROM expr) '
+ 'FROM (%s) s',
+ (SELECT string_agg(format('c%s AS MATERIALIZED (SELECT %s AS x)', i, i),
+ ', ')
+ FROM generate_series(1, 40) i),
+ (SELECT string_agg(format('SELECT x FROM c%s', i), ' UNION ALL ')
+ FROM generate_series(1, 40) i)));
+ subplan_names
+--------------------------------------------------
+ expr_2 expr_1 expr_3 expr_4 expr_1_1 expr_5 expr
+(1 row)
+
+DROP FUNCTION subplan_names(text);
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index c046b0e..538b1aa 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -1815,3 +1815,58 @@ SELECT * FROM not_null_text_tab
WHERE t NOT IN (SELECT id FROM not_null_tab);
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_1 is generated first, so the CTE expr_1 that comes after is numbered
+EXPLAIN (COSTS OFF)
+SELECT (SELECT 1 WHERE random() >= 0),
+ (WITH expr_1 AS MATERIALIZED (SELECT 2 AS x) SELECT x FROM expr_1);
+
+-- 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);
+
+-- Past 32 names, choose_plan_name() looks them up in a hash table. The CTEs
+-- c1 .. c40 keep their names, generated names still do not collide with
+-- expr_2 and expr_1 given by the user, and a CTE called expr after expr_N have
+-- been generated keeps its name (only the names other than cN are shown)
+CREATE FUNCTION subplan_names(query text) RETURNS text
+LANGUAGE plpgsql AS
+$$
+DECLARE
+ ln text;
+ names text[] := '{}';
+BEGIN
+ FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || query LOOP
+ IF ln ~ '^\s*(CTE|InitPlan|SubPlan) ' THEN
+ ln := regexp_replace(ln, '^\s*(CTE|InitPlan|SubPlan) ', '');
+ IF ln !~ '^c[0-9]+$' THEN
+ names := names || ln;
+ END IF;
+ END IF;
+ END LOOP;
+ RETURN array_to_string(names, ' ');
+END;
+$$;
+SELECT subplan_names(format(
+ 'WITH %s, expr_2 AS MATERIALIZED (SELECT 0 AS x) '
+ 'SELECT (SELECT x FROM expr_2), (SELECT 1 WHERE random() >= 0), '
+ '(WITH expr_1 AS MATERIALIZED (SELECT 2 AS x) SELECT x FROM expr_1), '
+ '(WITH expr AS MATERIALIZED (SELECT 3 AS x) SELECT x FROM expr) '
+ 'FROM (%s) s',
+ (SELECT string_agg(format('c%s AS MATERIALIZED (SELECT %s AS x)', i, i),
+ ', ')
+ FROM generate_series(1, 40) i),
+ (SELECT string_agg(format('SELECT x FROM c%s', i), ' UNION ALL ')
+ FROM generate_series(1, 40) i)));
+DROP FUNCTION subplan_names(text);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 553162c..6055f03 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3021,6 +3021,7 @@ SubXactCallback
SubXactCallbackItem
SubXactEvent
SubXactInfo
+SubplanNameEntry
SubqueryScan
SubqueryScanPath
SubqueryScanState
@@ -4331,6 +4332,7 @@ storeInfo
storeRes_func
stream_stop_callback
string
+subplan_name_hash
substitute_actual_parameters_context
substitute_actual_parameters_in_from_context
substitute_grouped_columns_context
--
2.56.0
choose_plan_name() v6 -- measurements
Builds: master at 76e9e44b03a (2026-11-04), v5 and v6 applied to it, and
18.6; all -O2, without assertions. "v6 A" is the smaller variant (the hash
table only replaces the list searches); "v6" is the patch attached.
Planning time is EXPLAIN (SUMMARY)'s, in ms, median of 5 samples, the
builds taking turns. At N = 4000 no two samples of a cell differ by
more than 9% of its median; in the cells of a few ms (N = 1000, 2000)
single samples stray by up to 27%, with no second mode.
join_collapse_limit = from_collapse_limit = 1, so join order search is
not what is measured.
1. Generated names, all from one base name: the 4000-arm UNION
SELECT 1 UNION SELECT 2 ... UNION SELECT N (setop_1 .. setop_N)
N 18.6 master v5 v6 A v6
100 0.3 0.7 0.3 0.6 0.3
500 1.3 37.1 2.0 7.8 1.7
1000 3.2 269.4 3.3 27.8 3.5
2000 7.4 2084.3 8.4 111.7 8.6
4000 18.8 16615.6 21.8 440.5 22.1
2. Different names given by the user: N CTEs
WITH c1 AS MATERIALIZED (SELECT 1 AS a), ..., cN AS ...
SELECT count(*) FROM (SELECT a FROM c1 UNION ALL ... SELECT a FROM cN) s
N 18.6 master v5 v6 A v6
100 0.6 0.6 0.6 0.6 0.6
500 4.1 4.6 4.4 4.2 4.1
1000 10.9 12.0 11.9 11.1 10.8
2000 34.0 38.1 38.5 34.8 34.4
4000 127.8 152.7 151.1 128.8 126.3
And N subqueries in FROM, s1 .. sN:
SELECT 1 FROM (SELECT 1 AS a OFFSET 0) s1 CROSS JOIN ... sN
(N = 4000 measured one build at a time: with five servers up, one of
them went away at that size)
N 18.6 master v5 v6 A v6
100 0.5 0.5 0.5 0.5 0.5
500 3.9 3.8 3.7 4.0 3.6
1000 9.4 10.1 10.1 9.4 10.2
2000 29.4 32.8 33.8 29.2 29.8
4000 97.1 116.3 113.9 96.4 95.7
3. The threshold: choose_plan_name() alone, from a test-only C function
that calls it N times on a fresh PlannerGlobal; total ns for the N
calls, median of 1001, with the list only and with the hash table
from the first name. The hash table is faster from N = 8 with
generated names and from N = 40 with different names, where the list
is cheapest; at 32 that case is 0.2 us slower in total.
N generated (expr_N) different (cN)
list hash list hash
4 250 240 50 140
8 1001 500 110 300
16 4348 1032 330 631
24 11312 1593 601 851
32 22804 2304 1001 1192
40 39306 2935 1512 1392
48 62111 3677 2184 1543
64 130494 5290 3997 2424
128 778317 10851 14608 6121
256 5213552 24187 54125 15580
4. Small statements, below 32 names: 8 statements (sublinks, CTEs, IN,
EXISTS, UNION, min/max, a subquery in FROM, one with 20 sublinks), 20
times each per round; the sum of their planning times per round, with
master, a second cluster of the same master build ("master again") and
v6 taking turns; 4 runs of 40 rounds, pooled; median and 95% CI of the
difference. Two clusters of one build differ by about 2%, as much as
v6 and master do. "aligned": master and v6 both built with
-falign-functions=64, which makes the difference go away, so it comes
from where the code lands, not from what runs: below 32 names v6 runs
master's loops plus one pointer test per call. The last line adds a
statement with 40 subplans, which uses the hash table.
v6 vs master: +3.6% [95% CI +2.0..+5.2], n=160+160
v6 vs master again: +1.6% [95% CI +0.1..+2.9], n=160+160
master again vs master: +2.0% [95% CI +0.7..+3.4], n=160+160
aligned: v6 vs master: +0.0% [95% CI -0.9..+1.2], n=160+160
aligned: v6 vs master again: -1.2% [95% CI -2.3..-0.1], n=160+160
aligned: master again vs master: +1.2% [95% CI +0.1..+2.6], n=160+160
with a 40-subplan statement: -2.3% [95% CI -3.2..-1.0], n=40+40
Each statement alone, median of 600, in us (EXPLAIN's resolution);
"again" is the second cluster of the master build, in the same run;
on the right, the builds with -falign-functions=64:
default build aligned
master again v6 master again v6
0 23 23 24 24 25 24 SELECT a, (SELECT max(b) FROM t2
1 10 10 10 10 11 10 SELECT * FROM t WHERE a IN (SELEC
2 41 41 42 42 42 42 SELECT * FROM t WHERE EXISTS (SEL
3 39 39 40 41 41 40 WITH x AS MATERIALIZED (SELECT a
4 19 19 20 20 21 20 SELECT a FROM t WHERE b = 1 UNION
5 12 12 13 13 13 13 SELECT min(a), max(a) FROM t
6 26 26 27 27 28 27 SELECT t.a, s.c FROM t, (SELECT a
7 106 105 107 109 110 107 SELECT (SELECT count(*) FROM t2 W
5. Names: v6 chooses the same names as master. make check and the
checks of pg_overexplain, pg_plan_advice, pg_stash_advice and
postgres_fdw pass, on master and REL_19_STABLE, and the names printed
for 32 more statements (19 with every kind of subplan, 13 built so
that generated names meet names given by the user; EXPLAIN with
pg_overexplain's RANGE_TABLE and pg_plan_advice's PLAN_ADVICE) are
byte-identical to master's. The same holds with the threshold set to
0, so that every name goes through the hash table.
