We’re building a durable execution library that checkpoints workflow state to Postgres. Naturally, users want that state to eventually be deleted.

Intuitively, one might think deleting data is cheap. But for Postgres, that assumption is completely wrong, and we found that at large scale, deleting old workflows could actually be slower than executing them. The root cause is one of Postgres's most important, yet infamous, features: multi-version concurrency control (MVCC).

In this blog post, we’ll discuss how deletions in Postgres actually work, how they interact with Postgres’s indexes and buffer cache, and how to make them scale in the context of a Postgres-backed workflows and queues system.

How Postgres Deletes a Row

To understand why deletes in Postgres are so costly, we have to understand how they work. When you delete a row in Postgres, the database doesn’t physically delete the row. That’s because Postgres needs to provide isolation between database transactions: if your transaction deletes a row, that deletion shouldn’t be visible until you commit. If Postgres deleted rows directly, those deletions would be visible to other transactions immediately (bar expensive locking), violating isolation.

Instead, Postgres implements multi-version concurrency control (MVCC). Each time a row is updated, Postgres inserts a new version of the row containing the updated data into your table and indexes. Each version is stamped with the transaction ID of the transaction that created it and the ID of the transaction that superseded it. When you delete a row, Postgres stamps its final version with your transaction ID, making the row invisible to later transactions. This design provides transaction isolation: updates made by a transaction are not visible until the transaction commits, and long-running transactions can access old versions to view a consistent “snapshot” of data.

One consequence of MVCC is churn. Each update and delete creates a “dead tuple,” an old version of a row, which Postgres must, at some point, actually delete to reclaim disk space. Postgres cleans up dead tuples through the VACUUM operation (periodically run by the autovacuum), which finds and removes all dead tuples that are no longer visible to any active transaction. When building a durable execution system that must regularly delete the data of millions of workflows and their steps, this MVCC churn interacts in subtle ways with Postgres caching and indexes to make deletes more costly than they appear.

Struggling with Locality

Workflow deletions typically follow a retention policy: the user sets a policy (such as “delete all workflows that completed more than one week ago”) and the workflow engine enforces it by periodically deleting all workflows that have aged out. The DELETEs are issued in batches of size N, where we repeatedly delete the N oldest workflows until no remaining workflows are older than the retention cutoff.

Interestingly, the performance challenge isn’t deleting the workflows themselves, but deleting the data associated with them in other tables. For example, workflows typically comprise several steps, which write their output to a separate step_outputs table. To keep step data in sync with workflow data, we originally used a foreign key: each row in step_outputs referenced its workflow’s row in workflow_status with ON DELETE CASCADE so deleting a workflow automatically deleted its steps too.

This is textbook design that makes sense from a data integrity perspective: a workflow’s steps should be deleted along with the workflow. But at scale, its performance is awful. The reason is cache locality. Each time a workflow was deleted, Postgres had to find each of its steps and delete them too. Because a workflow typically performs many steps over a long period of time, those step records are widely separated on disk, so each step deletion requires an entire page to be fetched from disk into memory, updated, then written back to disk. This cache churn meant it was far slower to delete workflows than it was to execute them.

Dropping Foreign Keys

To fix retention performance, we had to do what any database textbook would call heresy: drop the foreign keys referencing the workflow_status table and delete data from each table separately. 

With the foreign keys gone, retention proceeds in phases. First, we delete the workflow rows as before. Without foreign keys to cascade to, this is fast. Then, we perform similar batch deletes on tables storing workflow data, like step_outputs. These batch deletes are fast for the same reason the batch delete of workflow_status is fast: they delete rows in their physical creation order, so cache locality is high.

One wrinkle in this design is that workflows are deleted based on their completion time, but the data tables only store creation time.  To guard against deleting data associated with a still-active, long-running workflow, we include an anti-join in the batch delete, only deleting data whose associated workflow is already deleted.

Debugging a 20-Minute Index Lookup

While this new deletion mechanism made sense in theory, when implementing it we encountered a truly bizarre performance bug: an index lookup taking 20 minutes. The issue was in the first query in the batch delete, which finds the created_at timestamp of the batch_size-th oldest row in the table. This query is correctly backed by an index on created_at, so it should be fast. And usually, it was fast. But sometimes, on a database near saturation, its performance collapsed and this innocuous query took upwards of 20 minutes to complete, even with a query plan correctly using its index.

The issue with this query’s performance turned out to be related to how Postgres MVCC performs deletions. To delete a row, Postgres stamps it with the transaction ID of the transaction that deleted it. That way, later transactions know to ignore it, and autovacuum can clean it up. However, this stamp is applied only to the row itself, not to any indexes referencing the row. This means that a query trying to find a row via index must check the row itself (not just its index entry) to confirm the row is not dead.

Ordinarily, this is not a problem because dead tuples are evenly distributed across an index. But this particular SELECT query encountered a worst-case scenario. To find the batch_size-th oldest row in the table, the query walks the created_at index from oldest to newest. Normally, this completes in O(batch_size) time, which is plenty fast. However, the problem is that rows are deleted from oldest to newest. So if another deletion recently ran, and autovacuum hadn’t caught up, there could be potentially millions of dead tuples at the front of the index, and the query has to fetch and check each of them to confirm they’re dead before proceeding. These millions and millions of dead tuple checks caused the query to blow up and take 20 minutes.

Luckily, once we knew what was happening, it was easy to fix: we inserted a manual table VACUUM before and after each retention pass. This way, dead tuples are cleaned up before they can stall future retention periods. By improving cache locality and avoiding pathological index scans, the combination of manual VACUUM and removing foreign keys improved deletion performance by an order of magnitude.

Why Not Partitions?

This post wouldn’t be complete without touching on an alternative deletion strategy we decided not to adopt: table partitioning. Some high-performance Postgres-based systems avoid deletion entirely by partitioning data tables by time and dropping old partitions once their data is no longer needed. This is much faster than SQL DELETEs because it doesn’t go through MVCC at all, Postgres literally deletes the files on disk containing the old data.

The issue with partitioning is that it’s inflexible. 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. A handful of long-running workflows that last weeks or months can block the deletion of billions of rows belonging to shorter-lived workflows. Similarly, a partition-based system cannot support complex retention policies such as retaining different classes of workflows for different periods of time or retaining failed workflows longer than successful workflows.

Learn More

If you like building scalable, reliable systems, we’d love to hear from you. At DBOS, our goal is to make Postgres-backed durable execution as simple and performant as possible. Check it out:

• Quickstart: https://docs.dbos.dev/quickstart 
• GitHub: https://github.com/dbos-inc
• Discord community: https://discord.gg/eMUHrvbu67