`WHERE status = 'pending'` is not enough to avoid the performance problem, even if you have an index on `(status)`, because the index will still contain dead tuples until it is vacuumed.

Rough intuition: Postgres doesn't immediately delete rows, it just marks them as invalid after a certain snapshot version/transaction ID (and this mark is in the heap, not the indexes, AFAIK).

Every potential tuple that your index returns, Postgres needs to visit the heap to see if that tuple is alive. UNLESS all the tuples in that heap page are alive, in which case an optimisation called the 'visibility map' allows that check to skipped (relevant for Index-Only Scans, where Postgres can get all the results for your query from the index directly).

The only way to avoid the problem is therefore to either vacuum frequently enough that Postgres doesn't get any dead tuples returned from the index (that it must then visit the heap to check for liveness), or to bake in some condition to your queries that prevents the dead tuples from being returned from the index altogether. Vacuuming frequently is expensive and conflicts with having long-running transactions, so the latter option is generally the choice to go for when it matters.

[n.b. I feel I should note I am not a Postgres developer and wouldn't call myself an expert, just an enthusiast and dealt with a few problems here and there. So what I say should be taken with a grain or two of salt, though I believe it to be accurate.]