Delete Files and the Cost of Merge-on-Read

A single row in a file of five million must be removed. The copy-on-write answer is to read the file, filter out the row, and write a new file of 4,999,999 rows: five million rows read and written to remove one. At a terabyte scale with deletes arriving continuously, the write amplification is the dominant cost of the table, not the query workload.

The merge-on-read answer is to leave the file untouched and record the deletion separately: a small side file naming the rows to suppress. The write is cheap and proportional to the number of deleted rows. The read becomes more expensive, because the reader must now combine a data file with a delete file before it can produce rows. Every format that supports row-level deletes is choosing a point on that curve, and the two families of delete file sit at different points.

Position deletes: naming the row by where it sits

A position delete identifies a row by the pair (data file path, ordinal position within that file). The ordinal is the row’s index in the file’s row order, counted from zero across the file’s row groups, so position 1,204,553 means the 1,204,554th row the file’s writer emitted. Applying it requires no comparison of values and no knowledge of the schema: the reader skips that ordinal and moves on.

This is the cheaper form on both sides. The delete file is tiny: a path, a long, and optionally a row’s worth of values for diagnostics. Applying it is a bitmap or a counter check during the scan, costing a comparison per row and no extra memory if the reader streams. It is also unambiguous: the position identifies one row even if the table has duplicate values, and a re-written data file invalidates the delete (correctly), because the position no longer refers to the same row.

The constraint is that positions are only stable while the data file is stable. Any rewrite of that file, whether compaction, an overwrite, or a schema change that requires rewriting, invalidates every position delete that targets it, and the writer performing the rewrite must apply those deletes itself rather than carry them forward. That requirement is what couples merge-on-read to compaction: a compaction job cannot simply concatenate files if any of them has pending deletes.

Delta Lake’s deletion vectors are the same idea in a different encoding: a bitmap or a set of deleted ordinals attached to a data file, stored alongside the file and referenced from the log. The semantic is positional, so the same invalidation rule applies.

The two kinds of delete file store different things, and the difference explains their costs:

Delete file kind	What each entry stores	How the reader applies it
Position	data file path, ordinal, optionally the row values	membership test on (path, ordinal)
Equality	a tuple of key column values	lookup per scanned row on those columns

Equality deletes: naming the row by value

An equality delete identifies rows by a tuple of column values: “delete every row where customer_id = 4471 AND order_date = DATE '2025-03-27'”. The file stores those value tuples, and the reader must compare each scanned row’s key against the delete set.

The advantage is that the delete survives a rewrite of the data file. If a compaction job rewrites the file and changes row order, the equality delete still applies, because it names values rather than positions. That makes equality deletes composable with concurrent rewrites in a way position deletes are not: the compaction job does not need to know about them, and it can be run by a different process.

The costs are three. The reader must build a lookup structure from the delete tuples, which costs memory proportional to the number of distinct deleted keys and time proportional to one lookup per scanned row. The delete file must be joined to the data files whose key ranges overlap, and the format records bounds on the delete file’s key columns for exactly this reason, so that a scan can determine which delete files could possibly apply. And the delete is not stable under a schema change of the key column: renaming a key column is fine because the delete file records field identifiers, but widening its type requires the delete’s stored values to be promoted too.

A subtle correctness point: equality deletes apply to rows committed before the delete, not to rows committed after. If a new row with customer_id = 4471 arrives after the delete, it must survive. The mechanism is the sequence number: a delete file carries a sequence number, and it applies only to data files with a lower sequence number. Readers that ignore sequence numbers and apply all deletes to all files silently delete newly arrived rows, and the error appears only when a delete and a re-insert of the same key coexist in one snapshot. The sequence number ordering, and its interaction with the commit protocol, is the part of merge-on-read most often implemented incorrectly.

What the reader actually executes

A position delete set is small enough to hold as a set of ordinals per file, so applying it costs one hash lookup per row and no memory proportional to the file:

def scan_with_position_deletes(path, rows, deleted_ordinals):
    # deleted_ordinals: set of ints for this path, loaded from the delete file
    for ordinal, row in enumerate(rows):
        if ordinal in deleted_ordinals:
            continue                      # suppressed by the delete file
        yield row

def scan_with_equality_deletes(rows, deleted_keys, key_columns):
    # deleted_keys: set of tuples, one per deleted key combination
    for row in rows:
        key = tuple(row[c] for c in key_columns)
        if key in deleted_keys:
            continue
        yield row

The second function shows the memory cost directly: deleted_keys must be resident for the duration of the scan, and its size is the number of distinct deleted keys, not the number of deleted rows.

A scan with deletes present becomes a two-phase operation. Phase one plans: for each data file, find the delete files whose sequence number is lower and whose key bounds overlap. Phase two executes: read the data file, apply the applicable deletes, emit surviving rows.

The plan is a join between two sets of file metadata, and its cost is not negligible. A table with 100,000 data files and 5,000 delete files can produce a large number of candidate pairs unless the bounds eliminate most of them. In the position-delete case the delete file names its target path explicitly, so the join is exact and cheap. In the equality case the join is a range overlap test on the key bounds, and its cost grows with the product of the two counts in the worst case.

There is also a cache problem. A reader that applies equality deletes to a data file must hold the delete set in memory for the duration of the file’s scan. For a delete file with a million keys, that is tens of megabytes per concurrent scan, and the memory is not shared between scans unless the engine explicitly shares the lookup. Position deletes avoid this entirely because they can be applied as a streaming filter.

The maintenance obligation

Merge-on-read defers work, and the deferral compounds. Every delete adds a file, and a table that accumulates thousands of small delete files pays for it at read time: more planning, more per-file overhead, more objects for the metadata tree to describe.

The standard response is to rewrite affected files periodically, applying the deletes during the rewrite and dropping the delete files. This is exactly the copy-on-write cost, paid later and in batch rather than per delete. The decision of when to pay it is the same trade as compaction: rewrite when the delete files targeting a data file are numerous enough that the read overhead exceeds the rewrite cost, or when a file’s deleted fraction exceeds a threshold that makes reading it wasteful. Formats and engines expose a per-file deleted-record count precisely so that a job can select candidates without scanning.

Deletes also have to be considered when a snapshot expires. A delete file is referenced by a snapshot; dropping the snapshot drops the reference; but the data file it targeted may still be referenced by a later snapshot. Deleting the delete file while keeping the data file resurrects the deleted rows. This is why the reference counting in snapshot expiry and orphan files must be done over the union of all retained snapshots rather than per snapshot.

Choosing between the two

The choice is not global; it is per table and often per operation.

Situation	Cheaper choice
Few deletes, large files, read-heavy	merge-on-read with position deletes
Continuous delete stream, GDPR-style row removal	merge-on-read, then rewrite on a schedule
Rewrites run concurrently with deletes	equality deletes, or a serialized writer
Small files, deletes frequent	copy-on-write, since files are rewritten anyway
Delete affects most of a file	copy-on-write, since the read is wasted

The pattern in the last row is worth stating plainly: merge-on-read never helps when the delete removes most of a file, because the reader still reads the whole file to discover that nearly all of it is gone. A file that is 90% deleted is a file that should be rewritten, and the format’s per-file deleted count exists to make that decision automatic.

Interactions worth knowing

Deletes and pruning. A delete file’s bounds participate in pruning, but the pruning is over the delete’s key space, not the table’s. A query that filters out the rows a delete would have removed still reads the delete file, because the planner does not reason about predicate implication between the query and the delete. This is a missed optimisation, not a correctness issue.

Deletes and time travel. Reading an older snapshot does not apply deletes committed after it, which is the point. Reading a snapshot at or after the delete applies it. The two are different row sets, and a comparison between them is the only way to see what a delete did, because no delete log is retained separately.

Deletes and the metadata tree. Every delete file is an entry in a manifest, so a table with a high delete rate grows its manifest count faster than its data volume suggests. The manifests that describe delete files can be filtered separately from those describing data files, which is why implementations tag them with a content type rather than mixing them.