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
