apache / apache/iceberg-rust

Scan planning matches every position delete to every data file in the partition, making planning memory O(data files × delete files)

Open
#2,935 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Rust
Stars
1.4k
Forks
567
Avg merge
2d 2h
Merged PRs (30d)
93

Description

### Apache Iceberg Rust version

None

### Describe the bug

`PopulatedDeleteFileIndex` matches position deletes by partition and sequence number only, never by the data file they reference. On an unpartitioned merge-on-read table that is a single bucket, so planning creates a `FileScanTaskDeleteFile` for nearly every (data file, delete file) pair.

`crates/iceberg/src/delete_file_index.rs`:

- `PopulatedDeleteFileIndex` holds `pos_deletes_by_partition`, and a `pos_deletes_by_path` map is present but commented out with `// TODO: do we need this?`
- `get_deletes_for_data_file` has a `TODO` quoting the spec's referenced_data_file rule and noting "we're not yet doing that here"

Results are correct, but planning allocates memory proportional to the product.

https://github.com/apache/iceberg-rust/issues/630 mentions this:

> A naive approach may be to simply build a list of all of the delete files referred to by the top-level manifest list and give references to this list to all `ManifestEntryContexts` so that, if any delete files are present then all of them are included in every `FileScanTask`.
> Improvements could then be made to refine this approach to filter out inapplicable delete files that goes into each `FileScanTask`'s `delete_files` property.
> Challenging part of deletion file processing is to filter unnecessary deletion files in each task, which we can introduce as optimization later.

This issue is meant as a follow-up. I have encountered an OOM when testing #2620 by implementing compaction and letting it run on various table layouts. Note that #2620 merely is important for compaction, the problem I am describing exist independat from this.

One such table was written using Trino `MERGE INTO` commits. It is unpartitioned, v2 merge-on-read with a 200-column decimal-heavy schema. Some statistics:

data files: 1,440
position delete files: 204,557 (file-scoped, ~2.85 delete rows each)
data rows: 676,923
data bytes: 89.8 MB (on disk)
delete bytes: 219 MB (on disk)

Tracing lead me to my planning stage where I found 180,650,985 delete-file references, which fits niceley to the suggested O(data files × delete files) bound. Data sequence number "pruning" does reduce the number of references (`0.63*1,440*204,557`, every `MERGE` can only reference data files before that, so only the final commit could reference all 1,440 files), but not enough. At `size_of::()` == 80 B inline plus owned 158-byte path, that is ~53 GB, and the process was OOM-killed 26 seconds in — before any delete file was read.

I implemented the mentioned "filter [for] for unneccessary deletion files in each task" and re-tryed. Memory-consumption dropped to 0.81 GB, indicating that I could be on the right track, which lead me to filing this issue.

The fix mimiks Javas' approach: use `referenced_data_file` when set, otherwise fall back to the reserved `file_path` column's bounds when `lower == upper` (every row then names the same data file), otherwise partition scope (`ContentFileUtil.referencedDataFile`). `DeleteFileIndex` keeps a `posDeletesByPath` bucket accordingly. I will open a PR with the suggested fix, referencing this issue.

### To Reproduce

My test table was created as follows

In a loop, create a temp table with 5 to 1000 rows, randomly. The schema is an id field an 200 floating point numbers. With propability 80% choose existing ids (it is just a counter) and generate new random data for that. You may also add an additional field that indicates U(pdate) or D(elete), but I chose to create only ~1% D(elet)s, so this probably doesn't matter. Ingest the Table using Trino into a target table:

`MERGE INTO… WHEN MATCHED AND ... THEN UPDATE … WHEN MATCHED AND IS_DELETE=‘D’ THEN DELETE ... WHEN NOT MATHED THEN INSERT`

The target table is V2, unpartitioned, with merge-on-read set.

1440 iterations should produce a layout roughly equivalent to min.

A small binary that `plan_files` the table and `try_collect`s the `FileScanTask` should then produce a similar memory problem.

### Expected behavior

I'd expect `try_collect` on the result of `plan_files` to succeed as the number of delete files might be huge, but each of them only applies to a single file and the resulting memory footbrint should be much smaller.

### Willingness to contribute

I would be willing to contribute a fix for this bug with guidance from the Iceberg community

Contributor guide

Open the contributing guide

Research direction

Start in crates/iceberg/src/delete_file_index.rs, reading PopulatedDeleteFileIndex, get_deletes_for_data_file, and the commented pos_deletes_by_path TODO. Use the described unpartitioned merge-on-read table or a small plan_files/try_collect reproduction to inspect planning memory. Done means position deletes are matched to their referenced data files, with partition-scope fallback where needed, and planning avoids the data-file × delete-file allocation pattern.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.