While working on a query recently, I noticed that Postgres was picking the wrong query plan for a query I would have expected to be quite simple. The original query plan was disastrous and the query would have taken an hour. Let’s see why it happened, and how I fixed it.

The dreadful sequential scan

Let’s say that we have the classic table structure for books and authors like this:

And let’s say that the book table contains about 500 million rows, and the author table contains about 15 million rows. Of course, the book table has an index on author_id. The query I wanted to perform was something like this:

SELECT title
FROM book
WHERE author_id = ANY(ARRAY[
    -- big array of 20 000 author IDs
])

The query plan I got from Postgres was something like this (in my real case, the data was larger so I interrupted the query, otherwise it would have taken nearly one hour):

Seq Scan on book  (cost=50.00..23744850.44 rows=226248550 width=214) (actual time=0.398..57972.022 rows=668908.00 loops=1)
  Filter: (author_id = ANY ('{1986,2506,2649,...}'::integer[]))
  Rows Removed by Filter: 501780796
  Buffers: shared hit=523834 read=15684221
Planning Time: 9.645 ms
Execution Time: 57988.687 ms

Postgres decided to go for a sequential scan on the book table. This did not match my expectation at all: why would Postgres not use the index on author_id? This query is very simple and a clear-cut use case for the index. A sequential scan on this huge table would be extremely costly, taking a long time and keeping the disk very busy.

So, how did we end up there?

Lies, damned lies, and database statistics

If you look at the query plan, it is clear that Postgres is vastly overestimating the number of rows returned. It estimates that we are asking for a significant fraction of the table. This is why Postgres prefers a sequential scan: if we want a big chunk of the table, it is cheaper to read it sequentially than to go through an index scan. But I am asking for 20 000 authors when there are 15 million, so I am in fact absolutely not asking for a big part of the table; I am merely asking for 0.13% of it.

The issue is caused by the way Postgres estimates the number of rows. The row count estimation from Postgres for such a simple query can be described (simplified) as:

Where TotalRows is the estimated total number of rows in the table according to Postgres¹, DistinctValues is the number of distinct values passed to the author_id filter condition, and TotalDistinctValues is the estimate of distinct values for the author_id column from the Postgres column statistics². In our case, DistinctValues is correctly 20 000, TotalRows is also correct at 500 million, but TotalDistinctValues is estimated at 45 000, instead of the correct value of 15 million.

The wrong estimate of n_distinct comes from the way statistics are gathered in Postgres. To get statistics, Postgres samples a subset of the table rows (30 000 by default³), and extrapolates from there an estimate for the whole table.

Once Postgres has acquired the sample of values, the estimation of distinct values is determined through this algorithm (slightly simplified and assuming non-null values)⁴:

Where the Haas-Stokes Duj1⁵ estimator is:

where:

• is the number of rows in the sample
• is the estimated number of rows in the table
• is the number of distinct values in the sample
• is the number of values that appear exactly once in the sample

What the Duj1 algorithm does is estimate how many values are present in the whole table, depending on how many values are repeating in the sample. It is in a way the inverse of the birthday problem, and just like it, the result is not exactly intuitive and is very sensitive to changes in its inputs: in this case, the number of values that repeat in the sample. To give an example, if it saw 29 998 values appearing once and 1 value appearing twice in the sample, it would estimate that our column has around 237 million distinct values. If it saw 29 990 values appearing once and 5 values appearing twice instead, the estimate would be 76 million, already 3 times smaller!

This works well when the sample is statistically representative of the distribution of values in the whole table. Unfortunately for us, this sensitivity can cause big trouble when this assumption is broken.

It turns out that, because of the algorithm used by Postgres to sample, rows that are in the same block are more likely to be sampled together during ANALYZE. Postgres starts by taking 30 000 random blocks, and then picks rows at random in those blocks, until reaching the expected 30 000-row sample⁶. This two-step sampling method is designed to make each row equally likely to be included in the sample while being cheap to compute. Given that blocks hold a variable number of rows that is not known beforehand, Postgres could not cheaply do a truly random uniform sample of rows without scanning the whole table. And simply picking 30 000 random blocks and one row per block would favor rows present in blocks with fewer rows in them. The algorithm from Postgres is actually pretty elegant and provides good statistical properties for a random sample at low cost.

The outcome however is that some of the sampled blocks will have more than one row picked. In fact, assuming about 33 rows per block (the average for our example), here’s a representation of how many rows each sampled block contributes to the final row sample, using Postgres’s method vs a fully random sample of rows of the table.

This behavior is not usually an issue for statistics gathering, because randomness inside a block is enough not to bias the sample significantly. But in our case, the book table was mostly populated by inserting rows from the same author together. This means that within the same block, rows are likely to have the same author_id. In fact, because we have about 33 rows per author, roughly matching a whole block, the likelihood that two rows in the same block share the same author_id is about 2/3. We are therefore much more likely to have multiple values appearing several times than in a fully random sample.

Using the numbers above, this gives us the following estimation for n_distinct on author_id:

Compared to what we would have gotten from a truly random sample:

The simple fact that we write multiple rows for the same author consecutively changes the estimate of n_distinct by more than 300×!

How to fix it

The fix is very easy: instead of relying on Postgres’s automatic statistics, it is possible to set n_distinct manually for a column. And instead of setting an absolute value, we can set a negative value corresponding to the ratio of distinct values to rows. This allows the value to stay relevant even as the table grows, as long as the distribution of values remains approximately the same.

In our case we want

And it can be applied in Postgres through a simple SQL command:

ALTER TABLE book ALTER COLUMN author_id SET (n_distinct = -0.03);
ANALYZE book (author_id);

Note that the ANALYZE command is necessary: the override only takes effect at the next ANALYZE.

After such a change, the query plan uses the index as I would have expected:

Bitmap Heap Scan on book  (cost=94888.67..2324399.27 rows=666667 width=214) (actual time=2783.478..4133.591 rows=668908.00 loops=1)
  Recheck Cond: (author_id = ANY ('{1986,2506,2649,...}'::integer[]))
  Heap Blocks: exact=40905
  Buffers: shared hit=58081 read=61122 written=46727
  ->  Bitmap Index Scan on book_author_id_idx  (cost=0.00..94672.00 rows=666667 width=0) (actual time=2780.373..2780.374 rows=668908.00 loops=1)
        Index Cond: (author_id = ANY ('{1986,2506,2649,...}'::integer[]))
        Index Searches: 19563
Planning Time: 7.149 ms
Execution Time: 4148.385 ms

This is a 14× gain on a cold test database. In real usage, with a hot index cache, the speedup can be even larger: a test run with a fully hot index brought it down to 300 ms, so a speedup of around 200× compared to the original query.

Not bad for what is basically a one-line fix!

As usual, the moral of the story is that Postgres is damn smart, but may need your help to get the ideal query plan. It is built on many assumptions and compromises, and things can go wrong quickly when they are not aligned with your specific case, especially as scale gets larger.

Footnotes

1. This is coming from reltuples in the pg_class system catalog, which stores the estimated number of rows for each table. Ex: SELECT reltuples FROM pg_class WHERE relname = 'book'; ↩

2. This is n_distinct in the pg_stats system catalog, which stores the estimated number of distinct values for each column. Ex: SELECT n_distinct FROM pg_stats WHERE tablename = 'book' AND attname = 'author_id'; ↩

3. The exact value is 300 × default_statistics_target, which defaults to 100. ↩

4. See compute_scalar_stats in the Postgres source code. ↩

5. Peter J. Haas and Lynne Stokes, Estimating the Number of Classes in a Finite Population, Journal of the American Statistical Association 93 (444), 1998, pp. 1475–1487. A preprint version (IBM Research Report RJ 10025) is freely available; it is also the reference cited in the Postgres source code. ↩

6. See acquire_sample_rows in the Postgres source code. ↩