Postgres DELETE at scale: foreign keys, cache and dead tuples

DELETE has a bad reputation in Postgres. Many performance-sensitive systems avoid deleting rows and prefer to empty whole tables with TRUNCATE or drop entire partitions by date. Peter Kraft and Qian Li, from DBOS, have published Postgres DELETE Can Actually Scale, explaining why that reputation is deserved and, at the same time, how they got deletes to scale in a system processing tens of thousands of workflows and steps per second.

I liked it because it isn’t a post about tricks, but about understanding what Postgres does underneath. And the two problems they ran into show up in any large table with a retention policy.

Deleting in Postgres isn’t deleting

To understand why DELETE is expensive, you need to remember how MVCC (multi-version concurrency control) works. Postgres doesn’t remove a row when you delete it: it stamps it with the ID of the transaction that deleted it. That way, transactions that started earlier still see it, and later ones ignore it. That’s what lets a delete stay invisible until commit without locking anyone out.

The consequence is that every UPDATE and every DELETE leaves behind a dead tuple, an old version of the row that takes up space until VACUUM (usually autovacuum) cleans it up, once no active transaction can need it any more. At small volumes you don’t notice. When you delete millions of rows a day, those dead tuples interact with the cache and indexes in non-obvious ways.

The case: workflow retention

DBOS is a durable execution engine that stores workflow state in Postgres. Users define a retention policy, such as “delete workflows that finished more than a week ago”, and the system applies it periodically by deleting the N oldest workflows in batches until none are past the cutoff.

The curious part is that deleting the workflows themselves wasn’t the problem. The problem was their associated data in other tables, like step_outputs, where each step of a workflow stores its result.

First problem: ON DELETE CASCADE

The original design was textbook: each row in step_outputs had a foreign key to its workflow in workflow_status, with ON DELETE CASCADE. Delete the workflow and Postgres deletes its steps. Flawless referential integrity.

At scale, performance was awful, and the reason is cache locality. A workflow runs many steps over quite a long time, so its rows in step_outputs end up scattered across the disk, mixed with those of other workflows. Each cascading delete forces an entire page to be loaded into memory, modified and written back, maybe to delete a single row. The result: deleting workflows was much slower than running them.

The fix was to drop the foreign keys and delete from each table separately, in phases:

1. The oldest workflows are deleted in batches from workflow_status, which is fast without the cascade.
2. Similar batch deletes are run on data tables like step_outputs.

Both steps are fast for the same reason: they delete rows in the physical order they were created, so each page loaded into memory contains many rows to delete.

There’s a delicate detail. Workflows are deleted based on when they finished, but the data tables only store when they were created. To avoid deleting the data of a long workflow that’s still running, the delete includes an anti-join: only data whose workflow no longer exists is removed. With a simplified schema, it would look something like this:

DELETE FROM step_outputs s
WHERE s.created_at <= $1  -- batch limit
  AND NOT EXISTS (
    SELECT 1
    FROM workflow_status w
    WHERE w.workflow_id = s.workflow_id
  );

In other words, the integrity the database used to guarantee is now guaranteed by the retention logic itself.

Second problem: a 20-minute index lookup

The new mechanism surfaced a very strange performance bug. Each batch starts with a query that looks up the created_at of the Nth oldest row, to know how far to delete. It has an index on created_at, the query plan uses it correctly and it normally takes no time at all. But sometimes, with the database close to saturation, it took more than 20 minutes.

The cause is MVCC again. The “deleted row” stamp goes on the row, not on the index entries pointing to it. So when a query finds a row through an index, it has to go to the table to check whether it’s still alive.

Normally dead tuples are spread across the index and this doesn’t matter. But here was the worst possible case: the query walks the index from oldest row to newest, and retention deletes precisely the oldest rows. If a batch had just run and autovacuum hadn’t caught up yet, there could be millions of dead tuples right at the start of the index, and the query had to visit each one in the table before reaching the first live row.

The fix was simple once the problem was understood: run a manual VACUUM of the table before and after each retention pass, so dead tuples don’t pile up at the start of the index.

With both changes together, delete performance improved by an order of magnitude.

Why not use partitions

The classic alternative is to partition tables by time and drop old partitions, as queue systems like pgmq or PgQue do. It’s much faster than any DELETE, because it doesn’t go through MVCC: Postgres simply deletes the files from disk.

The problem is rigidity. A partition can’t be dropped until all its data has expired. For a message queue, where each item lives for a predictable time, it works very well. But in a workflow system, a few workflows lasting weeks or months can block the deletion of billions of rows from short workflows. And it doesn’t allow finer retention policies either, like keeping failed workflows longer than successful ones.

My takeaway

This post reminded me of the one on how PostgreSQL estimates your queries: in both cases, understanding performance isn’t just about looking at the query, you need to know how Postgres works inside. Here, on top of that, the query plan was correct: a well-used index can take 20 minutes if what’s behind it is full of dead rows.

And I keep two practical ideas for any table with retention:

• ON DELETE CASCADE is convenient, but it isn’t free. If child rows are created over time and end up scattered across the disk, a cascading delete can be much more expensive than deleting each table separately in creation order.
• If you always delete from the old end of an index, don’t wait for autovacuum. An explicit VACUUM after each pass keeps the next query from having to walk through everything you just deleted.

Partitions are still the best option when data expires uniformly. But when it doesn’t, DELETE can scale well if you take into account how MVCC works.

Source: Postgres DELETE Can Actually Scale, Peter Kraft and Qian Li, DBOS.