Scan planning matches every position delete to every data file in the partition, making planning memory O(data files × delete files)
- 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
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