I've seen that on non-partial indexes when doing and order by query that has an index. The query planner sometimes preferentially chooses the ordering index to do an index scan, then filters out all the items that don't matche the query predicate. This is great when you're likely to take the last 10 timestamps, but falls flat when you have to check 100k items.

One sneaky way to deal with this is to order by an expression that can't be indexed, like id+0. I've had 4 order of magnitude speed ups when that sort of query tweaking pointed the planner at the right index. (And in that case, a partial index)