Re: O(N^3) planning time in choose_plan_name() since 8c49a484e8e

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].

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]
https://www.postgresql.org/message-id/flat/d606f08e-3a56-409f-8591-ccdbb3379b0e%40data-bene.io