O(N^3) planning time in choose_plan_name() since 8c49a484e8e
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
Hello Manu,
On 10/10/2026 09:02, Manu wrote:
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
Thanks for the patch and detailed analysis.
I noticed this as well while working on or-expansion patch [1]/messages/by-id/d606f08e-3a56-409f-8591-ccdbb3379b0e@data-bene.io.
I tested v1 on master, and the results are good:
Tested across various N for both UNION arms and scalar sublinks:
I only started seeing improvements starting from N = 20.
N = 1,000 UNION: dropped from 390 ms to 3.7 ms (~100x faster).
N = 2,000 UNION: dropped from 3.14 s to 11.9 ms (~260x faster).
I did some quick perf profiling on master, i saw that ~98% of total
query planning CPU cycles were on choose_plan_name() calling strcmp().
With v1 applied, choose_plan_name() drops to 0.1%.
The only small issue found in v1 is the assertion:
Assert(strlen(name) < NAMEDATALEN);
While identifiers entered via raw SQL are truncated to NAMEDATALEN - 1
(63 bytes), anything else created programmatically by extensions, ...
(e.g., via makeAlias()) do not enforce truncation.
And in non-assert builds, dynahash silently truncates the key at 74
bytes, i think that risks collisions ?
Instead of asserting, you should probably defensively clip name to
NAMEDATALEN - 1 bytes if it exceeds that length (similar to
set_rtable_names() and other places)
Apart from this, looks good!
Regards,
Ayoub
[1]: /messages/by-id/d606f08e-3a56-409f-8591-ccdbb3379b0e@data-bene.io
/messages/by-id/d606f08e-3a56-409f-8591-ccdbb3379b0e@data-bene.io
Hi,
On 2026-10-10 04:02:22 -0300, Manu wrote:
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.
Are there halfway realistic cases where this is a problem?
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.
Hm. What if we instead just switched to something like using
list_length(glob->subplanNames) as a suffix once the list gets long enough?
Creating hash tables ain't free memory-usage-wise.
Greetings,
Andres Freund
Andres Freund <andres@anarazel.de> writes:
Hm. What if we instead just switched to something like using
list_length(glob->subplanNames) as a suffix once the list gets long enough?
Or just do it that way always. I think the requirement here is only
uniqueness and reproducibility.
regards, tom lane
Hi Ayoub, Andres, Tom,
Thanks, all three of you. v2 is attached: no hash table, no extra
memory, and the names stay as they are. A 4000-arm UNION plans in
21 ms (v18 20 ms, master 17.6 s), and every form stays within
0.92-1.18x of v18 up to 8000 arms.
On Wed, Oct 28, 2026 at 5:29 PM Ayoub Kazar <ayoub.kazar@data-bene.io>
wrote:
And in non-assert builds, dynahash silently truncates the key at 74
bytes, i think that risks collisions ?
Worse than collisions, thanks for testing v1: with an 80-byte alias set
by C code, two subqueries were enough for a non-assert build to loop
forever in choose_plan_name(), ignoring cancel and terminate. v2 has
no keys to cut and plans such aliases fine.
On Wed, Oct 28, 2026 at 12:42 PM Andres Freund <andres@anarazel.de>
wrote:
Are there halfway realistic cases where this is a problem?
Only generated SQL. A UNION ALL of N aggregates, N correlated scalar
subqueries or N ORed IN (SELECT ...) plan 2x slower than v18 from
N = 100-200, and take over 100 ms from N = 500-1000.
On Wed, Oct 28, 2026 at 1:31 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Or just do it that way always. I think the requirement here is only
uniqueness and reproducibility.
I tried that first. It works, but it renumbers names wherever base
names mix, and users write those names into pg_plan_advice strings: its
own alternatives test stops matching, since exists_to_any_1 becomes
exists_to_any_2, and pg_plan_advice is in 19.
So v2 keeps a counter per base name. Names are never released, so
every smaller suffix is taken and the counter gives today's name. A
suffixed name determines its base and suffix, split at the last
underscore, so suffixed names can't collide with each other; only names
used as given (CTE names, subquery aliases) can, and those are checked.
No existing expected output changes, and a test-only build running the
old algorithm alongside found no mismatch. check-world passes with
cassert; REL_19_STABLE takes the patch as is.
Regards,
Manu
On 28/10/2026 21:27, Manu wrote:
So v2 keeps a counter per base name. Names are never released, so
every smaller suffix is taken and the counter gives today's name. A
suffixed name determines its base and suffix, split at the last
underscore, so suffixed names can't collide with each other; only names
used as given (CTE names, subquery aliases) can, and those are checked.
No existing expected output changes, and a test-only build running the
old algorithm alongside found no mismatch. check-world passes with
cassert; REL_19_STABLE takes the patch as is.
One small suggestion: the suffix parsing in subplan_name_in_use() scans
the digits
multiple times across strspn, strlen, and strtoul. It might be a bit cleaner
to fold the validation and conversion together into a single pass.
Something like
- if (suffix != NULL && suffix[1] >= '1' && suffix[1] <= '9' &&
- strspn(suffix + 1, "0123456789") == strlen(suffix + 1) &&
- strlen(suffix + 1) <= 10)
+ if (suffix != NULL && suffix[1] >= '1' && suffix[1] <= '9')
{
- char *base = pnstrdup(name, suffix - name);
- SubplanNameSuffix *entry = subplan_name_suffix(glob, base, false);
+ char *endptr;
+ unsigned long val = strtoul(suffix + 1, &endptr, 10);
- pfree(base);
- if (entry != NULL && strtoul(suffix + 1, NULL, 10) <
entry->next_suffix)
- return true;
+ if (*endptr == '\0')
+ {
+ char *base = pnstrdup(name, suffix - name);
+ SubplanNameSuffix *entry = subplan_name_suffix(glob, base,
false);
+
+ pfree(base);
+ if (entry != NULL && val < entry->next_suffix)
+ return true;
+ }
}
Not a big deal though...
Regards,
Ayoub
Hi Ayoub,
On Fri, Oct 30, 2026 at 2:57 AM Ayoub Kazar <ayoub.kazar@data-bene.io>
wrote:
One small suggestion: the suffix parsing in subplan_name_in_use() scans
the digits
multiple times across strspn, strlen, and strtoul. It might be a bit cleaner
to fold the validation and conversion together into a single pass.
Thanks, that reads better. Done in v3, attached. The length cap goes
too: next_suffix is an unsigned, and strtoul saturates instead of
wrapping, so a longer suffix never comes out below it.
Regards,
Manu
Manu <manuelreyesbravo@gmail.com> writes:
Thanks, that reads better. Done in v3, attached. The length cap goes
too: next_suffix is an unsigned, and strtoul saturates instead of
wrapping, so a longer suffix never comes out below it.
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.
I wonder if it'd be better to fold the two lists into one,
with a list of structs like
typedef struct SubplanNameData
{
const char *base; /* the base name */
bool taken; /* if true, the base name itself is taken */
unsigned next_suffix; /* if > 0, every smaller suffix is taken */
} SubplanNameData;
That doesn't directly fix the complication I mention above,
but maybe it'd provide a basis for documenting it. Or maybe
it's not helpful, not sure.
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.
regards, tom lane
Hi Tom,
On Sat, Oct 31, 2026 at 2:35 PM Tom Lane <tgl@sss.pgh.pa.us> 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
On 01/11/2026 01:55, Manu wrote:
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.
Aside: The last test on:
+-- a name of NAMEDATALEN - 1 bytes, used twice
+EXPLAIN (COSTS OFF)
+WITH nnnnnnnnnnnnnnnnnnn
This isn't a concern anymore so we don't need this i think?
Also v3 had this test:
+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)
+
I guess we should keep this for expr_1_1 case ...
Regards,
Ayoub
Hi Ayoub,
On Sun, Nov 1, 2026 at 3:31 AM Ayoub Kazar <ayoub.kazar@data-bene.io>
wrote:
+-- a name of NAMEDATALEN - 1 bytes, used twice
This isn't a concern anymore so we don't need this i think?
Agreed, there are no keys to truncate any more; v5 drops it.
I guess we should keep this for expr_1_1 case ...
Yes, it is the case where the generated name comes first. v5,
attached, brings it back next to the other two; the code is unchanged.
Regards,
Manu
Attachments:
t254133_11v5-0001-Avoid-O-N-3-planning-time-in-choose_plan_name.patchtext/x-patchDownload+158-50
On Sat, Oct 31, 2026 at 2:36 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
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.
FTR, I don't think there's anything particularly magical about the
names the current code generates. I was aiming to have the code be
clearly correct, and I admit I spent no time worrying about cases with
4000 subqueries. Hence, it's fine with me if we change the algorithm,
but I agree that should ideally only be done as part of a major
release. The complicated part is making sure that generated names
don't collide with user-written names that might happen to have the
same format. It's also important that the set of names we end up with
doesn't depend on what the planner chooses to do. We want expr_5 to
mean the same thing no matter how the query gets planned, because
advice strings can refer to it.
I don't see an email from Heikki in this thread so I'm not sure what
that proposal was specifically.
--
Robert Haas
Databricks
Hi Robert,
On Tue, Nov 3, 2026 at 9:21 AM Robert Haas <robertmhaas@gmail.com>
wrote:
It's also important that the set of names we end up with
doesn't depend on what the planner chooses to do. We want expr_5 to
mean the same thing no matter how the query gets planned, because
advice strings can refer to it.
On master that already doesn't hold when a custom plan folds a sublink
away:
CREATE TABLE t (a int, b int); CREATE TABLE t2 (a int, b int);
PREPARE p(int) AS
SELECT CASE WHEN $1 = 0 THEN NULL
ELSE (SELECT sum(b) FROM t2 WHERE a = t.a AND b = 1) END,
(SELECT sum(b) FROM t2 WHERE a = t.a AND b = 2),
(SELECT sum(b) FROM t2 WHERE a = t.a AND b = 3)
FROM t;
With EXECUTE p(0), the custom plan names the b = 2 and b = 3 sublinks
expr_1 and expr_2, and the generic plan names them expr_2 and expr_3,
so expr_2 is a different subquery in each. v5 keeps master's names,
so it behaves the same; a single counter would extend this to
subplans of other kinds.
Regards,
Manu
On Tue, Nov 3, 2026 at 9:54 AM Manu <manuelreyesbravo@gmail.com> wrote:
On master that already doesn't hold when a custom plan folds a sublink
away:CREATE TABLE t (a int, b int); CREATE TABLE t2 (a int, b int);
PREPARE p(int) AS
SELECT CASE WHEN $1 = 0 THEN NULL
ELSE (SELECT sum(b) FROM t2 WHERE a = t.a AND b = 1) END,
(SELECT sum(b) FROM t2 WHERE a = t.a AND b = 2),
(SELECT sum(b) FROM t2 WHERE a = t.a AND b = 3)
FROM t;With EXECUTE p(0), the custom plan names the b = 2 and b = 3 sublinks
expr_1 and expr_2, and the generic plan names them expr_2 and expr_3,
so expr_2 is a different subquery in each. v5 keeps master's names,
so it behaves the same; a single counter would extend this to
subplans of other kinds.
Right. I'm not sure how much of a practical concern this type of case
is, but I won't be enormously surprised if it inconveniences some user
and they want us to do better. We'll have to think about how realistic
a goal that is, and how much better we could actually do, and most
likely that's work for v20 or later. In this example, I think the
subquery names will be stable if you always use generic plans, and I
think they will be stable if you always use custom plans and the
parameter values are unchanged. But they may change between different
custom plans with different parameter values, which I think is fine.
And they may also change between custom plans and generic plans, which
is less fine but I don't think we can do anything about it in time for
v19.
A sort of general point that I'd like to make here in this age of
AI-driven bug hunting is that there are infinite bugs that we can try
to fix, but we only have so much time to fix things and need to direct
our limited time into the things that are most worthwhile. It isn't
entirely clear to me that this is a real issue that's going to bother
real users; I coded the feature as I did because I did not expect the
number of subqueries to exceed a few dozen. You're not wrong to ask
what happens if someone violates that expectation, and I'm not against
improving the code, but I don't want to spend a ton of effort or code
on what seems like something of a corner case, either.
My proposal is:
- 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 lowering the cost from O(N^3) to O(N^2) is judged acceptable,
then all we need is to use the hash table to replace linear searches
of glob->subplanNames, and only when it's been built.
- 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. When we enter choose_plan_name, we do a lookup
of "name" in this hash table, if it's been built. If no entry is found
and !always_number, we can use the exact name. If an entry is found,
we can change the "If a numeric suffix" loop to start the search from
the value found in the hash table.
I think this is similar to Tom's proposal upthread, except that I'd
rather use a hash table than rely on lists, because anything that
relies on lists can always be made to be at least O(N^2) by manually
assigning names to every subquery and making them all different. I
think Tom's proposal, and your v5, only work when all the names are
autogenerated from the same base name. That's an important special
case, but I'm a little worried that if we just fix that, someone will
come along next week with an LLM-generated report about the more
general case.
--
Robert Haas
Databricks
Hi Robert,
On Tue, Nov 3, 2026 at 11:17 AM Robert Haas <robertmhaas@gmail.com>
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
Attachments:
t254133_15v6-0001-Avoid-O-N-3-planning-time-in-choose_plan_name.patchtext/x-patchDownload+281-30
measurements.txttext/plainDownload
On Wed, Nov 4, 2026 at 4:55 PM Manu <manuelreyesbravo@gmail.com> wrote:
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.
Huh, that seems surprising. I expected the case with 4000 CTEs with
different names to be much worse. Why is the UNION case such a
disaster compared to everything else? I must be missing something
here. Of course, strcmp() on every list item is more expensive when
there's a prefix match, but I wouldn't expect that to make so much
difference.
--
Robert Haas
Databricks
Hi Robert,
On Fri, Nov 6, 2026 at 9:41 AM Robert Haas <robertmhaas@gmail.com>
wrote:
Huh, that seems surprising. I expected the case with 4000 CTEs with
different names to be much worse. Why is the UNION case such a
disaster compared to everything else? I must be missing something
here. Of course, strcmp() on every list item is more expensive when
there's a prefix match, but I wouldn't expect that to make so much
difference.
It's the number of strcmp() calls, not the cost of each. With a
counter in choose_plan_name() on today's master (median of 5):
UNION, 4000 arms: 10,674,664,000 strcmp() calls, 16.88 s in the
function out of 16.92 s of planning
CTEs, 4000 names: 7,998,000 strcmp() calls, 22 ms in the function
out of 154 ms of planning
A name nobody has used yet costs one pass over the list, so N
different names make N(N - 1)/2 calls. The UNION arms all ask for
"setop" with always_number, so the suffix loop starts at 1 in every
arm: the k-th arm tries setop_1 .. setop_k, and each try scans the
list until it finds that name; the last one scans all of it. That
makes (N^3 - N)/6 + N(N - 1)/2.
Per call the UNION is actually the cheaper case, 1.6 ns against
2.8 ns, so the prefix match isn't what hurts.
Regards,
Manu
Hi Robert,
I did not expect the number of subqueries to exceed a few dozen.
I can confirm it is a real issue, we have it in a real application. The application generates its SQL, and a typical statement has 250 scalar sublinks (expr_N), around 100 subqueries with the same alias, around 170 CTEs and a UNION ALL with about 100 arms.
With 19.0 this statement needs about 78 ms for planning, with 18.7 about 40 ms. Same data, statistics and build options, and the execution time is the same in both. In a profile about 40% of the planning time is strcmp() in choose_plan_name(). For the whole application this makes the requests 3.5% slower, the heavier ones 5-9%.
You wrote that with a list also distinct names can make it O(N^2). We see this too. When I change the statement so most subqueries have their own alias and most scalar sublinks are gone, it still needs about 52 ms on 19.0 (40 ms on 18.7), and most of the difference is still in choose_plan_name(). As far as I see, your hash table idea would solve both cases for us.
So for us this is for sure a real world use case. Generated SQL gets to these numbers in normal use.
Regards,
Andreas Fe
On Friday, November 20th, 2026 at 2:26 PM, Robert Haas <robertmhaas@gmail.com> wrote:
Show quoted text
On Tue, Nov 3, 2026 at 9:54 AM Manu <manuelreyesbravo@gmail.com> wrote:
On master that already doesn't hold when a custom plan folds a sublink
away:CREATE TABLE t (a int, b int); CREATE TABLE t2 (a int, b int);
PREPARE p(int) AS
SELECT CASE WHEN $1 = 0 THEN NULL
ELSE (SELECT sum(b) FROM t2 WHERE a = t.a AND b = 1) END,
(SELECT sum(b) FROM t2 WHERE a = t.a AND b = 2),
(SELECT sum(b) FROM t2 WHERE a = t.a AND b = 3)
FROM t;With EXECUTE p(0), the custom plan names the b = 2 and b = 3 sublinks
expr_1 and expr_2, and the generic plan names them expr_2 and expr_3,
so expr_2 is a different subquery in each. v5 keeps master's names,
so it behaves the same; a single counter would extend this to
subplans of other kinds.Right. I'm not sure how much of a practical concern this type of case
is, but I won't be enormously surprised if it inconveniences some user
and they want us to do better. We'll have to think about how realistic
a goal that is, and how much better we could actually do, and most
likely that's work for v20 or later. In this example, I think the
subquery names will be stable if you always use generic plans, and I
think they will be stable if you always use custom plans and the
parameter values are unchanged. But they may change between different
custom plans with different parameter values, which I think is fine.
And they may also change between custom plans and generic plans, which
is less fine but I don't think we can do anything about it in time for
v19.A sort of general point that I'd like to make here in this age of
AI-driven bug hunting is that there are infinite bugs that we can try
to fix, but we only have so much time to fix things and need to direct
our limited time into the things that are most worthwhile. It isn't
entirely clear to me that this is a real issue that's going to bother
real users; I coded the feature as I did because I did not expect the
number of subqueries to exceed a few dozen. You're not wrong to ask
what happens if someone violates that expectation, and I'm not against
improving the code, but I don't want to spend a ton of effort or code
on what seems like something of a corner case, either.My proposal is:
- 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 lowering the cost from O(N^3) to O(N^2) is judged acceptable,
then all we need is to use the hash table to replace linear searches
of glob->subplanNames, and only when it's been built.- 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. When we enter choose_plan_name, we do a lookup
of "name" in this hash table, if it's been built. If no entry is found
and !always_number, we can use the exact name. If an entry is found,
we can change the "If a numeric suffix" loop to start the search from
the value found in the hash table.I think this is similar to Tom's proposal upthread, except that I'd
rather use a hash table than rely on lists, because anything that
relies on lists can always be made to be at least O(N^2) by manually
assigning names to every subquery and making them all different. I
think Tom's proposal, and your v5, only work when all the names are
autogenerated from the same base name. That's an important special
case, but I'm a little worried that if we just fix that, someone will
come along next week with an LLM-generated report about the more
general case.--
Robert Haas
Databricks
Hi Andreas,
On Fri, Nov 20, 2026 at 1:36 PM UTC, Andreas <andreasfe@pm.me> wrote:
As far as I see, your hash table idea would solve both cases for us.
That hash table is what v6 does, posted on 4 November:
/messages/by-id/179382931036.1743405.1568941311065599844@gmail.com
It applies to master and REL_19_STABLE as of today. If you can plan
your statement with it, the numbers against 18.7 would show whether
it is enough for 19.
Regards,
Manu
On Fri, Nov 20, 2026 at 8:36 AM Andreas <andreasfe@pm.me> wrote:
I can confirm it is a real issue, we have it in a real application. The application generates its SQL, and a typical statement has 250 scalar sublinks (expr_N), around 100 subqueries with the same alias, around 170 CTEs and a UNION ALL with about 100 arms.
With 19.0 this statement needs about 78 ms for planning, with 18.7 about 40 ms. Same data, statistics and build options, and the execution time is the same in both. In a profile about 40% of the planning time is strcmp() in choose_plan_name(). For the whole application this makes the requests 3.5% slower, the heavier ones 5-9%.
Well, that sucks. Sorry about that.
You wrote that with a list also distinct names can make it O(N^2). We see this too. When I change the statement so most subqueries have their own alias and most scalar sublinks are gone, it still needs about 52 ms on 19.0 (40 ms on 18.7), and most of the difference is still in choose_plan_name(). As far as I see, your hash table idea would solve both cases for us.
So for us this is for sure a real world use case. Generated SQL gets to these numbers in normal use.
OK. Can you test Manu's latest patch and see how that does with your workload?
I would normally be somewhat reluctant to back-patch anything here,
but if people are hitting this on real workloads within days of
release, I think we should.
--
Robert Haas
Databricks