tl;dr

A table format compaction rewrites data files in a more efficient layout. Even though the layout change makes no logical changes to the table, concurrent transactions that refer to the old layout often need to be re-executed because the objects they reference don’t exist in the new layout. A compaction map is a compact data structure that repairs the conflict by remapping references from the old layout to the new one, without re-executing anything. Remapping conflicts takes tens or hundreds of milliseconds (v3) or ~2 seconds (v2) instead of minutes to re-run the compaction or transaction.

Compaction maps were presented in the FORMATS workshop at ACM SIGMOD/PODS 2026 last May. This is an overview of the problem and solution, but… c’mon, the paper is only 4 pages. The implementation is here based on Apache Iceberg 1.10.1 and works on v2 and v3 tables.

Layout Conflicts

If you’re already familiar with compaction and the issues it causes in production workloads, feel free to skip this section.

Table formats store direct references between objects in the underlying store. To reduce write amplification, most formats allow updates to patch existing snapshots by writing only what changed as delta updates: rows inserted and rows deleted from existing objects in the table. Readers merge deltas against a checkpoint to compute the snapshot state:

In formats like Apache Iceberg, a position delete vector tombstones rows in a particular object by logical position¹. For example, if a transaction \(T_i\) updates rows stored in s3://.../base.parquet, \(T_i\) would write a position delete vector referencing base.parquet and a new object delta-i.parquet with the new rows. A subsequent transaction \(T_j\) that updates an overlapping set of rows would write position delete vectors for both base.parquet and delta-i.parquet alongside a new object delta-j.parquet. Saliently, updates depend not only on the state of the table, but also its layout; transactions reference specific objects and offsets.

In Iceberg, v2 tables encode position delete vectors as Apache Parquet files, while v3 tables encode them as Roaring bitmaps in the Puffin format. The two formats have different performance characteristics, but the underlying problem is the same: a layout change invalidates references to objects in the old layout.

Delta commits impose merge costs to readers, increasing query latency by up to 2-3x. To avoid this overhead, table formats periodically compact the layout of a table by merging all the live rows into a new set of objects. Logically, compaction is a noop transaction that reorganizes the rows in a table, but compaction conflicts with concurrent transactions that refer to the old layout. Concurrent transactions’ delta commits refer to the same rows in the table, but the referents of the position delete vectors don’t exist in the new layout. Symmetrically, transactions that committed while the compaction was running can invalidate its result: the transaction’s deletion vectors refer to objects the compaction elided from its prepared snapshot, so the compaction cannot be a successor to the transaction.

The solution for most layout conflicts is to re-execute, repeating the same work over the same data. Failed compactions accumulate a backlog under sustained writes, pushing operators toward smaller and more frequent compactions. Each compaction is a new commit that conflicts with concurrent transactions, making simple workloads with SLOs difficult to tune: even a single writer loading data to the table can be interrupted by a compaction, causing it to miss an SLO. The tension between necessary maintenance and workload tuning is a real problem in production tables.

Compaction Maps

Instead of re-executing compactions/transactions, we can repair layout conflicts by remapping references from the old layout to the new layout. This is sound, because the compaction is a logical noop that preserves all live rows from a snapshot; any successor transaction executed against the old layout depends on a subset of the data that compaction preserves. Whether the transaction or the compaction commits first, our task is to rebase transaction changes on top of the compacted layout to create a new successor that preserves the same logical state.

It’s inexpensive to rebase delta updates. Newly inserted rows are unchanged; only the (compressed) position delete vectors reference the old layout. So if we can locate the tombstoned rows, then we can rewrite the position delete vector to refer to the new layout, making it a valid successor to the compaction. The compaction effects the mapping between layouts, but doesn’t record it. A compaction map is that record: parameters for remapping functions to map positions from the old layout to the new layout.

As in the figure, rebasing a transaction or compaction is symmetric. If the compaction commits first, then the transaction can correct its position delete vector using the committed compaction map. If the transaction commits first, then the compaction can use the compaction map to rewrite the committed position delete vector to refer to the compaction’s new layout of the older snapshots. Either way, the transaction’s position delete vector is rewritten.

A compaction can rebase more than one transaction onto its new layout. Logically, compaction is the identity operation on a past table state, so rebasing a sequence of transactions conflicting with a new layout of that state is valid. Similarly, transactions can commute with a chain of compactions, and the compaction implementation will “carry” remappings forward to avoid dependencies between compaction maps. Genuine conflicts with other transactions still need to be resolved by the transaction engine.

Implementation

Following Iceberg conventions, our prototype compaction map is encoded as an Apache Avro file. Compactions usually move long runs of rows², so maps require very little state to describe most remapping functions.

As in the figure, rebasing a position delete vector is straightforward. The compaction map stores the region- a run- relocated from the source layout to its new location(s). The row’s position within the run is preserved in the compaction, so the new position can be calculated as tgt_start + (pos - src_start). The map is compact; in the evaluation it requires 2.6KiB for 10 runs and 8.9KiB for 10,000 runs.

When the compaction commits, it stores a reference to the map in the manifest list. This also serves as a flag for SERIALIZABLE transactions, which can ignore read conflicts introduced by a compaction, since the compaction didn’t change the logical snapshot.

Remapping Strategy

The number of runs \(r\) (relocated intervals) and positions \(p\) varies, so a policy selects an appropriate algorithm based on what it encounters at runtime³. After filtering out irrelevant runs, positions are remapped either by looking up the relevant range or, when the map has many runs, by merging the sorted positions against the runs in one pass. Merging wins when runs vastly outnumber positions, and again when both counts are large and the map is dense; range lookup wins on sparse maps, and whenever the run count is small even for millions of positions.

Employing a strategy yields impressive-sounding, orders-of-magnitude speedups over naive/static strategies, but in practice the difference is rarely significant. As we’ll see next, the remapping latency is usually dominated by I/O, not the remapping algorithm.

Evaluation

There are more details in the workshop paper, but the bottom line is that remapping is very cheap. The following heatmaps show the total latency (in ms) remapping \(p\) positions with \(r\) runs in a compaction map, for both v3 and v2 tables.⁴

At the largest values we measured, the mean total latency to read, remap, and write a v3 position delete vector from storage is 293-463ms, depending on the cloud provider. Compare this to minutes to re-execute the compaction or transaction.

Zooming into the top-right cell of the heatmaps: on 1M positions and 10k runs, the remapping latency across providers and v2 (Parquet) and v3 (Roaring bitmap) tables is shown below. Writing a v2 position delete file is more expensive than writing a v3 position delete vector (most of the cost is encoding and writing the Parquet file), but the remapping latency is still orders of magnitude faster than re-executing the transaction.

Related and Future Work

Compaction is not the only layout change that should commute with (at least some) transactions. Deduplication, clustering (Apache Hudi), and mostly-sorted tables would benefit from a similar approach.

Merge Indexes

Compaction maps were inspired by the REMIX index for LSM trees. REMIX indexes record the path taken through SSTables in an LSM tree, so instead of each reader repeating the exact same comparisons to effect a merge over immutable data, readers can use the index to swap between iterators.

REMIX indexes also include “anchor keys” to initialize iterators and seek into the merge state. If the table is sorted, adding anchor keys to a compaction map would serve a similar purpose: recording the path a reader takes when scanning \(d^+\) through a table update. Because a compaction doesn’t reclaim any storage until the old checkpoint is garbage-collected, building the map instead of performing the compaction might recover some read performance at a fraction of the storage cost.

Deduplication and Mostly-Sorted Tables

In many deployments, recently-written rows contain duplicates. Periodically, rows are deduplicated and written back to the table. Deduplication is not a logical noop- it removes rows, where a compaction preserves all of them- but for transactions insensitive to duplicates the shape of the problem is the same: a maintenance operation invalidating concurrent work it doesn’t logically conflict with. A similar dedup map could repair conflicts and allow these transactions to commute with the deduplication operation.

If a table is only unsorted in its most recent data, the map stays a manageable size, and re-sorting could commute the same way. We did not experiment with z-order or re-sorting compactions: in the worst case the map includes an entry for each row, and re-execution on the compacted data is sometimes cheaper anyway- that being the motivation for the compaction in the first place. Anecdotally full reorderings are uncommon, but without workload data the evaluation would be science fiction.

Clustering in Apache Hudi

Apache Hudi doesn’t use position delete vectors and its compactions don’t create layout conflicts. However, it does cluster records by key into file groups. A reclustering operation is a layout change that- redistributing keys across groups- conflicts with concurrent transactions in a similar way. It’s possible that a similar approach, recording metadata with the reclustering operation, could be used to rebase concurrent transactions onto the new layout.

Conclusion

Layout conflicts are a real problem in production workloads, despite being logical noops. Compaction maps can repair these conflicts without re-executing transactions, reducing the latency of conflict resolution from minutes to milliseconds.

Thanks

This was the first meeting of the FORMATS workshop and it was excellent. Thanks to the FORMATS organizers for creating a venue for academic and industry researchers to share work in this space.

Thanks also to Sagar Sumit for his insight on the application of compaction maps to re-clustering in Apache Hudi. Thanks to Owen O’Malley for the deduplication example.