Another idea that might conceivably be useful to you on 9.6 is to
reorganize the bulk deletions so that most of them aren't at the endpoint of the live id range. If you made it so that the extremal values are deleted last, you'd never hit this behavior.
regards, tom lane
Hm, I am not sure I understood your suggestion. We'd still need to find a range of ids to delete, and the order by asc has the nice property that it moves old records first, which helps tables with a lot of activity on recently created tuples (and I suppose an ordering in the other direction would suffer from the same problem).