RE: Planner picks n² query plan when available

Thanks for your answers.

> What we have here is a straightforward way to write a query versus a much-less-straightforward way [...] So I'm not seeing why we should put our finite development resources into optimizing the much-less-straightforward way.

Ah, I should have explained this: this was meant as a pure-SQL reproducer for n² query plans with:

```sql
SELECT id FROM indexed_table WHERE indexed_value = ANY ($1)
```

where `$1` is an array bind parameter.

I recall having seen the same O(n²) issue with this, even after PG 14 (50e17ad2), so I thought the SQL version being slow would be the same effect...
However I have just attempted a reproducer for the `$1` variant (writing the corresponding application code...), and couldn't reproduce the inefficiency.
I also thought I saw that even `= ANY(ARRAY[1,2])` would lose the size to `10` so I assumed the same issue would happen with `$1` (array) but I tried to reproduce that as well and couldn't, so I must have been looking at a different planner node. 😵‍💫

Considering this seems to not affect `= ANY ($1)`, this indeed makes this issue significantly less important than I first thought. I'll let you know if I manage to reproduce this again but that seems unlikely at this point.

> It's a little disingenuous to complain about bad estimates with this test methodology: the test tables are never vacuumed or analyzed.

Apologies, I had originally put ANALYZEs for the temp tables as well but then removed them to minimize the example as they didn't change the plans or resulting estimate of `10`, and row estimates for the subselect were still of the correct order of magnitude. I shouldn't have done that, as that did spend your time wondering about this.

Just for completeness (but I wouldn't have created this thread just for this):

While this is an example of a scenario where = ANY(array) performs badly and = ANY(subquery) performs well, I have also found occurences where = ANY (ARRAY(subquery)) lets the planner push filters further down and performs an order of magnitude better as well, so if this was improved we might be able to say "just always use `= ANY(array)`", which would be simpler.

> IIUC, hashed "= ANY()" expressions were already implemented

Thanks for pointing to the particular commit.

I can see [here](https://github.com/postgres/postgres/blob/4c4aaa19a6fed39e0eb0247625331c3df34d8211/src/backend/optimizer/util/clauses.c#L2278) that it is a requirement that "The 2nd argument of the array contain only Consts"

Since the limit of elements before it chooses hash is 9, it looks like if this wasn't a constraint, the hardcoded 10 of the subquery case would be handled with reasonable efficiency.
I'm wondering what creates this constraint.

It looks like solving this may improve performance for the case where `= ANY(ARRAY(subquery))` allows the planner to push filters further down but the subquery produces many results.

(Also it looks like in that case the executor could even look at "would I know how to do this?" set by the planner, and decide whether to actually do it by checking the actual length of the array at that point rather than having decided based on estimates.)

> Did you recheck [that the planner always supposes that arrays are of size 10] on a recently released version of PostgreSQL? IIRC this was updated in PG17 (9391f715)

I have just run the reproducer script on PG 17.1 and observe the same thing: wrong row estimate, and O(n²) plan getting picked.
Writing it as `ARRAY(SELECT value ..)` produces the same results as writing it as `(SELECT array_agg(value) ..)` or `ARRAY(VALUES ..)`.

Simpler reproducer for loss of array size when building arrays from subselects (PG 17.1):

```sql
EXPLAIN ANALYZE SELECT UNNEST(ARRAY(VALUES (1), (2)));
/* Gives:
ProjectSet (cost=0.03..0.09 rows=10 width=4) (actual time=0.009..0.011 rows=2 loops=1)
InitPlan 1
-> Values Scan on ""*VALUES*"" (cost=0.00..0.03 rows=2 width=4) (actual time=0.001..0.002 rows=2 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.002..0.002 rows=1 loops=1)
Planning Time: 0.052 ms
Execution Time: 0.026 ms
*/
```

Should I open a separate "bug" thread for this particular issue given [the commit you mentioned](https://github.com/postgres/postgres/commit/9391f71523b6e57f1194d9f6543bc7948c16411b), or is that expected behavior ?

(My understanding is that this wouldn't solve the performance problem of the original query given the const array limitation but this may improve other cases.)

Thanks again for your time!
________________________________
De : Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Envoyé : jeudi 21 novembre 2024 14:52
À : Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com>
Cc : Toto guyoyg <thomas(dot)bessou(at)hotmail(dot)fr>; pgsql-hackers(at)postgresql(dot)org <pgsql-hackers(at)postgresql(dot)org>
Objet : Re: Planner picks n² query plan when available

Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> writes:
> On Thu, 21 Nov 2024 at 13:03, Toto guyoyg <thomas(dot)bessou(at)hotmail(dot)fr> wrote:
>>
>> Offending O(n²) query:

> I disagree with the O(n^2) claims.

I think these cases actually are O(n^2). But I'm finding it hard
to care. What we have here is a straightforward way to write a
query versus a much-less-straightforward way --- indeed, a way
that isn't even syntactically legal per the SQL standard.
The straightforward way is already well optimized, and no reason has
been given why the much-less-straightforward way should be considered
preferable. So I'm not seeing why we should put our finite
development resources into optimizing the much-less-straightforward
way.

>> 4. The EXPLAIN ANALYZE output shows that the planner always supposes that arrays are of size 10, instead of using the estimated sizes of subqueries they are created from, or actual size provided as argument.

It's a little disingenuous to complain about bad estimates with
this test methodology: the test tables are never vacuumed or
analyzed. And since they're temporary, there's no hope of
autovacuum curing that oversight. It's not clear that having
done that would improve anything in this particular case,
but it's certainly not helping.

regards, tom lane