First of all, what are you optimizing for? Expiry latency shouldn't matter, only keeping pace with insert throughput. And while I appreciate that you sidestepped the immediate issue through the solutions presented in the article, dropping the foreign key and adding an anti-join doesn't feel like a long-term solution, since you trade referential integrity for orphan risk.

There's a point in PostgreSQL scalability where the need to vacuum (following updates/deletes) becomes a problem in itself, and that point is a lot closer than most anticipate. For instance, vacuum can’t be unable to reclaim versions unexpectedly (e.g stuck transaction holding the TID horizon), leaving you with millions of dead tuples & massive stale index linked-lists, which can lead to major service degradations.

An alternative could be to tombstone rows with a HOT UPDATE on a `deleted_at` column. If that update is HOT (heap-only), the new row version lives on the same page and no new index entries are created. The old version does become a dead tuple, but it's pruned in-page and ad-hoc by ordinary reads and writes, so VACUUM is never needed to reclaim them, and dead tuples never accumulate, least of all in the indexes. On PG16+ this even works with a BRIN index on `deleted_at`, given some fillfactor headroom.

That also addresses the 20-minute scan, which seems to have been caused by walking millions of dead index entries at the oldest end of created_at, each needing a heap visit to confirm it was dead. With HOT tombstoning, those dead entries never get created in the first place. A persisted keyset cursor (the last processed `created_at`) would avoid re-walking that region either way.

The manual VACUUM also couples your business logic to the storage layer, which is a bit of a slippery slope that’ll cause issues when you scale to the next order of magnitude.

I understand why long-running workflows and per-class retention complicate partitions. But if most workflows are short-lived, partitioning plus a tombstone sweep for the long-lived stragglers could avoid most DELETEs, and would also help index sanity, caching.. and let you profit from the many other benefits of partitions.