The Query That Was Fast for Two Years and Then Was Not

The query had an index, the index was used for two years, and then, over a week or so, the query got slower and slower without any deploy touching it. The team diffed code, found nothing, and suspected the database. The database had indeed changed its behaviour, but the change was not a regression. It was a decision, recomputed continuously, and the input to the decision that changed was the size of the table, which had crossed the threshold where the planner's arithmetic flips from index to scan.

I have lost on-call weeks to this exact shape of slow burn, so the order below is the order I fix it in.

Plans are not chosen once. They are chosen per execution against current statistics and current cost parameters, and both of those move as the table grows, so a query can drift from fast to slow with a perfectly stable codebase. This is the growth version of the plan cache story in the slow query that ran in four milliseconds under EXPLAIN, except here even the fresh EXPLAIN shows the slow plan, because the slow plan is now correct.

This was Postgres 16.3, a table that grew from a few million rows to a few hundred million, and a selective query whose selectivity slowly got less selective.

The planner's arithmetic, briefly

The planner estimates the cost of each candidate plan from the statistics: how many rows match, how scattered they are, how much of the table must be read, and whether the pages are likely cached. An index scan is cheap when it touches few rows that are clustered, and expensive when it bounces around the heap for many rows. A sequential scan is expensive on a large table but has a cost per row that does not depend on selectivity.

The two cost lines cross. Above a certain fraction of the table matching, or a certain scatter, the sequential scan's line is below the index scan's, and the planner chooses it, correctly. The threshold is not a bug. It is the planner doing its job against a table that is no longer the table the index was added for.

The second threshold is the cache. An index scan's heap bounces are cheap while the hot pages sit in memory and become physical IO when the working set exceeds it, and the planner's random page cost parameter encodes an assumption about that. A table that used to fit now does not, so the same plan that was cached bounces is now disk, and the cost model, which may still assume the old hit rate, and the reality, diverge, and the divergence shows up as the plan that is right on paper and slow on disk.

Why it degrades over a week, not a deploy

The statistics are refreshed by analyse, which runs on thresholds, so the planner's picture of the table updates in steps as the table grows, and each refresh can nudge the estimated row counts, and the nudge can cross the cost crossover. Meanwhile the cache threshold is crossed continuously as the working set grows past memory. The combination is a degradation that looks gradual from the outside and is a series of small decisions inside, none of which is wrong, which is why no diff explains it.

This is the signature to remember: a query whose plan changed with no code change, degrading with the data's growth, is a threshold crossing, and the investigation should measure the table and the plan over time, not the code.

Seeing the flip

The history of the plan is the diagnosis. If you have query statistics collection, the plan change with its timestamp is visible directly, and it will line up with an analyse or a growth milestone. Without it, reconstruct: EXPLAIN now shows the scan, and the index's usage counters show the decline, the index that was scanned millions of times a day now scanned rarely, which is the flip made visible in the index statistics.

The cache half is visible in the buffers: the same query's buffers show shared read, physical IO, rising as the plan degrades, which is the working set no longer fitting, the same measurement as why an index only scan still read the heap but for the whole access path.

The fix, in order

Make the query selective again, if the product allows. The flip happened because the fraction matching grew. A tighter predicate, a time bound, a status filter, moves the query back under the threshold, and is the fix that scales, because it reduces the work rather than arguing with the planner.

Help the planner's estimate. If the estimate is wrong rather than the plan, more granular statistics, extended statistics for correlated columns, raise the statistics target on the column, change the chosen plan back, because the planner chose the scan on a bad row estimate, and fixing the estimate restores the index honestly.

Accept the scan and make it cheap. If the query genuinely touches a large fraction now, the index was the wrong tool for the new shape, and the honest fix is the scan optimised: a partial index for the hot slice, a covering index so the scan is an index scan, or precomputation, because fighting the planner to force an index on a query that now needs most of the table is paying bounce cost to avoid a sequential read, which is backwards.

Right size the cache or the table. If the degradation is the cache threshold, the working set either gets more memory, or the table gets smaller, via archiving the cold rows, which is a capacity decision and should be made as one, with the numbers, rather than discovered as a latency incident.

The takeaway

A plan is a decision against current statistics and current size, and both move, so a query can cross from index to scan with no code change, degrading over the weeks the table grows. Watch the plan and the index usage over time, treat a stable query's slow week as a threshold crossing, and fix by restoring selectivity, fixing the estimate, or accepting the scan and making it cheap.

The codebase was innocent. The table voted, and the planner agreed with the table. The same "the input distribution moved under a stable system" lesson is the noisy neighbour post for memory and the p99 post for latency, and the growth chart is the only witness that saw it happen.

Related reading: Your RAG Is Slow Because Retrieval Is an Untuned Database explores a connected angle.

Published on debugly.dev by Rohit Bhadani | Founder of Krova Cloud