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

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