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

From: Andreas <andreasfe(at)pm(dot)me>
To: Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: Manu <manuelreyesbravo(at)gmail(dot)com>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Ayoub Kazar <ayoub(dot)kazar(at)data-bene(dot)io>, Andres Freund <andres(at)anarazel(dot)de>, pgsql-hackers(at)lists(dot)postgresql(dot)org
Subject: Re: O(N^3) planning time in choose_plan_name() since 8c49a484e8e
Date: 2026-11-20 13:36:09
Message-ID: vZ3uW4SZVgqthfirPubPlILzxK3A57MbHBMcsElQU7ReNXXFbS7eCIH70bBZuzi7c08na3K6v1b2yHAF14s9oDWwwGNVJlPjoULy9UfRsd0=@pm.me
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi Robert,

> I did not expect the number of subqueries to exceed a few dozen.

I can confirm it is a real issue, we have it in a real application. The application generates its SQL, and a typical statement has 250 scalar sublinks (expr_N), around 100 subqueries with the same alias, around 170 CTEs and a UNION ALL with about 100 arms.

With 19.0 this statement needs about 78 ms for planning, with 18.7 about 40 ms. Same data, statistics and build options, and the execution time is the same in both. In a profile about 40% of the planning time is strcmp() in choose_plan_name(). For the whole application this makes the requests 3.5% slower, the heavier ones 5-9%.

You wrote that with a list also distinct names can make it O(N^2). We see this too. When I change the statement so most subqueries have their own alias and most scalar sublinks are gone, it still needs about 52 ms on 19.0 (40 ms on 18.7), and most of the difference is still in choose_plan_name(). As far as I see, your hash table idea would solve both cases for us.

So for us this is for sure a real world use case. Generated SQL gets to these numbers in normal use.

Regards,
Andreas Fe

On Friday, November 20th, 2026 at 2:26 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> 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
>
>
>
>
>

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message David Geier 2026-11-20 14:06:51 Re: Keep TIDBitmap pagetable memory across bitmap scans
Previous Message Andrew Dunstan 2026-11-20 13:15:58 Re: Table AM callback for logical decoding support (REPACK CONCURRENTLY)