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

Hi Robert,

On Tue, Nov 3, 2026 at 11:17 AM Robert Haas <robertmhaas(at)gmail(dot)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