DBOS explains how Postgres actually deletes rows and how it made workflow retention deletes scale: batched deletes of the oldest workflows, dropping foreign keys so tables are cleaned in phases, debugging a 20-minute index lookup, and why it chose DELETE over dropping partitions.

Postgres DELETE Can Actually Scale

Postgres DELETE has a bad reputation, with many high-performance systems opting to avoid deletes entirely, instead cleaning up data by truncating entire tables or dropping entire partitions. If deletes didn't scale, that would be a shame, because DELETE is far more flexible than dropping partitions or tables, especially when data is heterogeneous and you need to store some items longer than others. The accusations aren't wrong: Postgres DELETE uses a lot of expensive machinery to ensure deletes are transactionally safe, so deleting every row in a table is indeed orders of magnitudes slower than just dropping the table. But DELETE can still scale, especially for workloads that require its flexibility and strong guarantees.

In this blog post, we'll show how with the right optimizations, Postgres DELETE can be used at scale. We'll focus on how we tuned DELETE in a Postgres-backed durable workflows and queues workload, optimizing cache and index performance to apply data retention policies to a system processing tens of thousands of workflows and steps per second.

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.

Diagram - how Postgres executes a DELETE statement

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.

Cascading DELETE SQL statement to delete workflow steps

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.

Diagram - DBOS Workflow and workflow step deletion in Postgres

Dropping Foreign Keys

To fix retention performance, we dropped the foreign keys referencing the workflow_status table and deleted 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.

Benchmark - why Deletions can take much longer than you expect

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?

Before we finish, we want to return to the alternative solution of dropping partitions (or truncating tables) and explain why we aren't using it. To reiterate, some high-performance Postgres-based systems (like pgmq or PgQue) 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. Additionally, a partition-based system cannot support complex retention policies that some users need, 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