brgr-s opened a new pull request, #2961:
URL: https://github.com/apache/iceberg-rust/pull/2961
## Which issue does this PR close?
- Closes #2950
## What changes are included in this PR?
Equality deletes are currently applied by turning every delete row into a
predicate
expression and OR-ing them into a single tree, which is then evaluated
against every row
of every data file the delete file applies to. The cost is `O(data_rows ×
delete_keys)`.
This replaces the predicate tree with a hash probe:
- **`EqDeleteSet`** (`arrow/caching_delete_file_loader.rs`) holds the delete
keys as a `HashSet<EqDeleteKey>`, where `EqDeleteKey(Vec<Option<Datum>>)` is
one delete row's equality-field values. The set also carries the layout it was
built for as `Vec<(name, field_id, Type)>`.
- Delete files that share a layout are merged with **`EqDeleteSet::union`**,
which returns `Err` when the layouts differ rather than trusting the caller.
- **`build_equality_delete_predicates`** (`arrow/reader/row_filter.rs`)
turns each set into one `ArrowPredicate` pushed into parquet's `RowFilter`,
with a `ProjectionMask` restricted to that set's equality columns. Only those
columns are decoded to evaluate the filter, and rows are dropped during decode
rather than after materialisation.
- Sets with distinct layouts become independent predicates applied in
sequence, so a table whose delete files disagree on equality-field ids stays
correct.
Cost becomes `O(data_rows + delete_keys)`.
We hit this compacting merge-on-read tables written by Flink upsert
(`write.upsert.enabled`, format-version 2), where each commit contributes an
equality-delete file and the reader ends up applying a large fraction of them
to every data file. Two test tables, timing the read+rewrite phase:
```
data files eq-delete files delete refs before
after speedup
a120 120 120 7,140 27,536 ms
3,333 ms 8.3x
b500 500 500 124,750 295,268 ms
21,250 ms 13.9x
```
This is the same core idea as **#2343 by @t3hw** — replace the
per-delete-row predicate tree with a hash-set check — and that PR deserves the
credit for identifying the problem and the fix. It was closed by the stale bot
after 30 days of inactivity. @t3hw has since
[confirmed](https://github.com/apache/iceberg-rust/pull/2343#issuecomment-)
that their organisation moved off iceberg-rust and nobody is pushing it
forward, and encouraged filing this.
This is an independent implementation written against current `main` rather
than a revival of that branch, because #2343 cannot be pushed to from outside.
*!!! NOTE !!!!*
Does not include the fixes from #2873 and #2630 and therefore still carries
the same bugs these PRs aim to fix. I decided against folding in those changes
in this PR. I would rather rebase my PR after #2873 and #2630 have been merged.
## Are these changes tested?
Yes — 11 new tests:
*Delete-set construction and semantics* (`caching_delete_file_loader.rs`,
`delete_filter.rs`):
- `test_equality_delete_set_preserves_null_rows`
- `test_equality_delete_set_matches_null_delete_value`
- `test_equality_delete_set_multiple_columns`
- `test_equality_delete_set_multiple_delete_rows`
- `test_build_equality_delete_sets_mixed_ids_not_merged`
- `test_build_equality_delete_sets_same_layout_unioned`
- `test_union_rejects_mismatched_layout`
*End-to-end filtering through the reader* (`reader/row_filter.rs`):
- `test_eq_delete_single_column_filters_matching_rows`
- `test_eq_delete_multi_column_keeps_null_and_partial_matches`
- `test_eq_delete_promotes_data_type_before_probe`
- `test_eq_delete_distinct_layouts_apply_independently`
Also verified on the rebased branch:
- `cargo test -p iceberg --lib` — 1500 passed, 0 failed
- `cargo clippy -p iceberg --all-targets --all-features` — clean
- `cargo fmt --check` — clean
- `cargo public-api -p iceberg --all-features -ss` diffs empty against
`crates/iceberg/public-api.txt`: **no public API change** (the new types
are
`pub(crate)`), so `public-api.txt` needs no regeneration.
## AI Disclosure
I used AI to
- Identify the runtime problem I encountered and write a specific test that
validated the identified problem
- Search for filings of PRs and Issues in `iceberg-rust` GitHub
- Check Iceberg Java for their approach
- Review my changes before filing the PR
- Help formulate the Issue and PR text
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
