Skip to main content

Iceberg V3 in Velox

· 17 min read
Apurva Kumar
Software Engineer @ Meta
Zhenyuan Zhao
Software Engineer @ Meta
Naveen Kumar Mahadevuni
Software Engineer @ IBM
Joe Abraham
Software Engineer @ IBM
Reetika Agrawal
Software Engineer @ IBM
Kevin Gu
Software Engineer @ IBM

Iceberg V3 changes how row-level deletes are stored, gives every row a stable identity, and lets you add a column with a default value without rewriting data. Over the past six months we added most of this to the Velox Iceberg connector. Deletion vectors work on both read and write, including DELETE, UPDATE and MERGE. Row lineage, default values and the new geospatial types work on read, and write defaults work on write.

This post covers how each of those works, and a few places where the implementation was less obvious than the spec made it look.

FeatureReadWrite
Deletion vectorsYesYes
Row lineageYesNo
Default valuesYes (initial-default)Yes (write-default)
geometry, geographyYes (Parquet)No
variant, timestamp_ns, multi-argument transforms, encryptionNoNo

Deletion vectors​

In V2, a row-level delete is a file of (file_path, pos) pairs. Every DELETE, UPDATE or MERGE adds more of these files. To scan one data file, a reader has to open every delete file that might reference it, filter by path, and merge the sorted positions. Until compaction catches up, the cost of reading a table grows with the number of writes to it.

V2 positional delete files compared with a single V3 deletion vector for one data file
V2 positional delete files vs. a V3 deletion vector for one data file.

V3 replaces this with deletion vectors. A deletion vector is a Roaring bitmap of deleted row positions, stored as a deletion-vector-v1 blob inside a Puffin file. The spec allows at most one per data file. The manifest entry records the blob's offset and length, so a reader makes one ranged read and never has to parse the Puffin footer.

Puffin file layout with one deletion-vector-v1 blob and a JSON footer
Puffin file layout. The manifest entry points straight at the blob.

The blob wraps the bitmap in a big-endian length, a 4-byte magic number and a big-endian CRC-32. The bitmap uses the 64-bit portable Roaring format: a group count, then for each group a 32-bit key holding the high bits of the positions, followed by an ordinary 32-bit Roaring bitmap holding the low bits. A data file with fewer than 232 rows has exactly one group, so in practice this is the standard 32-bit format with a 12-byte prefix.

Byte layout of a deletion-vector-v1 blob and its 64-bit Roaring serialization
The deletion-vector-v1 blob and its 64-bit Roaring serialization.

Reading​

The main design question on the read side was where to apply the bitmap. We could have decoded every row and filtered afterwards. But the Parquet and DWRF readers already take a bitmap of rows to skip, and V2 positional deletes were already using it. So DeletionVectorReader keeps the bitmap's containers compressed, the way they are stored, and for each batch sets the bits of the deleted rows in that batch's range straight from them. The file reader then skips those rows while decoding. Our first version expanded every deleted row into a sorted list of 64-bit positions instead. With half of a 1M-row file deleted, that took about 5 ms to load; reading the compressed containers takes about 0.04 ms.

V2 positional deletes write into the same bitmap. A table upgraded from V2 can have old delete files sitting next to new deletion vectors, and it needs no special handling: both feed the same bitmap before the batch is decoded. Equality deletes match on values rather than positions, so they stay on their own path after the read.

Sequence numbers decide which deletes apply to which data files, and the rule differs by delete type. A positional delete or deletion vector applies when its sequence number is greater than or equal to the data file's. An equality delete applies only when its sequence number is strictly greater. That asymmetry is what lets a single commit delete a key with an equality delete and insert it again.

We check the length, magic number and CRC before trusting a bitmap, and that each container is well formed. For example, array values must be in increasing order, because each batch binary-searches them. If a deletion vector is corrupt, the query should fail. It should not return rows that were deleted.

We went back and forth on one case. When a blob's referenced-data-file doesn't match the path of the split being read, we log a warning and apply the deletes anyway. Engines and catalogs don't all normalize paths the same way. The manifest has already told us which data file this deletion vector belongs to, and failing the query or dropping the deletes would both be worse than trusting it.

Read path: sequence-number filter, delete readers, shared delete bitmap, file reader, post-read steps
How deletes are applied in IcebergSplitReader.

Writing​

The write side is harder because of the one-per-file rule. If a data file already has a deletion vector, a new delete can't add a second one; it has to replace it. IcebergDeletionVectorSink reads the existing deletion vector, adds the new positions to it, and writes a new Puffin file next to the data file. The commit message carries the referenced data file, the blob's offset and length, the number of deleted rows (after removing duplicates: Iceberg treats a deletion vector's cardinality as authoritative, and merging in the old vector can repeat positions), and the data file's partition spec and partition data. The coordinator then commits the new deletion vector in place of the old one.

To build a deletion vector, the sink needs to know which file each deleted row came from and where in that file it was. The scan adds a hidden $target_table_row_id column, ROW(file_path, row_position, spec_id, partition_data), in the same shape the Presto Java connector uses. We got the partition fields wrong twice, and both times the coordinator rejected the commit on a partitioned table. First, the MERGE path copied only the file path and position out of the row ID, which dropped the partition data. Second, the sink stamped every deletion vector with the table's current spec ID, which is wrong for a data file written before the spec evolved. The row ID is now passed through unchanged, and each deletion vector is committed under its data file's own spec.

UPDATE and MERGE follow the same model as Presto's DeleteAndInsertMergeProcessor. IcebergMergeProcessor turns each input row into an insert, a delete, or both, since an UPDATE is a delete of the old row plus an insert of the new one. IcebergMergeSink sends deletes to the deletion vector sink and inserts to the normal data sink. It then returns both sets of commit messages together, so new data files and new deletion vectors land in the same snapshot. Because an UPDATE produces two rows, the changed-row count has to count it only once. We got that wrong the first time too.

DELETE, UPDATE and MERGE write path through IcebergMergeProcessor and IcebergMergeSink
The DELETE, UPDATE and MERGE write path.

Matching Iceberg Java​

Most of the time we spent on the writer went into matching Iceberg Java byte for byte, since in practice it is the reference implementation. Some examples:

  • Our first CRC used folly::crc32, which skips the final inversion that standard CRC-32 applies. Because the reader and writer used the same function, Velox-to-Velox round trips passed, and the bug only showed up when we read a deletion vector written by Spark. We now use zlib's crc32, which matches java.util.zip.CRC32.
  • Java's RoaringPositionBitmap stores the high 32-bit key as a signed int and caps it at Integer.MAX_VALUE - 1. We reject larger positions at write time so we never write a file Java can't read, and the reader enforces the same cap. Without it, a key of 231 or more would shift into the sign bit and produce a negative row position.
  • Java has no "none" compression codec, so for an uncompressed blob the Puffin footer has to leave out compression-codec entirely.
  • We write only array and bitmap containers, never run containers. The reader accepts all three, because other writers may use runs.
  • We check this in CI. Eleven deletion vectors written by Iceberg Java 1.10 are checked in as test files, along with what Iceberg Java decodes from each, plus one bitmap in the older 32-bit format. They include run containers and positions on both sides of the 232 boundary, and the reader has to decode every one to exactly the same positions.

Row lineage​

V3 gives every row a _row_id and a _last_updated_sequence_number. Writers don't have to store them. When the stored value is null, the reader works it out: _row_id is the data file's first_row_id plus the row's position in the file, and _last_updated_sequence_number is the file's data sequence number. A stored non-null value always wins, which is how a row keeps its identity after compaction rewrites it. If the manifest entry has no first_row_id, which is the case for files written before the upgrade to V3, both columns read as null.

The easy mistake is in "position in the file." Once a deletion vector removes rows, a row's index in the output batch is no longer its position in the file. Computing _row_id from the output index gives wrong IDs without any error. So whenever lineage columns are projected, the reader adds a hidden row-number column and computes _row_id from that.

Worked example of row lineage inheritance with one row removed by a deletion vector
Lineage for one data file, with position 1 removed by a deletion vector.

Filters on lineage columns can't be pushed into the file reader, because it would evaluate them against the stored nulls. We turn off pushdown for those columns and apply the filter after the values have been filled in.

Default values​

initial-default and write-default let you add a column with a default value without rewriting the table. On read, a column that is missing from an older file gets its initial-default instead of null, and filters on that column still prune correctly. On write, if an INSERT leaves out a column that has a write-default, IcebergDataSink fills in the default.

The write path has one guard worth mentioning. The sink only fills in a default when the column was actually left out of the INSERT, and it checks that every value it is about to replace is null. If the planner ever wrongly marks a column as omitted, the query fails rather than overwriting user data. Timestamp defaults are parsed as UTC, not session-local time. That was another bug we fixed along the way.

Geospatial types​

V3 adds geometry and geography, stored as WKB. With VELOX_ENABLE_GEO on, the connector reads Parquet GEOMETRY and GEOGRAPHY columns into Velox's GEOMETRY and SPHERICAL_GEOGRAPHY types. The conversion happens in exactly one place, the Iceberg connector. The Parquet reader returns plain VARBINARY, and Hive tables never go through the conversion. That keeps WKB parsing out of the generic readers and makes it impossible to convert the same value twice.

Before converting, we validate the WKB. We reject EWKB, Z and M coordinates, truncated input, and nesting deeper than 100 levels. The GEOS version Velox pins (3.10.7) doesn't limit recursion depth (newer releases do), so without that check a crafted file could overflow the stack. Geography coordinates must fall within [-180, 180] × [-90, 90], the same rule Presto's to_spherical_geography applies. Velox and Presto Java share a golden file of encoded geometries, so the two runtimes produce identical bytes.

Writing these types is rejected for now. Velox's internal encoding isn't WKB, and writing it as-is would produce files no other engine can read.

Benchmark​

We ran a Velox micro-benchmark comparing deletion vectors with V2 positional deletes. It reads every row of one 1M-row, single-column DWRF file on local disk. The same deleted rows are stored three ways: one positional delete file, ten positional delete files, or one deletion vector. Each case ran five times, each time in its own process pinned to one core, and the times below are the medians. Reading the file with no deletes takes 19.6 ms.

Read time1 positional file10 positional filesDeletion vector
1% deleted22.8 ms23.4 ms22.9 ms
5% deleted24.0 ms24.7 ms23.8 ms
20% deleted27.1 ms27.6 ms26.0 ms
50% deleted29.4 ms29.9 ms26.8 ms
Line chart of read time against rows deleted for one positional delete file, ten positional delete files and one deletion vector, with a no-deletes reference line at 19.6 ms
Read time as the share of deleted rows grows.

At 1% and 5% deleted, the deletion vector and one positional delete file were within 1% of each other. From there the deletion vector was faster: about 4% at 20% deleted and 9% at 50%. Ten positional delete files were about 2-3% slower than one at every rate.

Most of the time deletes add to the scan goes into handling the deleted rows, not into loading the deletes. Measured on its own, loading and applying the deletion vector takes about 0.03 ms at 1% deleted and 0.6 ms at 50%. A positional delete file has to be read and decoded like a small data file, and it grows with every deleted row.

Delete file size1 positional file10 positional filesDeletion vector
1% deleted30 KB39 KB20 KB
5% deleted144 KB157 KB100 KB
20% deleted524 KB597 KB130 KB
50% deleted1,237 KB1,442 KB131 KB
Line chart of delete file size against rows deleted: positional delete files grow to 1,237 and 1,442 KB while the deletion vector levels off near 131 KB
Delete file size as the share of deleted rows grows.

Deletion vectors were smaller at every rate, and the gap widens as more rows are deleted. At 50% deleted, the deletion vector was 131 KB against 1,237 KB for one positional delete file, about 9× smaller. It stops growing near 131 KB because a 1M-row file spans 16 blocks of 64K rows, and a block with many deletes is stored as an 8 KB bitmap however many of its rows are deleted.

These are local files, so the benchmark doesn't capture the cost of opening many small V2 delete files on remote storage, which is where accumulated deletes hurt most.

Compared with Iceberg Java​

Since the bytes are the same on both sides, we can also compare Velox with Iceberg Java 1.10 directly. We wrote the deletion vectors with Iceberg Java's BitmapPositionDeleteIndex and checked that Velox writes byte-identical ones for the same rows. Then, on the same machine, we timed loading one deletion vector and checking every row of the 1M-row file against it. Each implementation ran five times in its own process pinned to one core, on JDK 21 for Java, and the times below are the medians.

Iceberg Java can apply a deletion vector in two ways. Its forEach walks the deleted positions once, which is the closest match to what Velox does. isDeleted looks up one row at a time.

Load and applyVeloxIceberg Java, forEachIceberg Java, isDeleted
1% deleted30 µs131 µs20.1 ms
5% deleted99 µs204 µs25.3 ms
20% deleted288 µs582 µs13.6 ms
50% deleted600 µs829 µs18.0 ms
Bar chart of the time to load and apply one deletion vector in Velox and in Iceberg Java's forEach path at 1%, 5%, 20% and 50% of rows deleted
Loading and applying the same deletion vector in Velox and Iceberg Java.

Velox was 1.4 to 4.3 times faster than Iceberg Java's forEach path, and the gap is widest at low delete rates, where loading dominates. Velox checks the blob and indexes its containers without building an in-memory bitmap, which took 15 µs at 1% deleted, against 110 µs for Iceberg Java to read the blob and build its bitmap. These numbers cover the deletion vector alone: in the Velox scan above, loading and applying it is about 2% of the read time at 50% deleted.

Building a deletion vector is the other half. For each data file that a DELETE, UPDATE or MERGE touches, the sink collects the deleted positions, serializes them, and counts the distinct positions for the commit message. For the first deletion vector of a data file the positions come from a scan in order, so the writer skips sorting and writes each Roaring container straight from its run of positions. When the data file already has a deletion vector, the sink seeds the writer with the old positions and then adds the new ones. The writer keeps track of the sorted prefix, sorts only the new positions, merges them in place, and reuses the result for the count.

We timed both cases the same way as above, with the same rows on both sides. For the merge case, every tenth deleted row is new.

Build and serializeFirst deletion vector: VeloxIceberg JavaMerging into an existing one: VeloxIceberg Java
1% deleted43 µs237 µs50 µs371 µs
5% deleted214 µs675 µs253 µs1.07 ms
20% deleted1.00 ms1.73 ms1.17 ms2.02 ms
50% deleted2.43 ms4.20 ms2.82 ms4.33 ms
Two bar charts of the time to build and serialize one deletion vector in Velox and Iceberg Java at 1%, 5%, 20% and 50% of rows deleted: on the left the first deletion vector for a data file, on the right merging into an existing deletion vector; Velox is faster in every case
Building and serializing the same deletion vector in Velox and Iceberg Java.

Velox was 1.7 to 5.5 times faster for the first deletion vector and 1.5 to 7.4 times faster when merging. Iceberg Java adds each position straight into its bitmap, so the order doesn't matter to it. New deletes that reach Velox in random order pay for a sort of the new positions, and there Velox is behind from 20% deleted up: 15.8 ms against 12.3 ms at 20%, and 41.5 ms against 20.4 ms at 50%. Building containers as positions arrive, the way Iceberg Java does, is the next thing to try. Iceberg Java's times also cover the blob's length, magic number and CRC, which take about 0.01 ms for a 131 KB bitmap, so they don't change the comparison.

What's left​

Several parts of V3 aren't in Velox yet: the variant type, nanosecond timestamps (timestamp_ns and timestamptz_ns), multi-argument transforms and source-ids in partition specs, table encryption, and writing lineage columns and geospatial types.

Thanks​

This work was done by Apurva Kumar, Zhenyuan Zhao, Naveen Kumar Mahadevuni, Joe Abraham, Reetika Agrawal, Kevin Gu. Thanks also to the Iceberg community.