Re: Postgres picks suboptimal index after building of an extended statistics

Hi!

I'd like to get this subject off the ground. The problem originally
described in [1] obviously comes from wrong selectivity estimation.
"Dependencies" extended statistics lead to significant selectivity miss
24/1000 instead of 1/1000. When the estimation is correct, the PostgreSQL
optimizer is capable of choosing the appropriate unique index for the query.

Tom pointed out in [2] that this might be a problem of "Dependencies"
extended statistics. I've rechecked this. The dataset consists of two
parts. The first part defined in the CREATE TABLE statement contains
independent values. The second part defined in the INSERT statement
contains dependent values. "Dependencies" extended statistics estimate
dependency degree as a fraction of rows containing dependent values.
According to this definition, it correctly estimates the dependency degree
as about 0.5 for all the combinations. So, the error in the estimate comes
from the synergy of two factors: MCV estimation of the frequency of
individual values, and spreading of average dependency degree for those
values, which is not relevant for them. I don't think there is a way to
fix "dependencies" extended statistics because it works exactly as
designed. I have to note that instead of fixing "dependencies" extended
statistics you can just add multi-column MCV statistics, which would fix
the problem.

CREATE STATISTICS aestat(dependencies,ndistinct,mcv) ON x,y,z FROM a;

Independently on how well our statistics work, it looks pitiful that we
couldn't fix that using the knowledge of unique constraints on the table.
Despite statistics, which give us just more or less accurate estimates, the
constraint is something we really enforce and thus can rely on. The
patches provided by Andrei in [1], [3], and [4] fix this issue at the index
scan path level. As Thomas pointed out in [5], that could lead to
inconsistency between the number of rows used for unique index scan
estimation and the value displayed in EXPLAIN (and used for other paths).
Even though this was debated in [6], I can confirm this inconsistency.
Thus, with the patch published in [4], I can see the 28-row estimation with
a unique index scan.

` QUERY PLAN
-----------------------------------------------------------------------
Index Only Scan using a_pkey on a (cost=0.28..8.30 rows=28 width=12)
Index Cond: ((x = 1) AND (y = 1) AND (z = 1))
(2 rows)

Also, there is a set of patches [7], [8], and [9], which makes the
optimizer consider path selectivity as long as path costs during the path
selection. I've rechecked that none of these patches could resolve the
original problem described in [1]. Also, I think they are quite tricky.
The model of our optimizer assumes that paths in the list should be the
different ways of getting the same result. If we choose the paths by their
selectivity, that breaks this model. I don't say there is no way for
this. But if we do this, that would require significant rethinking of our
optimizer model and possible revision of a significant part of it. Anyway,
I think if there is still interest in this, that should be moved into a
separate thread to keep this thread focused on the problem described in [1].

Finally, I'd like to note that the issue described in [1] is mostly the
selectivity estimation problem. It could be solved by adding the
multi-column MCV statistics. The patches published so far look more like
hacks for particular use cases rather than appropriate solutions. It still
looks promising to me to use the knowledge of unique constraints during
selectivity estimation [10]. Even though it's hard to implement and
possibly implies some overhead, it fits the current model. I also think
unique contracts could probably be used in some way to improve estimates
even when there is no full match.

Links.
1.
https://www.postgresql.org/message-id/0ca4553c-1f34-12ba-9122-44199d1ced41%40postgrespro.ru
2. https://www.postgresql.org/message-id/3119052.1657231656%40sss.pgh.pa.us
3.
https://www.postgresql.org/message-id/90a1d6ef-c777-b95d-9f77-0065ad4522df%40postgrespro.ru
4.
https://www.postgresql.org/message-id/a5a18d86-c0e5-0ceb-9a18-be1beb2d2944%40postgrespro.ru
5.
https://www.postgresql.org/message-id/f8044836-5d61-a4e0-af82-5821a2a1f0a7%40enterprisedb.com
6.
https://www.postgresql.org/message-id/90a1d6ef-c777-b95d-9f77-0065ad4522df%40postgrespro.ru
7.
https://www.postgresql.org/message-id/2df148b5-0bb8-f80b-ac03-251682fab585%40postgrespro.ru
8.
https://www.postgresql.org/message-id/6fb43191-2df3-4791-b307-be754e648276%40postgrespro.ru
9.
https://www.postgresql.org/message-id/154f786a-06a0-4fb1-b8a4-16c66149731b%40postgrespro.ru
10.
https://www.postgresql.org/message-id/f8044836-5d61-a4e0-af82-5821a2a1f0a7%40enterprisedb.com

------
Regards,
Alexander Korotkov