Proposal: Introduce deletion vector file to reduce write amplification

Motivation

Deletion vector is a commonly used technique to reduce write amplification in columnar storage. This idea is quite simple: we associate each data file with a deletion vector file, and during updates of data files, we don’t need to rewrite the whole data file, just the deletion vector file.

Let’s use the update sql as an example. In the following case, we need to rewrite whole data files, which introduces 249MB write io.

After introducing a deletion vector file, the write io can be reduced to 1M for each rewrite.

Design

Deletion Vector

Essentially the deletion vector is a set of row indices encoded in a bitmap used to mark deleted rows in a data file. It needs to provide two operations for efficient reading/writing:

1. The reader can be initialized with a starting position, and  returns an iterator of boolean values.
2. The writer should accept an iterator of boolean values as input.^[a][b]

With the required operations above, we have several choices of file format for deletion vectors:

1. A normal file with only one boolean column. Columnar formats like parquet, orc have support for boolean data types and can encode them efficiently.
2. Using roaring bitmap[1]. Roaring bitmap has been well known for being able to encode bitmap efficiently and widely used in many projects^[c], also it has predefined file format.  I have no data about the compression ratio compared with parquet boolean file^[d][e][f][g], but one disadvantage is that it’s not a normal data file like others, and requires introducing an extra concept to the iceberg.

Changes to spec

Since each deletion vector is associated with one data file, we propose to extend DataFile struct an optional deletion_vector_file field:

And the definition of DeletionVectorFile type:

Changes to operations

Read

As a basic implementation, when reading a data file, we will also open the deletion vector file to read the bitmap. This is similar to zip two iterators to filter deleted records. Compute engines are free to make optimization on this. For example, vectorized query engine could read a batch of bits and use it as selection vector of record batch.

Write^[h][i][j][k]

The example in Motivation part shows the process of doing an update when there is no deletion vector file associated with the data file. When there is already a deletion vector file associated, we will merge two deletion vector files. Following diagram shows the write process^[l][m][n][o]:

Delete

Let’s say we have a table with following schema:

```sql

CREATE TABLE IF NOT EXISTS s1.t1

        (

            id long,

            v_int int,

            v_double double,

            v_varchar string

        ) USING iceberg TBLPROPERTIES (

            'format-version'='2',

            'write.delete.mode' = 'merge-on-read',

            'write.update.mode' = 'merge-on-read',

            'write.merge.mode' = 'merge-on-read'

            );

```

And we execute sql:

```

DELETE FROM s1.t1 WHERE id > 1

```

We can see that the physical plan is quite similar to deletion with position deletes. The Sort is optional and depends on the number of affected data files for each writer task. Without sort, we need to buffer all deletes in memory before writing.

Update

Let’s say we have a table with following schema:

```sql

CREATE TABLE IF NOT EXISTS s1.t1

        (

            id long,

            v_int int,

            v_double double,

            v_varchar string

        ) USING iceberg TBLPROPERTIES (

            'format-version'='2',

            'write.delete.mode' = 'merge-on-read',

            'write.update.mode' = 'merge-on-read',

            'write.merge.mode' = 'merge-on-read'

            );

```

And we execute sql:

```

UPDATE s1.t1 SET v_int = v_int + 1 WHERE id > 1

```

Backward Compatibility

This proposal doesn’t break any existing spec, only adds a new kind of row level deletion file.

Deprecation

When deletion vector file added, we should deprecated usage of position delete file. Equality deletion file is still useful in streaming writes such as flink, but we should introduce more frequent minor compaction to rewrite equality deletion file as much as possible  for better reading performance.

Comparison with Position Deletes

Though it looks quite similar to existing position delete files, there are some differences:

1. It has no file_path column, but only a bitmap.
2. The mapping from data_file to deletion_vector_file is 1:1 (or 1: N, maybe we can have one deletion_vector_file per row group to further reduce write amplification). While the mapping from data_file to position_delete_file is N:M.^[p][q]

The differences brings some advantages for deletion_vector_file:

More flexible encoding format^[r][s].

For example we can use a roaring bitmap for better compression.

Better Planning Performance

Since a deletion_vector_file  is always associated with a data_file, we can ignore them during planning phase, since the result is always same as data_file.^[t][u]

Better read performance

Following diagram shows the read process with position deletion file:

1. We need to merge several position deletion files to build in memory bitmap for filtering.^{[v][w][x][y][z][aa]}
2. Then we can data_file to do filtering.

While with deletion vector file, we don’t need to merge several files before reading, just build selection vector[2] during scan:

This is benefited from the 1:1 relationship between  data_file and deletion_vector_file.

Easier to maintain statistics of each data_file

To avoid confusion, by statistics^{[ab][ac][ad][ae]} I mean things such as null_count, nan_count in manifest entry. To maintain statistics of pos_deletion_file, we need to store deleted row data in pos_deletion_file, which involves write amplification. With deletion_vector_file, we no longer need to maintain them for deletion files, only need to update the associated data_file’s statistics when necessary.

References

1. https://github.com/RoaringBitmap/RoaringFormatSpec/
2. https://dl.acm.org/doi/pdf/10.1145/=3465998.3466009