Outliers produce a bad query plan

Question

I have table document with ~2.5 millions rows and more than 100 columns. I provide only used in query columns:

CREATE TABLE document
(
  id serial PRIMARY KEY,
  organizationid INTEGER,
  status_1 TEXT NOT NULL,
  status_2 INTEGER DEFAULT 0 NOT NULL
);

CREATE INDEX ON document (organizationid);
CREATE INDEX ON document (status_1);
CREATE INDEX ON document (status_2);

Need to optimize next query:

SELECT *
FROM document
WHERE status_1 = '42' AND status_2 = 0 AND organizationid = 42 
ORDER BY id
LIMIT 25;

This query works great for other organizations, but organization 42 does not have documents with this filter (or have less than 20 time to time), and it produces bad query plan and slow query. The problem is in distributions of values in the table. Percent of documents with status_1 = '42' is 95%, status_2 = 0 is 10% and organizationid = 42 is 2%. So DB expects that there are ~4750 documents for this filter and make index scan using documnet_pkey and scan full table without finding any documents. It takes several minutes. But if I change organization to another, that has a lot of documents, the query will take less than a second. And if I change filter to organization with small amount of documents - DB just use index by organizationid and then sort resulted documents. It takes less than 50 ms.

How can I speed up the query for organization 42? Or what I need to research for it?

I use PostgreSQL 12

auto- vacuum and analyze enabled, and I ran analyze again before tests. I already increase GEQO_EFFORT to 10 (max), DEFAULT_STATISTICS_TARGET to 1000 (more value impact on other queries), created statistic:

CREATE STATISTICS custom_1 ON organizationid, status_1, status_2 FROM document;

created specific index:

CREATE INDEX ON document ((status_1 = '42' AND status_2 = 0 AND organizationid = 42));

and rerun analyze after all changes. But it doesn't help. I checked pg_stats and pg_stats_ext, it contains correct statistic as expected. For the created statistic, it has in most common value other combination of these columns and doesn't have this combination, so it is able to assume that combination in where is uncommon. For index on expression, statistic says that there is only false values in index.

Answer 1

The ideal index for these queries would be:

CREATE INDEX ON document (organizationid, status_1, status_2, id);

This should fix the specific query parameters you have a major problem with, and should also improve all the other parametrizations as well.

The custom statistics on the columns might do a good job of fixing the estimate when a combination is more common than expected, but usually a poor job of fixing it when the combination is less common than expected, which is the case here.

Your expression index could work, but only if the query is awkwardly written as:

...
WHERE (status_1 = '42' AND status_2 = 0 AND organizationid = 10) is true
...

A custom statistics (rather than index) on that expression could also "work", but those weren't implemented until v14 and it would still require the awkwardly written query. But at that point, it would fix the estimate, but inhibit the index usage you want to get it to use (the bitmap on the single column indexes), so it would "work" but still wouldn't work.