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

Hi Robert,

On Fri, Nov 6, 2026 at 9:41 AM Robert Haas <robertmhaas(at)gmail(dot)com>
wrote:
> Huh, that seems surprising. I expected the case with 4000 CTEs with
> different names to be much worse. Why is the UNION case such a
> disaster compared to everything else? I must be missing something
> here. Of course, strcmp() on every list item is more expensive when
> there's a prefix match, but I wouldn't expect that to make so much
> difference.

It's the number of strcmp() calls, not the cost of each. With a
counter in choose_plan_name() on today's master (median of 5):

UNION, 4000 arms: 10,674,664,000 strcmp() calls, 16.88 s in the
function out of 16.92 s of planning
CTEs, 4000 names: 7,998,000 strcmp() calls, 22 ms in the function
out of 154 ms of planning

A name nobody has used yet costs one pass over the list, so N
different names make N(N - 1)/2 calls. The UNION arms all ask for
"setop" with always_number, so the suffix loop starts at 1 in every
arm: the k-th arm tries setop_1 .. setop_k, and each try scans the
list until it finds that name; the last one scans all of it. That
makes (N^3 - N)/6 + N(N - 1)/2.

Per call the UNION is actually the cheaper case, 1.6 ns against
2.8 ns, so the prefix match isn't what hurts.

Regards,
Manu