Weird planning time data dependency in Postgres We got a fairly large table holding session data in Postgres. Recently, we found that the planning time for the most common query on this particular table increased over time, at one point to ~130ms which starved the whole instance. The planning time went back to normal after vacuuming and analyzing but is slowly creeping up again. What's particularly strange though is that the planning time seems to depend on the input data: 

explain analyze select * from django_session where expire_date &gt; now() limit 1;
                                                          QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.05 rows=1 width=207) (actual time=0.008..0.009 rows=1 loops=1)
   -&gt;  Seq Scan on django_session  (cost=0.00..6357552.08 rows=129398117 width=207) (actual time=0.008..0.008 rows=1 loops=1)
         Filter: (expire_date &gt; now())
 Planning Time: 7.201 ms
 Execution Time: 0.022 ms


In contrast to:

explain analyze select * from django_session where expire_date &gt; now() + interval '2 days' limit 1;
                                                          QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.05 rows=1 width=207) (actual time=0.008..0.009 rows=1 loops=1)
   -&gt;  Seq Scan on django_session  (cost=0.00..6681337.26 rows=128206390 width=207) (actual time=0.008..0.008 rows=1 loops=1)
         Filter: (expire_date &gt; (now() + '2 days'::interval))
 Planning Time: 0.053 ms
 Execution Time: 0.020 ms


This cut-off of about 2 days between increased and normal planning time exists regardless of what type of comparison is made (i.e. &lt;, >, = all have the same effect).

The table is cleaned up every day by deleting old sessions that are expired. 

Given the range of expiry_date of up to a year in the future could it be that Postgres' heuristic assumes that an expiry_date in the near future is an unlikely input? Why does this only happen when querying for this particular column and none of the others in the same table?
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.