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

On Tue, Nov 3, 2026 at 9:54 AM Manu <manuelreyesbravo(at)gmail(dot)com> wrote:
> On master that already doesn't hold when a custom plan folds a sublink
> away:
>
> CREATE TABLE t (a int, b int); CREATE TABLE t2 (a int, b int);
> PREPARE p(int) AS
> SELECT CASE WHEN $1 = 0 THEN NULL
> ELSE (SELECT sum(b) FROM t2 WHERE a = t.a AND b = 1) END,
> (SELECT sum(b) FROM t2 WHERE a = t.a AND b = 2),
> (SELECT sum(b) FROM t2 WHERE a = t.a AND b = 3)
> FROM t;
>
> With EXECUTE p(0), the custom plan names the b = 2 and b = 3 sublinks
> expr_1 and expr_2, and the generic plan names them expr_2 and expr_3,
> so expr_2 is a different subquery in each. v5 keeps master's names,
> so it behaves the same; a single counter would extend this to
> subplans of other kinds.

Right. I'm not sure how much of a practical concern this type of case
is, but I won't be enormously surprised if it inconveniences some user
and they want us to do better. We'll have to think about how realistic
a goal that is, and how much better we could actually do, and most
likely that's work for v20 or later. In this example, I think the
subquery names will be stable if you always use generic plans, and I
think they will be stable if you always use custom plans and the
parameter values are unchanged. But they may change between different
custom plans with different parameter values, which I think is fine.
And they may also change between custom plans and generic plans, which
is less fine but I don't think we can do anything about it in time for
v19.

A sort of general point that I'd like to make here in this age of
AI-driven bug hunting is that there are infinite bugs that we can try
to fix, but we only have so much time to fix things and need to direct
our limited time into the things that are most worthwhile. It isn't
entirely clear to me that this is a real issue that's going to bother
real users; I coded the feature as I did because I did not expect the
number of subqueries to exceed a few dozen. You're not wrong to ask
what happens if someone violates that expectation, and I'm not against
improving the code, but I don't want to spend a ton of effort or code
on what seems like something of a corner case, either.

My proposal is:

- 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 lowering the cost from O(N^3) to O(N^2) is judged acceptable,
then all we need is to use the hash table to replace linear searches
of glob->subplanNames, and only when it's been built.

- 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. When we enter choose_plan_name, we do a lookup
of "name" in this hash table, if it's been built. If no entry is found
and !always_number, we can use the exact name. If an entry is found,
we can change the "If a numeric suffix" loop to start the search from
the value found in the hash table.

I think this is similar to Tom's proposal upthread, except that I'd
rather use a hash table than rely on lists, because anything that
relies on lists can always be made to be at least O(N^2) by manually
assigning names to every subquery and making them all different. I
think Tom's proposal, and your v5, only work when all the names are
autogenerated from the same base name. That's an important special
case, but I'm a little worried that if we just fix that, someone will
come along next week with an LLM-generated report about the more
general case.

--
Robert Haas
Databricks