The index problem is interesting, maybe indexes should be updated synchronously at DELETE time? Guess there's architectural reason why postgres can't do that. I'd try to do it manually, by adding "deleted" column to both table and index whether it's performant(edit: that copies whole row so not likely).