I did explore a solution which is my “plan B” — adding a “done” column, then using “UPDATE … SET done = true” rather than deleting the rows. This causes dead tuples, of course, but then adding a new index with a “… WHERE NOT done” filter fixes the problem by forcing the query to use the right index. However, with this solution, rows will still have to be deleted *sometime*, so this just delays the problem. But it would allow a “batch cleanup”: “DELETE … WHERE done; VACUUM” in one fell swoop.
If you incorporate partitions into this, the final removal of the soft deleted rows becomes and truncate or a drop instead of a delete.
