How Postgres DELETE can actually scale

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;

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.

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.

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;

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.

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.