perf(deletes): apply equality deletes via a hashed key set inside the parquet RowFilter by brgr-s · Pull Request #2961 · apache/iceberg-rust

brgr-s · 2026-08-05T12:11:56Z

Which issue does this PR close?

Closes Equality delete file application scales with O(data rows × applicable delete keys) #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 + applicable_delete_refs).

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 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 1

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.

NOTE 2

An eq delete key column that is required and absent from a data file previously deleted every row of that file and now deletes none, but this only "hits" for those specific layouts. Other layouts or position delete file are still applied on the surviving rows. Both behaviours are spec-divergent, but this fix focues on performance and the new behaviour might be regarded as "less bad". I'd regard this worth a follow-up. See Comment
Eq delete sets no longer feed into row-group pruning, but this should not have any effect. RowGroupMetricsEvaluator::not_eq returns ROW_GROUP_MIGHT_MATCH unconditionally anyways.
Float/double delete keys (out-of-spec) now canonicalize signed zero and NaN payloads, whereas previous code had 0 != -0 and != for different NaNs. This only "hits" non-conforming writes. Might be worth a follow-up. See Comment
There is a discussion regarding rebuilding the machinery with RowConverter. This might improve performance even more, but is a bigger rebuild. See Comment
There is discussion regarding the ordering of predicates and the hash probes. If we had a model for selectivity or evaluation cost, this might also be an opportunity for performance improvements. See Comment

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

… parquet RowFilter Upstream-candidate version, based on apache/main. Does not include the fixes from apache#2873 and apache#2630; see local/eq-deletes.md.

mbutrovich

Thanks for looking at this @brgr-s. I inlined some comments from my first pass, and I have a number of test gaps to suggest:

Scan predicate combined with an equality delete, end to end. Every new eqd_* test in row_filter.rs uses the eqd_read helper (row_filter.rs:1445), which never calls .with_predicate(...); the only with_predicate usage in this file is in a pre-existing, unrelated test (row_filter.rs:388). This is exactly the code path this PR rewired: final_predicate and eq_delete_sets used to be ANDed into one bound Predicate before binding; now they're two separately-pushed ArrowPredicates in row_filter_predicates (pipeline.rs:388-451). Nothing exercises both branches being taken in the same scan and checking the intersection is correct. Same gap one level up: no test combines a positional delete, an equality delete, and a scan predicate in one real read and checks output rows; the existing "both delete types together" test (caching_delete_file_loader.rs, formerly test_build_equality_delete_predicate_case_sensitive-adjacent) only asserts build_equality_delete_sets(...).is_ok(), not actual filtered output.

Two equality-delete files, same equality_ids, different on-disk parquet types, through the real load path. This is the happy-path counterpart to test_union_rejects_mismatched_layout: that test only proves union() rejects a mismatch when two EqDeleteSets are hand-built with different types. Nothing proves the realistic case, that evolve_schema/RecordBatchTransformer normalizes two physically-different-typed delete files (e.g. one written as int32, another as int64, same equality_ids) to the same recorded type before they ever reach union(), so the grouping-by-id-only key in build_equality_delete_sets (delete_filter.rs:213) stays safe. Right now that guarantee is established only by reading the code, not by a test; if evolve_schema's casting behavior ever regresses, nothing would catch it before union() starts erroring in production.

Equality-delete key column missing from the data file, with a non-null initial_default on that field. Ties to the row_filter.rs:127-130 finding above: add a test with a field added via schema evolution with .with_initial_default(...), an older data file written before that field existed, and an equality-delete file keyed on it, and assert on the intended behavior (spec.md:898). Worth having regardless of which way the finding gets resolved, since right now nothing pins the behavior down at all.

Decimal precision promotion through the probe. test_eq_delete_promotes_data_type_before_probe only covers Int32 -> Int64. Datum::to has an explicit branch that errors on decimal scale mismatches (datum.rs:1168-1182) and a separate branch for same-scale precision promotion; decimal columns are a realistic equality-delete key (e.g. monetary amounts) and Iceberg's supported decimal evolution (precision widening) goes through a different code path than the int case already tested.

Float/double equality-delete columns. The spec explicitly disallows these ("Float and double columns cannot be used as delete columns in equality delete files", spec.md:853), but nothing in this PR checks for or tests that. EqDeleteKey derives Hash/Eq on Datum, so a float delete column would hit IEEE-754 float equality/hashing (NaN, -0.0 vs 0.0) that the spec restriction exists specifically to avoid. Worth a test asserting a clear, explicit rejection rather than relying on callers never producing one.

Empty EqDeleteSet skip path. if set.is_empty() { continue; } (row_filter.rs:90-92) is untested directly: an equality-delete file that parses to zero keys (e.g. legitimately empty file) should produce no ArrowPredicate for that set and not affect row-group/row-selection filtering. Same code path also needs to handle every key column of a set being simultaneously absent from the data file (column_indices ends up empty, ProjectionMask::leaves(parquet_schema, [])); worth confirming RowFilter still reports the correct row count with a zero-column projected batch.

Lower confidence, likely pre-existing behavior this PR doesn't touch, but the new test suite had a natural opportunity to cover it: an equality-delete file whose key column was later dropped from the table. Spec.md:898, first sentence, requires the dropped column still be used for matching. evolve_schema's target schema is task.schema (the current schema), which by definition no longer declares a dropped field; whether RecordBatchTransformer still carries a dropped-but-still-referenced equality_ids column through is worth a test even though the mechanism predates this PR.

mbutrovich · 2026-08-05T16:07:33Z

+                        let Some(pos) = batch_positions[i] else {
+                            columns.push(vec![None; num_rows]);
+                            continue;
+                        };


When an equality-delete key column is absent from a data file's parquet schema (schema evolution: the column was added after this file was written), the probe treats it as null for every row: columns.push(vec![None; num_rows]); continue;. Per spec.md:898, "the column value is read for older data files using normal projection rules" for exactly this case, and iceberg-rust already has a mechanism for "normal projection rules" for a missing column: RecordBatchTransformer resolves initial_default (see record_batch_transformer.rs, "Rule #3"), used for the data file's own output columns at pipeline.rs:494. The eq-delete probe runs earlier, inside the RowFilter, on raw decoded batches, before RecordBatchTransformer ever sees them, so it never consults initial_default and always substitutes null instead. Java's DeleteFilter avoids this by construction: it compares against record, which is built by the regular row reader against requiredSchema (DeleteFilter.java:99-101, 202-209), i.e. defaults are already resolved before the delete-set lookup runs at all. Concretely: a required column added later with a non-null initial_default, later used as an equality-delete key, will never delete matching rows in data files written before that column existed, because every row in those files probes as null instead of the default value. Low likelihood in practice, but it's a silent, spec-observable divergence, not a crash, so worth a test either way.

I followed your trace and you are correct, this is a spec divergence.

Digging deeper: the old code was also spec-divergent, in two different ways:

required missing columns lead to all rows beeing dropped for that data file

optional missing columns on the other hand "do nothing"

This PR keeps all rows in both cases, but scoped to that specific layout group. All rows survive, but if other delete files apply (eq deletes with different layouts, pos deletes), they "can" delete rows... I'd argue that this a slight improvement (maybe ressurect some rows vs. hard dropping all), but the fact you pointed out remains: it is spec divergent, it needs to be made obvious, and it needs to be fixed (but maybe not on this PR). I think this would be worth filing an issue, even if this PR does not get accepted.

it is spec divergent, it needs to be made obvious, and it needs to be fixed (but maybe not on this PR). I think this would be worth filing an issue, even if this PR does not get accepted.

The comment on test_eq_delete_on_column_absent_from_data_file makes the divergence visible. Could you file that issue and put its number in the test comment, so whoever fixes it finds the test?

Filed issue: #3369

it is spec divergent, it needs to be made obvious, and it needs to be fixed (but maybe not on this PR).

#3302 fixes case B of #3369 on the predicate path in main. Before the row filter is built, it evaluates each leaf on a column missing from the data file against that column's identity partition value or initial-default. The keep predicate built from equality deletes goes through the same step. assert_absent_b_reads_as_7 checks that an equality delete on b = 7 removes every row of a file that doesn't store b, when b reads as 7 through initial-default or an identity partition value.

The set probe here doesn't go through that predicate, and a missing key column becomes None. If #3302 merges first, this PR would bring case B back as a regression against main.

What do you think about resolving a missing key column with the normal projection rules in the probe: the identity partition value, then initial-default, then null? That value is the same for every row of the file, so the probe can use it as a constant column. When every key column of a set is missing, the set reduces to one lookup per file that keeps or drops all rows. residual_for_missing_fields in #3302 resolves the same values from constants_map and initial_default, so the two paths could share that lookup.

@mbutrovich I just pushed a change that resolves the missing key column with standard projection rules, after merging main in, so this branch should be up-to-date and not re-introduce the problem #3302 fixes.

brgr-s · 2026-08-05T19:28:44Z

@mbutrovich Thank you for your thourough review, really appreciate it. I will address your points shortly :)

brgr-s · 2026-08-06T13:22:58Z

@mbutrovich I worked through your comments and will follow up with commits adressing where we agree. Specifically, because it is not inlined: the test gap is real, so more tests!

I just have three comments on the test gaps:

float/double equality-delete columns: Datum does not use IEE-754 float semantics. PrimitiveLiteral stores OrderedFloat<..>, which treats NaN == NaN and Hash uses CANONICAL_NAN_BITS and canonicalize_signed_zero, so both agree. However, this does introduce a change: on main, eq-deletes go through arrow's kernel where is_eq is bitwise, so -0.0 != 0.0 and different NaN bits also do not match. I feel like the spec is not really clear on what is correct... but at the end of the day, it only applies to input that the spec dissallows and would only hit non-conforming writes. But the old implemenation also already did not Err on this, so we'd introduce a regression for those non-conforming writer. I'd opt for the test and against the error.

if set.is_empty() { continue; } untested: correct, but a test is limited. If continue is removed, you get num_cols = 0, empty keys, and contains is always false, so every row is kept for that pass. It is performance guard, not a correctness guard. “doesn’t affect row-group/row-selection filtering” is true by construction: after this PR only task.predicat drives row-group and page-index filtering, eq delete sets never do.

equality-delete key column later dropped from the table: this is pre-existing, but nothing would reach the probe: the scan would fail outright on generate_batch_transform:

Ok(field_id_to_mapped_schema_map
  .get(field_id)
  .ok_or(Error::new(ErrorKind::Unexpected, "field not found"))? // <------ here
  .0
  .clone())

I checked DeleteFilter.java:76 and DeleteFilter.java:318: I think this is the same failure. I think this is worth an issue rather than checking on an error string here. WDYT?

base)

…ete-hash

JanKaul · 2026-08-28T09:59:25Z

Did an independent verification pass on 06edf3c from a clean checkout: cargo test -p iceberg --lib → 1576 passed / 0 failed, arrow:: subset 169 passed, and clippy/fmt --check both clean. So CI green reproduces locally.

I also reviewed the hash-probe for silent mis-deletion risks and it holds up:

Datum hashes/compares over both type and value, and layout_matches checks field-id and type — so the per-row promotion (needs_promotion → datum.to(target)) is exactly what keeps probe keys comparable with the parsed delete keys under schema evolution. Nicely covered by the decimal-widening and int32→int64 tests.
Null-matches-null equality is correct and tested.
The multi-set AND-ing (keep = !set.contains; RowFilter ANDs) correctly deletes a row that matches any layout set, and the probe key is fully rewritten each row with a safe per-cell take().
Pipeline-wise, scan predicate + eq-delete predicates land in the RowFilter while positional deletes still drive the RowSelection, and they compose correctly.

The test suite now covers essentially the whole gap list from the first review (scan-pred × eq-delete intersection, pos+eq+pred, differing physical types through the real load path, decimal promotion, float/double canonicalization, empty set, absent key column). The absent-required-column → initial_default divergence is clearly documented and test-pinned; agree it's a good follow-up rather than a blocker here.

LGTM from my (non-committer) review; the remaining threads read as agreed follow-ups. Would be great to get a committer's eyes on it to move it forward.

github-actions · 2026-09-28T00:28:18Z

This pull request has been marked as stale due to 30 days of inactivity. It will be closed in 1 week if no further activity occurs. If you think that’s incorrect or this pull request requires a review, please simply write any comment. If closed, you can revive the PR at any time and @mention a reviewer or discuss it on the [email protected] list. Thank you for your contributions.

mbutrovich

Thanks for working through the first round, @brgr-s, and for the new tests. The branch now conflicts with main in caching_delete_file_loader.rs, delete_filter.rs, pipeline.rs, and row_filter.rs. Most of that comes from reader changes that landed since August, including the deletion vector read path in #3035. Could you merge or rebase onto main and resolve those? I'll do another pass once it's green.

The PR description says you'd rather rebase after #2873 and #2630 merge. #2873 was closed and continues as #3268, and both are still open. Would you be OK rebasing onto current main now instead of waiting for them?

equality-delete key column later dropped from the table: this is pre-existing, but nothing would reach the probe: the scan would fail outright on generate_batch_transform

I think this is worth an issue rather than checking on an error string here. WDYT?

An issue works for me, since this PR doesn't change that path. Could you file it and link it here? The spec says a dropped delete column "must still be used when applying the equality deletes". The initial_default case from the other thread comes from the same spec paragraph, so one issue could cover both.

mbutrovich · 2026-09-28T18:35:07Z

I removed the stale tag btw, if you're still game to work on this.

brgr-s · 2026-10-07T13:37:57Z

@mbutrovich Sorry for the late reply. I'm still interested in getting this merged, so I will work through your new comments and report back :)

…ete-hash

brgr-s · 2026-10-07T14:24:15Z

@mbutrovich #3268 merged in the meantime, so one thing less to do :)

I'll file two issues

Spec projection rules for equality deletes.
RowConverter follow-up

@JeonDaehong I'll file your note as issue as well, linking the Java-side issue and PR.

JeonDaehong · 2026-10-08T08:14:43Z

Thanks for filing those follow-ups, @brgr-s! Looking forward to the issue for my note. Happy to help with it once it's up!

JeonDaehong · 2026-10-14T11:20:39Z

FYI #3450: equality deletes on nested fields fail to load today. Since this PR reworks the same path, would you prefer I fix it on top of this PR after it lands, or separately now?

brgr-s · 2026-10-14T11:46:25Z

@JeonDaehong If this was directed at me: either is fine for me. Currently this PR is not moving forward very fast, and I feel the bug your are describing might be a bit more urgent, so probably no point in waiting?

JeonDaehong · 2026-10-14T12:12:19Z

Thanks @brgr-s! I'll fix it separately then, and keep the change small so it's easy to rebase this PR on top. I'll tag you on the PR.

mbutrovich · 2026-10-14T12:28:39Z

I generally don't like to increase scope of PRs for a few reasons: 1) they get squashed to the single commit on merge, so we lose the commit history, 2) that one commit is what goes in the changelog, which makes it hard to reason about the changes, 3) it makes it harder to revert if something breaks.

I know we're review-limited, but that's always true so I still prefer smaller scoped PRs.

Rebase of apache#2961 onto the fork base: - FileScanTaskDeleteFile requires file_format and its builder, like FileScanTask's, returns a Result since apache#3145, so the test helpers set the format and unwrap. - Literal equality follows Java's Double.compare since apache#3327: NaN matches NaN but -0.0 and 0.0 are distinct, so a -0.0 equality delete no longer removes the 0.0 row. The signed-zero test now expects that. Conflict resolutions made while replaying the PR's commits: the deletion-vector loader, the lost-wakeup fix in DeleteFilter (notified_owned) and the NOT normalization in the read pipeline are kept from upstream; the equality-delete set plumbing comes from the PR; both the upstream bloom-filter tests and the PR's equality-delete tests stay in row_filter.rs. Co-Authored-By: Claude Fable 5.1 <[email protected]>

The snapshot now also carries apache/iceberg-rust#2961, equality deletes applied through a hashed key set inside the parquet RowFilter. No source changes needed; Cargo.lock follows the pin. Co-Authored-By: Claude Fable 5.1 <[email protected]>

…e-hash

perf(deletes): apply equality deletes via a hashed key set inside the…

2b41415

… parquet RowFilter Upstream-candidate version, based on apache/main. Does not include the fixes from apache#2873 and apache#2630; see local/eq-deletes.md.

mbutrovich reviewed Aug 5, 2026

View reviewed changes

brgr-s added 6 commits August 6, 2026 15:24

Merge branch 'main' into brgr-s/equality-delete-hash

f9a8f28

Improve allocations in hash probe

c48dc2b

Add tests, comments and slightly improve merging (take biggest group as

1bbaa37

base)

Merge branch 'main' into brgr-s/equality-delete-hash

880d4cd

Merge remote-tracking branch 'upstream/main' into brgr-s/equality-del…

a7493ac

…ete-hash

Not a typo typo fix

06edf3c

mattfaltyn mentioned this pull request Aug 31, 2026

bug(arrow): filters lose rows after numeric schema promotion #3122

Open

github-actions Bot added the stale label Sep 28, 2026

mbutrovich self-requested a review September 28, 2026 13:13

mbutrovich removed the stale label Sep 28, 2026

mbutrovich reviewed Sep 28, 2026

View reviewed changes

Comment thread crates/iceberg/src/arrow/reader/row_filter.rs Resolved

brgr-s added 2 commits October 7, 2026 16:04

Merge remote-tracking branch 'upstream/main' into brgr-s/equality-del…

175e5b4

…ete-hash

reword comment

12c2bd3

This was referenced Oct 7, 2026

Equality deletes ignore spec projection rules for dropped and newly added delete columns #3369

Open

perf(deletes): build equality-delete probe keys with arrow::row::RowConverter #3370

Open

JeonDaehong mentioned this pull request Oct 14, 2026

fix(arrow): load equality deletes on fields nested in structs #3453

Open

brgr-s added 2 commits October 28, 2026 13:58

Merge remote-tracking branch 'origin/main' into brgr-s/equality-delet…

a272edd

…e-hash

value of missing key columns by standard projection rules

9be1845

c-thiel mentioned this pull request Nov 2, 2026

fix(spec): mark stale snapshot errors in add_snapshot as retryable conflicts lakekeeper/iceberg-rust#17

Merged

hcrosse mentioned this pull request Nov 3, 2026

perf(reader): skip per-row predicate evaluation when statistics prove every row matches #3613

Open

Conversation

brgr-s commented Aug 5, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Which issue does this PR close?

What changes are included in this PR?

Are these changes tested?

AI Disclosure

Uh oh!

mbutrovich left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mbutrovich Aug 5, 2026

Choose a reason for hiding this comment

Uh oh!

brgr-s Aug 6, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mbutrovich Sep 28, 2026

Choose a reason for hiding this comment

Uh oh!

brgr-s Oct 7, 2026

Choose a reason for hiding this comment

Uh oh!

mbutrovich Oct 16, 2026

Choose a reason for hiding this comment

Uh oh!

brgr-s Oct 28, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

brgr-s commented Aug 5, 2026

Uh oh!

brgr-s commented Aug 6, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

JanKaul commented Aug 28, 2026

Uh oh!

github-actions Bot commented Sep 28, 2026

Uh oh!

mbutrovich left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

mbutrovich commented Sep 28, 2026

Uh oh!

brgr-s commented Oct 7, 2026

Uh oh!

brgr-s commented Oct 7, 2026

Uh oh!

JeonDaehong commented Oct 8, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

JeonDaehong commented Oct 14, 2026

Uh oh!

brgr-s commented Oct 14, 2026

Uh oh!

JeonDaehong commented Oct 14, 2026

Uh oh!

mbutrovich commented Oct 14, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

This branch has not been deployed

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

brgr-s commented Aug 5, 2026 •

edited

Loading

mbutrovich left a comment •

edited

Loading

brgr-s Aug 6, 2026 •

edited

Loading

brgr-s commented Aug 6, 2026 •

edited

Loading

JeonDaehong commented Oct 8, 2026 •

edited

Loading

mbutrovich commented Oct 14, 2026 •

edited

Loading