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

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(dot)kazar(at)data-bene(dot)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(at)anarazel(dot)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(at)sss(dot)pgh(dot)pa(dot)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