In predicate is not pruned when its literals straddle the bounds (InclusiveMetricsEvaluator and ManifestEvaluator)
- Dominant language
- Rust
- Stars
- 1.4k
- Forks
- 567
- Avg merge
- 2d 2h
- Merged PRs (30d)
- 93
Description
### Apache Iceberg Rust version
v0.10.1, and `main` at d6d06f3c4a60e5f3a6d3d789a43513a919d9eacb
### Describe the bug
`InclusiveMetricsEvaluator::in()` and `ManifestEvaluator::in()` test the lower bound and the upper bound against the *full* literal set independently, instead of narrowing the literal set as Java and PyIceberg do. As a result, an `In` predicate whose literals straddle the bounds — none of them actually inside `[lower, upper]` — is not pruned.
For a file (or manifest) with bounds `[30, 79]` and `id IN (5, 104)`:
* lower bound check: "is any literal `>= 30`?" — yes, `104` — so keep going;
* upper bound check: "is any literal `<= 79`?" — yes, `5` — so keep going;
* result: `ROWS_MIGHT_MATCH`.
Java narrows instead: after the lower-bound filter the set is `{104}`, and the upper-bound filter empties it, so it returns `ROWS_CANNOT_MATCH`. `InclusiveMetricsEvaluator#in` in `iceberg-core` and `_InclusiveMetricsEvaluator.visit_in` in PyIceberg both do this.
Interestingly `StrictMetricsEvaluator::not_in` in this repo already does it the right way, with `filtered_literals.retain(...)` — so the two `in` implementations are inconsistent with the rest of the crate.
This is a pruning-effectiveness bug, not a correctness bug: the plan is a superset, so results are still right, but data files and whole manifests that cannot contain a match are opened and read. I hit it comparing scan plans on a `bucket[4]`-partitioned table — for `id IN (1, 4, 7)` iceberg-rust planned 5 data files where PyIceberg planned 3; the two extra files hold `{3}` and `{5}`, which land in the same bucket as one of the wanted ids and so survive partition filtering, and then survive the metrics filter too.
### To Reproduce
Two failing unit tests, using the fixtures already in each test module (`id` bounds are `[30, 79]`):
```rust
// crates/iceberg/src/expr/visitors/inclusive_metrics_evaluator.rs
#[test]
fn test_integer_in_straddling_bounds() {
let result = InclusiveMetricsEvaluator::eval(
&r#in_int("id", &[INT_MIN_VALUE - 25, INT_MAX_VALUE + 25]),
&get_test_file_1(),
true,
)
.unwrap();
assert!(!result, "Should skip: id in (5, 104), bounds are [30, 79]");
}
```
```rust
// crates/iceberg/src/expr/visitors/manifest_evaluator.rs
#[test]
fn test_in_straddling_bounds() -> Result<()> {
let case_sensitive = true;
let schema = create_schema()?;
let manifest_file = create_manifest_file(create_partitions());
let filter = Predicate::Set(SetExpression::new(
PredicateOperator::In,
Reference::new("id"),
FnvHashSet::from_iter(vec![
Datum::int(INT_MIN_VALUE - 25),
Datum::int(INT_MAX_VALUE + 25),
]),
))
.bind(schema.clone(), case_sensitive)?;
assert!(
!ManifestEvaluator::builder(filter)
.build()
.eval(&manifest_file)?,
"Should not read: id in (5, 104), summary is [30, 79]"
);
Ok(())
}
```
Both fail on `main`:
```
test expr::visitors::inclusive_metrics_evaluator::test::test_integer_in_straddling_bounds ... FAILED
test expr::visitors::manifest_evaluator::test::test_in_straddling_bounds ... FAILED
```
### Expected behavior
Both should return `ROWS_CANNOT_MATCH`, matching Java and PyIceberg.
Narrowing the set the way `StrictMetricsEvaluator::not_in` already does is enough. In `InclusiveMetricsEvaluator::in`:
```rust
let mut filtered_literals = literals.clone();
if let Some(lower_bound) = self.lower_bound(field_id) {
if lower_bound.is_nan() {
return ROWS_MIGHT_MATCH;
}
filtered_literals.retain(|datum| datum.ge(lower_bound));
if filtered_literals.is_empty() {
return ROWS_CANNOT_MATCH;
}
}
if let Some(upper_bound) = self.upper_bound(field_id) {
if upper_bound.is_nan() {
return ROWS_MIGHT_MATCH;
}
filtered_literals.retain(|datum| datum.le(upper_bound));
if filtered_literals.is_empty() {
return ROWS_CANNOT_MATCH;
}
}
ROWS_MIGHT_MATCH
```
and the equivalent in `ManifestEvaluator::in`. With both changed, `cargo test -p iceberg --lib` passes: 1614 passed, 0 failed, including the two new tests.
### Willingness to contribute
I can contribute a fix for this bug independently
Contributor guide
Research direction
Start with the `in` implementations and fixtures in `crates/iceberg/src/expr/visitors/inclusive_metrics_evaluator.rs` and `manifest_evaluator.rs`, comparing them with `StrictMetricsEvaluator::not_in`. Run the two supplied regression tests, then `cargo test -p iceberg --lib`; done means straddling literals return `ROWS_CANNOT_MATCH` and the full library suite passes.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 84/100