Comment by hinkley

Deleting from a database is a sucker's bet. If you add to a record and mark it dead there are fewer semantic problems to deal with.

Partial indexes give you approximately the same speedup as deletes.