Thread: Planner picks n² query plan when available

On Thu, 21 Nov 2024 at 13:03, Toto guyoyg <thomas.bessou@hotmail.fr> wrote:
>
> Offending O(n²) query:

I disagree with the O(n^2) claims. The number of live matched rows in
a single table's bitmap scan may be anywhere from 0 (leading to O(1)
complexity in the rescan) to 970_662_608_670 (= 226 tuples per page *
(2^32 - 1) pages), so such a rescan's complexity - given O(n)
complexity for always choosing to use a linear scan on the array to
find matches - would better be parameterized as O(n*m), for m live
tuples in the generated bitmap, or even O(n*m + k), as the bitmap may
contain k dead tuples which can also take some measurable amount of
effort to scan.

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

Did you recheck this on a recently released version of PostgreSQL?
IIRC this was updated in PG17, and with `= ANY (ARRAY[...])`
expressions you will get the expected number of rows for that array
expression (assuming accurate statistics on your table).

> It looks like this could be improved/fixed by either/all of:
>
> 1. Using a hashset (or sort + binary search) for recheck (past a certain array length or even always) instead of
alwayssearching linearly 

IIUC, hashed "= ANY()" expressions were already implemented with
commit 50e17ad2 (released in PG14) - look for
EEOP_HASHED_SCALARARRAYOP in expression handling code.

> 2. Fixing planner assuming that all arrays are of size 10, using instead actual or estimated sizes.

IIUC, this was also already implemented with commit 9391f715 (released in PG17).

> Taking it into account for recheck cond cost estimation. (This wouldn't solve recheck perf, but at least would make
theplanner aware that lossy heap scans and Hash index bitmap heap scans are n times more expensive than exact BTree
bitmapheap scans, and hopefully make it avoid picking them.) 
>
> Is my understanding correct?

I believe your understanding may be quite out of date. Not all planner
or executor features and optimizations are explicitly present in the
output of EXPLAIN, and the examples all indicate you may be working
with an outdated view of Postgres' capabilities.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

Matthias van de Meent <boekewurm+postgres@gmail.com> writes:
> On Thu, 21 Nov 2024 at 13:03, Toto guyoyg <thomas.bessou@hotmail.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
theestimated 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

Matthias van de Meent <boekewurm+postgres@gmail.com> writes:
> On Thu, 21 Nov 2024 at 13:03, Toto guyoyg <thomas.bessou@hotmail.fr> wrote:
>> It looks like this could be improved/fixed by either/all of:
>>
>> 1. Using a hashset (or sort + binary search) for recheck (past a certain array length or even always) instead of
alwayssearching linearly 

> IIUC, hashed "= ANY()" expressions were already implemented with
> commit 50e17ad2 (released in PG14) - look for
> EEOP_HASHED_SCALARARRAYOP in expression handling code.

I checked into that and verified that this test case isn't reaching
EEOP_HASHED_SCALARARRAYOP, because that commit only addressed the
scenario where the array argument of =ANY is a constant.  (A
post-const-folding constant, but still a constant.)

To apply that optimization here, where the array is an output of a
subplan, we'd need some mechanism whereby ExecEvalHashedScalarArrayOp
could find out when the array has changed underneath it.  That's
probably possible (by somehow extending the chgParam signaling logic),
but the details aren't obvious.  The planner's decision about when
to apply hashing would become much less obvious, too.

>> 2. Fixing planner assuming that all arrays are of size 10, using instead actual or estimated sizes.

> IIUC, this was also already implemented with commit 9391f715 (released in PG17).

That's not helpful here either, since the arrays are built on-the-fly
rather than being stored in table columns (where stats could be
collected on them).  You could imagine installing bespoke logic for
array_agg() that looks at the estimated rowcount for the sub-select,
perhaps.

The bottom line here is that improving these queries would take a
significant amount of work, and they just aren't very compelling
examples that seem to justify such effort.  Folding the output of
a subquery into an array is largely an anti-pattern in SQL in the
first place.

            regards, tom lane

Toto guyoyg <thomas.bessou@hotmail.fr> writes:
>> What we have here is a straightforward way to write a query versus a much-less-straightforward way [...] So I'm not
seeingwhy 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.

Ah, well, you should have said that was what you wanted.  While the
existing EEOP_HASHED_SCALARARRAYOP logic only deals with a Const array
value, it seems to me that we could trivially let it use external
Params too.  The case you presented would require being able to cope
with intra-query changes of the array value, but a Param coming from
outside the query doesn't entail that.

> However I have just attempted a reproducer for the `$1` variant (writing the corresponding application code...), and
couldn'treproduce the inefficiency. 

Depending on what you tested, you might have only seen the behavior
with a "custom plan" where the Param is actually replaced with a
Const.  It would go bad again if the plan changed to generic.
I see that cost_qual_eval_walker does charge differently for
hashed than un-hashed ScalarArrayOp, so getting the planner to
incorrectly opt for a generic plan might require a bad estimate
of the array size, but I'm sure that's still possible.

> I also thought I saw that even `= ANY(ARRAY[1,2])` would lose the size to `10` so I assumed the same issue would
happenwith `$1` (array) but I tried to reproduce that as well and couldn't, so I must have been looking at a different
plannernode. 

Or old code ... as Matthias mentioned, we improved that not so long
ago.

            regards, tom lane