How Postgres DELETE can actually scale (dbos.dev)

MVCC doesn't have to work the way Postgres does it. In some other databases a write like a DELETE or UPDTE directly overwrites disk blocks in place. There are no row copies or vacuums. To provide MVCC the database generates "undo logs" which are what they sound like - if you need to read the database at an earlier snapshot it reads the data off disk then use the undo data to revert the writes that happened after your MVCC snapshot. Undo data is periodically dropped when no live transaction needs it anymore.

There are patches to change Postgres to this kind of model, as it has many advantages - all the outages and problems caused by autovacuuming falling behind go away - but the patches were never merged.

Oracle has a couple of related features:

- undo data can be retained and used for time travel queries (SELECT .. AS OF).

- DML can be parallelized and write masters scale horizontally, so a large DELETE can run on multiple machines simultaneously. You do need to opt in manually though:

    ALTER SESSION ENABLE PARALLEL DML;

    DELETE /*+ PARALLEL(t, 8) */
    FROM   t
    WHERE  created_at < :cutoff;

    COMMIT;

https://docs.oracle.com/en/database/oracle/oracle-database/2...

That said the issues discussed in the blog post aren't directly to do with how fast the DELETE itself is processed but what it does to the database's performance afterwards.

Disclosure: I have a part time role in the Oracle DB group.

> A partition can’t be deleted until every single piece of data it stores is no longer needed. This is appropriate for some systems, like message queues, where data is needed for a predictable amount of time. However, it’s not appropriate for a workflow system that supports long-running workflows.

If most workflows complete within a few days, we could explicitly copy the long running items forward and then reclaim the entire partition. Sacrificing an extremely good technical solution because we can't be bothered to normalize <1% of use cases seems quite hasty, especially when we consider where this rejection of technological simplicity often takes us.

> Because a workflow typically performs many steps over a long period of time, those step records are widely separated on disk

Clustered indices would be so, so nice for Postgres to have. OrioleDB can’t come quickly enough.

> However, this stamp is applied only to the row itself, not to any indexes referencing the row.

Indices also hold the hint bit LP_DEAD, which is set by any query that follows the index to the heap and finds that it’s invisible to everyone.

I suspect that a combined query that uses pagination rather than LIMIT … OFFSET would be more performant here, and could skip the dead tuple problem.

    DELETE FROM step_outputs
    WHERE ctid = ANY(ARRAY(
        SELECT s.ctid
        FROM step_outputs s
        WHERE (s.created_at, s.id) > (?, ?)
            AND s.created_at < ?
            AND NOT EXISTS (
                SELECT 1 FROM workflow_status w
                WHERE w.workflow_uuid = s.workflow_uuid
            )
        ORDER BY s.created_at, s.id
        LIMIT ?
        ))
   RETURNING created_at, id;

Haven’t tested that, but something of that shape. You’d need a composite index on (created_at, id) as well.

Extreme scale and indexes are not at all a happy couple.

Doing away with database-managed indexes at scale makes for simpler queries and predictable latencies now and in the future. These indexes have costs associated with them which become detrimental as scale rises.

Application-managed indexes along with the required codebase discipline results in reduced bottlenecks, minimal latencies, and better parallelism. One can even parallelize the index-fetch phase itself, not to mention all the other goodies that come with it. This results in a different trade-off as cost moves to the application where it is controlled and therefore leveraged.

Note: I am talking generic database architecture and not just about Postgres.

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.

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).