You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xtable.apache.org by as...@apache.org on 2025/03/03 21:37:33 UTC
(incubator-xtable) branch main updated: Add change proposal for conversion of deletion vectors
This is an automated email from the ASF dual-hosted git repository.
ashvin pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/incubator-xtable.git
The following commit(s) were added to refs/heads/main by this push:
new dc209962 Add change proposal for conversion of deletion vectors
dc209962 is described below
commit dc209962c8f255be3b2afa5e213e5ca7735a3a14
Author: Ashvin Agrawal <as...@apache.org>
AuthorDate: Tue Jan 28 09:15:12 2025 -0800
Add change proposal for conversion of deletion vectors
---
rfc/rfc-2/2 - Deletion Info Conversion.md | 227 ++++++++++++++++++++++++++++++
1 file changed, 227 insertions(+)
diff --git a/rfc/rfc-2/2 - Deletion Info Conversion.md b/rfc/rfc-2/2 - Deletion Info Conversion.md
new file mode 100644
index 00000000..c18724b7
--- /dev/null
+++ b/rfc/rfc-2/2 - Deletion Info Conversion.md
@@ -0,0 +1,227 @@
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+-->
+# RFC-2: Support for conversion of Deletion Vectors from Delta Lake to Iceberg format
+
+## Proposers
+
+- @ashvin
+
+## Status
+
+GH Feature Request: https://github.com/apache/incubator-xtable/issues/339
+
+## Abstract
+Deletion vectors are one of the most popular features in table formats, allowing logical deletion of records, by marking
+them as deleted, without requiring rewriting of the data files to remove them physically. This document provides a
+high-level proposal of deletion vector conversion in XTable, focusing on the current implementation of deletion vectors
+in Delta Lake and Iceberg.
+
+## Background
+Deletion vectors feature in table formats like **_Delta Lake_** and **_Apache Iceberg_** are designed to enhance data
+management efficiency. These vectors allow for the marking of deleted rows without physically removing them from the
+data files, thereby optimizing operations such as `DELETE`, `UPDATE`, and `MERGE`. By maintaining a separate files of
+deletions, deletion vectors enable faster query performance and reduce the need for costly data file rewrites. This
+approach aligns with the merge-on-read paradigm, where changes are merged during read operations rather than write
+operations, ensuring minimal disruption to ongoing data ingestion processes.
+
+The main types of delete vectors are _**equality deletes**_ and _**position deletes**_.
+
+#### Equality deletes
+Equality deletes allow for row-level deletions based on specific column values rather than their positions within a
+file. This means that records in data files matching certain criteria are considered deleted without altering the
+original data files. This deletion vector type is useful when identifying and storing the exact position of the row(s)
+is expensive, but the content that identifies the row is clear. This feature is particularly useful in streaming use
+cases where updates are frequent. Currently, Iceberg supports equality deletes, however, there is a proposal to replace
+it in future versions.
+
+#### Position deletes
+Position deletes, on the other hand, specify the ordinals of records within a data file that should be considered
+deleted. This method relies on identifying the exact position within the data file, thereby providing a more precise and
+direct approach to managing row-level deletions. Position deletes can be further categorized into two representations:
+simple table representations and compressed bitmap representations.
+
+**_Simple table representations_** involve a straightforward structure typically stored in Parquet format, containing
+columns like `file_path` and `pos`. The `file_path` indicates the path of the data file, while `pos` specifies the
+ordinal of the record to be deleted. These files can optionally include the row data for equality deletes, aiding in
+identifying the exact change which is particularly useful in CDC applications.
+
+A **_compressed bitmap representations_**, leverage a compressed bitmap to represent deletions. This method allows for a
+more compact and optimized storage of delete vectors, which in turn saves memory and network bandwidth. The
+_RoaringBitmap_ is a popular choice for this representation. While the bitmaps are typically stored in separate files,
+in cases where the bitmaps are small because the number of deleted records is low, they can be embedded within the
+commit logs to optimize the number of network round trips required to load all the files.
+
+#### Row level deletes in Delta Lake
+Currently, Delta Lake supports RoaringBitmaps for deletion vectors, while Iceberg supports simple table representations.
+The java libraries of Delta Lake and Iceberg provide APIs to read and write between these representations. Delta Lake
+provides support for deletion vectors for `DELETE` operations since versions 2.4, while `UPDATE` and `MERGE` commands
+default to the copy-on-write mode.
+
+In Delta Lake, the implementation of deletion vectors involves `actions` in the commit logs, namely `AddFile` and
+`RemoveFile`. When a DML command is executed, it identifies the rows to be modified and generates a deletion vector,
+typically in a compressed bitmap format like RoaringBitmap. The generated deletion vector is stored directly
+in the commit logs `json` files (when the number of deletions is minimal). When stored in separate files, the files
+paths are encoded and referenced in the json files. With each DML operation, the commit log records the removal of the
+original data file and its addition with updated details including the newly added deletion vector.
+
+Example:
+```
+Type Path DV Path
+RemoveFile file_a.parquet NULL
+AddFile file_a.parquet file_a_dv_1.bin
+```
+
+If a file with an existing deletion vector is updated again, a new deletion vector is created, merging the previous and
+new deletions. The commit log records the removal of the old deletion vector information and the addition of the new
+one.
+
+Example:
+```
+Type Path DV Path
+RemoveFile file_a.parquet file_a_dv_1.bin
+AddFile file_a.parquet file_a_dv_2.bin
+```
+
+When a compaction operation rewrites records into new files, the deletion vectors associated with data files that are
+removed are also marked as deleted. The commit log records the removal of the old file and deletion vector and
+the addition of the new compacted file.
+
+Example:
+```
+Type Path DV Path
+RemoveFile file_a.parquet file_a_dv_2.bin
+AddFile file_d.parquet NULL
+```
+
+> Note: XTable would generate deletion vectors in the target table format corresponding to the source table format.
+> While compaction in the source table will result in the removal of deletion vectors, XTable currently does not remove
+> the generated deletion files in the target table. Over time, if the deletion vectors are not removed in the target
+> table, they could significantly increase the number of files and storage size of target table. This is a known issue
+> and a mitigation strategy is currently being discussed and tracked by this
+> [task](https://github.com/apache/incubator-xtable/issues/655).
+
+#### Row level deletes in Iceberg
+Iceberg (v2), on the other hand, supports equality deletes and simple table representations for position based row level
+deletes. This proposal focuses on positional deletes. Similar to Delta Lake, Iceberg also maintains a separate file for
+recording ordinals of deleted records. The delete entries are typically stored in parquet files with `file_path` and
+`pos` as mandatory columns.
+
+Example:
+```
+file_path, pos
+/test_table/part-00000-3c1805f0c478-c000.parquet 36
+/test_table/part-00000-3c1805f0c478-c000.parquet 35
+/test_table/part-00000-446d734f04e8-c000.parquet 7
+/test_table/part-00000-446d734f04e8-c000.parquet 9
+```
+
+However, unlike Delta Lake, the Iceberg commit log does not embed the metadata of deletion
+files withing the metadata of data files. Instead, it records addition of a deletion file as an independent event in
+a separate manifest file. The resulting manifest list file uses the same structure as that for data files, but with a
+few more properties.
+
+Example:
+```
+ "added-position-delete-files": "1",
+ "added-delete-files": "1",
+ "added-position-deletes": "12",
+ "total-delete-files": "3",
+ "total-position-deletes": "27",
+ "total-equality-deletes": "0"
+```
+
+
+## Implementation of the conversion of Deletion Vectors in XTable
+On a high level, the implementation of deletion vector conversion in XTable involves the following steps. XTable must
+first locate the deletion vector, which can be stored either inline within the commit logs or can be stored in a
+separate deletion vector file whose path is recorded in the commit logs. Once located, XTable can utilize the utility
+methods provided by table format libraries to stream the ordinals of the records affected by the deletion operations.
+
+Unlike currently supported conversion of metadata in XTable, deletion vectors require special handling. While all
+table metadata is present in commit logs and manifest files, deletion vectors can be stored in separate files. The size
+of the deletion vectors is proportional to the number of records deleted, which can be significant in large tables.
+The proposed implementation aims to handle this efficiently by streaming the records from the sources to the targets.
+
+**New Class: `InternalDeletionVector`**
+
+To improve the functionality, a new class to manage the internal in-memory representation of deletion vectors is added.
+This is similar to creating internal representation for data files, schema, and partitioning spec. For XTable, adding
+a new deletion vector file is same as adding a new data file. Moreover, the deletion vector representation is an
+extension of the data file representation, with additional fields to capture the deletion vector metadata.
+
+The following metadata is relevant for deletion vectors:
+- `size`: Size of the deletion vector.
+- `countRecordsDeleted`: Number of records deleted.
+- `sourceDeletionVectorFilePath`: Path of the deletion vector file (optional as deletion vectors can be stored inline).
+> The fields above are inherited from InternalDataFile. The fields below are new fields specific to deletion vectors.
+- `dataFilePath`: Path of the data file associated with the deletion vector.
+- `offset`: Offset of the deletion vector within the file (optional as inline deletion vectors do not have an offset).
+- `ordinalStream`: Stream of ordinals of the records deleted.
+
+**Modifications in `DataFilesDiff`**
+
+Currently, XTable only converts the addition and removal of data files. To support deletion vectors, XTable would need
+to detect new deletion vectors in the source table and add it to the conversion pipeline similar to data files.
+Handling new deletion vectors does not require any changes in the `DataFilesDiff` class. The class encapsulates the
+addition and removal of data files, and the addition of deletion vectors is treated as a new data file addition.
+Which means, if a source produces deletion vectors, going forward, the `filesAdded` field in `DataFilesDiff` will
+not only contain data files but also deletion vectors. The consumers which cannot handle instance of
+`InternalDeletionVector` in `filesAdded` can either ignore them or raise an exception.
+
+**Updates in `DeltaActionsConverter`**
+The converter class is responsible for converting Delta Lake `actions` into internal representations, resulting in
+`TableChange` objects. The converter is updated to extract deletion vectors from the `AddFile` actions. Currently,
+the converters read content from source metadata files and then close the file handles. However, this will be different
+for deletion vectors. To avoid the potential memory explosion, the converters will create a provider of deletion vectors
+ordinals, which will be used to stream the ordinals of the records deleted to the targets.
+
+**Changes in `DeltaConversionSource`**
+As described above, the delta commit logs adds data file entries in commit log each time delete vectors are updated.
+This needs special handling in the delta source, to avoid duplication of data file actions.
+
+**New class `IcebergDeleteVectorConverter`**
+
+The purpose of this class is to convert internal deletion vectors to Iceberg positional delete files. The class will
+contain methods matching other Iceberg converters, for instance `toIceberg`. However, similar to unique handling of
+deletion vectors in `DeltaActionsConverter`, this class will have a unique implementation. This class will generate
+data files for deletion vectors, which will be added to the target table. The cost of conversion of deletion vectors
+is proportional to the number of records deleted, and not the size of metadata or number of files.
+
+Iceberg is quite
+flexible when it comes to location of data and metadata files. Since deletion vectors are data files, colocating them
+with metadata files could be confusing. Typically, deletion files are stored in partition specific directories, in
+the data directory of a table. However, it seems cleaner to keep all XTable generated data files in a separate
+directory, which will be configurable. The default location for deletion vectors will be `deletion-vectors` directory
+in the base directory of the table.
+
+**Modifications in `IcebergDataFileUpdatesSync` and `IcebergConversionTarget`**
+Finally, existing classes that handle Iceberg data files and sync operations will be updated to handle deletion vectors.
+Most changes are straightforward and inline with existing logic. However, as described earlier, new deletion vectors
+are added to a separate manifest file in Iceberg. This requires invoking a separate transaction operation specific
+to row level operations. The row level operation is initiated only if there are new deletion vectors in the
+`FilesAdded`.
+
+## Rollout/Adoption Plan
+
+This change does not cause any breaking changes. Before this change, delete vectors were ignored and would cause
+incorrect results in the target table. With this change, XTable will be able to convert the deletion vectors from Delta
+Lake to Iceberg format, ensuring that the target table is consistent with the source table.
+
+## Test Plan
+
+New tests will be added to verify the conversion of deletion vectors from Delta Lake to Iceberg format. The integration
+tests will cover generation of position deletes using spark sql, and the conversion of these deletes to Iceberg format.
\ No newline at end of file