Weird planning time data dependency in Postgres
The reason is an optimization in PostgreSQL, weird as it sounds.

When estimating result counts ow WHERE conditions like the one in your query, PostgreSQL uses a histogram, which is an approximation of the distribution of the values in the column.

Now these histograms are only re-calculated when 10% or more of the table has changed. With data like time-series, that can lead to a considerable skew, because the maximum (or minimum) of the values keeps increasing (or decreasing). So even if only a small percentage of the data change, the minimum or maximum can become inaccurate rather quickly.

To improve estimates, PostgreSQL commit 40608e7f949 has added a feature: when the cut-off value is in or beyond the last histogram bucket (as it is in your case), and if there is an index on the column, the optimizer will scan the index for the actual minimum or maximum and use that instead. This improves the quality of the estimate considerably.

However, there is a drawback. If the extreme values of the index all belong to deleted (&ldquo;dead&rdquo;) table rows, the index scan has to scan way more entries than it bargained for the get the actual minimum or maximum. This has been improved with commit 3ca930fc39c in version 11, which allows such an index scan to &ldquo;kill&rdquo; those index tuples, so that the next index scan can quickly ignore them.

I conclude that you must use a version older than v11.

There are two remedies:


Upgrade to v11 or better.
Set autovacuum_vacuum_scale_factor low (0.01 or lower) for that table, so that it is processed by autovacuum more often. VACUUM gets rid of those dead index entries, which will make query planning fast again.