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