This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-3144-68a17aba6ee0c1500bcb65e881da4c71786bc42a in repository https://gitbox.apache.org/repos/asf/iceberg-rust.git
commit 2135b37730c55ba98fecaae8747bffb7105c0ece Author: Marcelo Tesla <[email protected]> AuthorDate: Wed Oct 28 09:54:50 2026 +0000 fix(expr): prune In predicates that straddle metrics bounds (#3144) * fix(expr): prune In predicates that straddle metrics bounds InclusiveMetricsEvaluator and ManifestEvaluator tested each bound against the full literal set, so IN lists with values both below lower and above upper were not pruned. Narrow the set the way Java, PyIceberg, and StrictMetricsEvaluator::not_in already do. * fix(expr): check In literals against both bounds together Apply review feedback: use any() instead of clone/retain, and prune straddling In predicates in RowGroupMetricsEvaluator too. * refactor(expr): share In bound check across metrics evaluators The three In evaluators used the same match. Pull it into a crate-private helper. * fix(expr): treat NaN metrics bounds as unbounded for In pruning A valid min or max still prunes when the other bound is NaN, instead of bailing on both sides. * chore(deps): bump ctutils and tokio past rustsec advisories The security audit fails on ctutils 0.4.2 and warns on tokio 1.53.1. Both versions are already on main. 0.4.5 and 1.53.3 clear the two advisories. * fix(expr): keep incomparable In literals from pruning ge and le are false when Datum::partial_cmp is None, so any_literal_in_bounds treated those literals as outside the range. Prune only when every literal is provably below the lower bound or above the upper bound. * fix(expr): look up row group stats once for In min_value and max_value each resolved the same statistics. The In path now uses one stats_and_type_for_field_id lookup and still drops a NaN bound before the prune. --------- Co-authored-by: Marcelo Tesla <[email protected]> --- Cargo.lock | 4 +- .../expr/visitors/inclusive_metrics_evaluator.rs | 181 ++++++++++++++++++--- .../src/expr/visitors/manifest_evaluator.rs | 49 ++++-- crates/iceberg/src/expr/visitors/mod.rs | 127 +++++++++++++++ .../expr/visitors/row_group_metrics_evaluator.rs | 147 ++++++++++++++--- 5 files changed, 442 insertions(+), 66 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 017d9b071..859704c5a 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -6628,9 +6628,9 @@ checksum = "1f3ccbac311fea05f86f61904b462b55fb3df8837a366dfc601a0161d0532f20" [[package]] name = "tokio" -version = "1.53.1" +version = "1.53.3" source = "registry+https://github.com/rust-lang/crates.io-index"; -checksum = "202caea871b69668250d242070849eb495be178ed697a3e98aebce5bc81a0bed" +checksum = "ce3335fa71841cda333a58d7615b03901380ecf09d59b3296d21f8bbac0dde4e" dependencies = [ "bytes", "libc", diff --git a/crates/iceberg/src/expr/visitors/inclusive_metrics_evaluator.rs b/crates/iceberg/src/expr/visitors/inclusive_metrics_evaluator.rs index f7abe7ab5..c1b61cd6a 100644 --- a/crates/iceberg/src/expr/visitors/inclusive_metrics_evaluator.rs +++ b/crates/iceberg/src/expr/visitors/inclusive_metrics_evaluator.rs @@ -455,30 +455,21 @@ impl BoundPredicateVisitor for InclusiveMetricsEvaluator<'_> { return ROWS_MIGHT_MATCH; } - if let Some(lower_bound) = self.lower_bound(field_id) { - let lower_bound = &*Self::promote_bound(lower_bound, reference); - if lower_bound.is_nan() { - // NaN indicates unreliable bounds. See the InclusiveMetricsEvaluator docs for more. - return ROWS_MIGHT_MATCH; - } - - if !literals.iter().any(|datum| datum.ge(lower_bound)) { - // if all values are less than lower bound, rows cannot match. - return ROWS_CANNOT_MATCH; - } - } - - if let Some(upper_bound) = self.upper_bound(field_id) { - let upper_bound = &*Self::promote_bound(upper_bound, reference); - if upper_bound.is_nan() { - // NaN indicates unreliable bounds. See the InclusiveMetricsEvaluator docs for more. - return ROWS_MIGHT_MATCH; - } - - if !literals.iter().any(|datum| datum.le(upper_bound)) { - // if all values are greater than upper bound, rows cannot match. - return ROWS_CANNOT_MATCH; - } + let lower_bound = self + .lower_bound(field_id) + .map(|bound| Self::promote_bound(bound, reference)); + let upper_bound = self + .upper_bound(field_id) + .map(|bound| Self::promote_bound(bound, reference)); + + // A NaN bound is unreliable on that side only. Drop it to unbounded + // so a valid bound can still prune. + if super::all_literals_outside_bounds( + super::finite_bound(lower_bound.as_deref()), + super::finite_bound(upper_bound.as_deref()), + literals, + ) { + return ROWS_CANNOT_MATCH; } ROWS_MIGHT_MATCH @@ -1657,6 +1648,59 @@ mod test { ); } + #[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]"); + } + + #[test] + fn test_float_in_nan_upper_bound_prunes_below_lower() { + let result = InclusiveMetricsEvaluator::eval( + &r#in_float("no_nans", &[2.0, 3.0]), + &get_test_file_float_nan_upper(), + true, + ) + .unwrap(); + assert!( + !result, + "Should skip: NaN upper is unbounded, both literals are below lower 4.0" + ); + } + + #[test] + fn test_float_in_nan_lower_bound_prunes_above_upper() { + let result = InclusiveMetricsEvaluator::eval( + &r#in_float("no_nans", &[2.0, 3.0]), + &get_test_file_float_nan_lower(), + true, + ) + .unwrap(); + assert!( + !result, + "Should skip: NaN lower is unbounded, both literals are above upper 1.0" + ); + } + + #[test] + fn test_float_in_nan_lower_bound_does_not_prune_when_a_literal_is_inside_upper() { + let result = InclusiveMetricsEvaluator::eval( + &r#in_float("no_nans", &[2.0, 4.0]), + &get_test_file_float_nan_lower_upper_3(), + true, + ) + .unwrap(); + assert!( + result, + "Should read: NaN lower is unbounded, 2.0 is inside upper 3.0" + ); + } + #[test] fn test_integer_not_in() { let result = InclusiveMetricsEvaluator::eval( @@ -1987,6 +2031,16 @@ mod test { filter.bind(schema.clone(), true).unwrap() } + fn in_float(reference: &str, float_literals: &[f32]) -> BoundPredicate { + let schema = create_test_schema(); + let filter = Predicate::Set(SetExpression::new( + In, + Reference::new(reference), + FnvHashSet::from_iter(float_literals.iter().copied().map(Datum::float)), + )); + filter.bind(schema.clone(), true).unwrap() + } + fn not_in_int(reference: &str, int_literals: &[i32]) -> BoundPredicate { let schema = create_test_schema(); let filter = Predicate::Set(SetExpression::new( @@ -2200,6 +2254,85 @@ mod test { content_size_in_bytes: None, } } + + fn get_test_file_float_nan_upper() -> DataFile { + DataFile { + content: DataContentType::Data, + file_path: "/test/path".to_string(), + file_format: DataFileFormat::Parquet, + partition: Struct::empty(), + record_count: 10, + file_size_in_bytes: 10, + column_sizes: Default::default(), + value_counts: HashMap::from([(9, 10)]), + null_value_counts: HashMap::from([(9, 0)]), + nan_value_counts: HashMap::from([(9, 0)]), + lower_bounds: HashMap::from([(9, Datum::float(4.0_f32))]), + upper_bounds: HashMap::from([(9, Datum::float(f32::NAN))]), + key_metadata: None, + split_offsets: None, + equality_ids: None, + sort_order_id: None, + partition_spec_id: 0, + first_row_id: None, + referenced_data_file: None, + content_offset: None, + content_size_in_bytes: None, + } + } + + fn get_test_file_float_nan_lower() -> DataFile { + DataFile { + content: DataContentType::Data, + file_path: "/test/path".to_string(), + file_format: DataFileFormat::Parquet, + partition: Struct::empty(), + record_count: 10, + file_size_in_bytes: 10, + column_sizes: Default::default(), + value_counts: HashMap::from([(9, 10)]), + null_value_counts: HashMap::from([(9, 0)]), + nan_value_counts: HashMap::from([(9, 0)]), + lower_bounds: HashMap::from([(9, Datum::float(f32::NAN))]), + upper_bounds: HashMap::from([(9, Datum::float(1.0_f32))]), + key_metadata: None, + split_offsets: None, + equality_ids: None, + sort_order_id: None, + partition_spec_id: 0, + first_row_id: None, + referenced_data_file: None, + content_offset: None, + content_size_in_bytes: None, + } + } + + fn get_test_file_float_nan_lower_upper_3() -> DataFile { + DataFile { + content: DataContentType::Data, + file_path: "/test/path".to_string(), + file_format: DataFileFormat::Parquet, + partition: Struct::empty(), + record_count: 10, + file_size_in_bytes: 10, + column_sizes: Default::default(), + value_counts: HashMap::from([(9, 10)]), + null_value_counts: HashMap::from([(9, 0)]), + nan_value_counts: HashMap::from([(9, 0)]), + lower_bounds: HashMap::from([(9, Datum::float(f32::NAN))]), + upper_bounds: HashMap::from([(9, Datum::float(3.0_f32))]), + key_metadata: None, + split_offsets: None, + equality_ids: None, + sort_order_id: None, + partition_spec_id: 0, + first_row_id: None, + referenced_data_file: None, + content_offset: None, + content_size_in_bytes: None, + } + } + fn get_test_file_2() -> DataFile { DataFile { content: DataContentType::Data, diff --git a/crates/iceberg/src/expr/visitors/manifest_evaluator.rs b/crates/iceberg/src/expr/visitors/manifest_evaluator.rs index 61f01cd5e..b9140d591 100644 --- a/crates/iceberg/src/expr/visitors/manifest_evaluator.rs +++ b/crates/iceberg/src/expr/visitors/manifest_evaluator.rs @@ -401,6 +401,9 @@ impl BoundPredicateVisitor for ManifestFilterVisitor<'_> { _predicate: &BoundPredicate, ) -> Result<bool> { let field = self.field_summary_for_reference(reference); + // A missing lower_bound covers all-null, all-NaN, and mixed null+NaN + // summaries (Iceberg spec). Those cases prune here and never reach + // all_literals_outside_bounds. if field.lower_bound.is_none() { return ROWS_CANNOT_MATCH; } @@ -409,20 +412,16 @@ impl BoundPredicateVisitor for ManifestFilterVisitor<'_> { return ROWS_MIGHT_MATCH; } - if let Some(lower_bound) = &field.lower_bound { - let lower_bound = - ManifestFilterVisitor::bytes_to_datum(lower_bound, &reference.field().field_type); - if literals.iter().all(|datum| &lower_bound > datum) { - return ROWS_CANNOT_MATCH; - } - } + let lower_bound = field.lower_bound.as_ref().map(|bound| { + ManifestFilterVisitor::bytes_to_datum(bound, reference.field().field_type.as_ref()) + }); + let upper_bound = field.upper_bound.as_ref().map(|bound| { + ManifestFilterVisitor::bytes_to_datum(bound, reference.field().field_type.as_ref()) + }); - if let Some(upper_bound) = &field.upper_bound { - let upper_bound = - ManifestFilterVisitor::bytes_to_datum(upper_bound, &reference.field().field_type); - if literals.iter().all(|datum| &upper_bound < datum) { - return ROWS_CANNOT_MATCH; - } + if super::all_literals_outside_bounds(lower_bound.as_ref(), upper_bound.as_ref(), literals) + { + return ROWS_CANNOT_MATCH; } ROWS_MIGHT_MATCH @@ -1371,6 +1370,30 @@ mod test { Ok(()) } + #[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(()) + } + #[test] fn test_not_in() -> Result<()> { let case_sensitive = true; diff --git a/crates/iceberg/src/expr/visitors/mod.rs b/crates/iceberg/src/expr/visitors/mod.rs index c5aca6838..2fe92340b 100644 --- a/crates/iceberg/src/expr/visitors/mod.rs +++ b/crates/iceberg/src/expr/visitors/mod.rs @@ -15,6 +15,10 @@ // specific language governing permissions and limitations // under the License. +use fnv::FnvHashSet; + +use crate::spec::Datum; + pub(crate) mod bloom_filter_evaluator; pub(crate) mod bound_predicate_visitor; pub(crate) mod expression_evaluator; @@ -27,3 +31,126 @@ pub(crate) mod rewrite_not; pub(crate) mod row_group_metrics_evaluator; pub(crate) mod strict_metrics_evaluator; pub(crate) mod strict_projection; + +/// Returns true if every literal is provably outside the inclusive `[lower, upper]` +/// range, so rows cannot match. Missing bounds are treated as unbounded on that side. +/// +/// Returns false when there are no bounds, or when a literal does not compare +/// with a bound. Incomparable values must not be pruned. +pub(crate) fn all_literals_outside_bounds( + lower: Option<&Datum>, + upper: Option<&Datum>, + literals: &FnvHashSet<Datum>, +) -> bool { + match (lower, upper) { + (Some(lower), Some(upper)) => literals + .iter() + .all(|datum| datum.lt(lower) || datum.gt(upper)), + (Some(lower), None) => literals.iter().all(|datum| datum.lt(lower)), + (None, Some(upper)) => literals.iter().all(|datum| datum.gt(upper)), + (None, None) => false, + } +} + +/// Drops a NaN bound so that side is treated as unbounded. +/// +/// A NaN min or max is unreliable, but the other bound may still prune. +/// Inclusive evaluators in Java and PyIceberg bail to might-match when +/// either bound is NaN. Dropping only the NaN side is a deliberate +/// divergence: `total_cmp` treats NaN as the maximum, so the remaining +/// finite bound is still a valid prune. +pub(crate) fn finite_bound(bound: Option<&Datum>) -> Option<&Datum> { + bound.filter(|datum| !datum.is_nan()) +} + +#[cfg(test)] +mod tests { + use super::*; + + fn floats(vals: &[f32]) -> FnvHashSet<Datum> { + vals.iter().copied().map(Datum::float).collect() + } + + #[test] + fn both_bounds_require_a_literal_inside_the_range() { + let lower = Datum::float(4.0_f32); + let upper = Datum::float(6.0_f32); + assert!(all_literals_outside_bounds( + Some(&lower), + Some(&upper), + &floats(&[2.0, 8.0]) + )); + assert!(!all_literals_outside_bounds( + Some(&lower), + Some(&upper), + &floats(&[2.0, 5.0]) + )); + } + + #[test] + fn lower_only_prunes_literals_below_the_bound() { + let lower = Datum::float(4.0_f32); + assert!(all_literals_outside_bounds( + Some(&lower), + None, + &floats(&[2.0, 3.0]) + )); + assert!(!all_literals_outside_bounds( + Some(&lower), + None, + &floats(&[2.0, 4.0]) + )); + } + + #[test] + fn upper_only_prunes_literals_above_the_bound() { + let upper = Datum::float(1.0_f32); + assert!(all_literals_outside_bounds( + None, + Some(&upper), + &floats(&[2.0, 3.0]) + )); + assert!(!all_literals_outside_bounds( + None, + Some(&upper), + &floats(&[0.5, 3.0]) + )); + } + + #[test] + fn neither_bound_cannot_prune() { + assert!(!all_literals_outside_bounds( + None, + None, + &floats(&[2.0, 3.0]) + )); + } + + #[test] + fn incomparable_literal_blocks_pruning() { + let lower = Datum::int(1); + let upper = Datum::int(3); + let string_only: FnvHashSet<Datum> = [Datum::string("a")].into_iter().collect(); + assert!(!all_literals_outside_bounds( + Some(&lower), + Some(&upper), + &string_only + )); + + let mixed: FnvHashSet<Datum> = [Datum::int(0), Datum::string("a")].into_iter().collect(); + assert!(!all_literals_outside_bounds( + Some(&lower), + Some(&upper), + &mixed + )); + } + + #[test] + fn finite_bound_drops_nan() { + let nan = Datum::float(f32::NAN); + let finite = Datum::float(4.0_f32); + assert!(finite_bound(Some(&nan)).is_none()); + assert_eq!(finite_bound(Some(&finite)), Some(&finite)); + assert!(finite_bound(None).is_none()); + } +} diff --git a/crates/iceberg/src/expr/visitors/row_group_metrics_evaluator.rs b/crates/iceberg/src/expr/visitors/row_group_metrics_evaluator.rs index d07d922dd..ea3e13595 100644 --- a/crates/iceberg/src/expr/visitors/row_group_metrics_evaluator.rs +++ b/crates/iceberg/src/expr/visitors/row_group_metrics_evaluator.rs @@ -500,29 +500,17 @@ impl BoundPredicateVisitor for RowGroupMetricsEvaluator<'_> { let Some((stats, primitive_type)) = self.stats_and_type_for_field_id(field_id)? else { return ROW_GROUP_MIGHT_MATCH; }; - - if let Some(lower_bound) = get_parquet_stat_min_as_datum(&primitive_type, stats)? { - if lower_bound.is_nan() { - // NaN indicates unreliable bounds. See the InclusiveMetricsEvaluator docs for more. - return ROW_GROUP_MIGHT_MATCH; - } - - if !literals.iter().any(|datum| datum.ge(&lower_bound)) { - // if all values are less than lower bound, rows cannot match. - return ROW_GROUP_CANT_MATCH; - } - } - - if let Some(upper_bound) = get_parquet_stat_max_as_datum(&primitive_type, stats)? { - if upper_bound.is_nan() { - // NaN indicates unreliable bounds. See the InclusiveMetricsEvaluator docs for more. - return ROW_GROUP_MIGHT_MATCH; - } - - if !literals.iter().any(|datum| datum.le(&upper_bound)) { - // if all values are greater than upper bound, rows cannot match. - return ROW_GROUP_CANT_MATCH; - } + let lower_bound = get_parquet_stat_min_as_datum(&primitive_type, stats)?; + let upper_bound = get_parquet_stat_max_as_datum(&primitive_type, stats)?; + + // A NaN bound is unreliable on that side only. Drop it to unbounded + // so a valid bound can still prune. See InclusiveMetricsEvaluator. + if super::all_literals_outside_bounds( + super::finite_bound(lower_bound.as_ref()), + super::finite_bound(upper_bound.as_ref()), + literals, + ) { + return ROW_GROUP_CANT_MATCH; } ROW_GROUP_MIGHT_MATCH @@ -1809,9 +1797,9 @@ mod tests { } #[test] - fn eval_true_for_lower_bound_is_nan_filter_is_in() -> Result<()> { - // TODO: should this be false, since the max stat - // is lower than the min val in the set? + fn eval_false_for_lower_bound_is_nan_all_literals_above_upper_is_in() -> Result<()> { + // NaN lower is treated as unbounded. The valid upper bound (1.0) + // still prunes IN (2.0, 3.0). let row_group_metadata = create_row_group_metadata( 1, 1, @@ -1839,7 +1827,7 @@ mod tests { iceberg_schema_ref.as_ref(), )?; - assert!(result); + assert!(!result); Ok(()) } @@ -1903,6 +1891,76 @@ mod tests { Ok(()) } + #[test] + fn eval_false_for_nan_upper_bound_all_literals_below_lower_is_in() -> Result<()> { + // NaN upper is treated as unbounded. The valid lower bound (4.0) + // still prunes IN (2.0, 3.0). + let row_group_metadata = create_row_group_metadata( + 1, + 1, + Some(Statistics::float( + Some(4.0), + Some(f32::NAN), + None, + Some(0), + false, + )), + 1, + None, + )?; + + let (iceberg_schema_ref, field_id_map) = build_iceberg_schema_and_field_map()?; + + let filter = Reference::new("col_float") + .is_in([Datum::float(2.0_f32), Datum::float(3.0_f32)]) + .bind(iceberg_schema_ref.clone(), false)?; + + let result = RowGroupMetricsEvaluator::eval( + &filter, + &row_group_metadata, + &field_id_map, + iceberg_schema_ref.as_ref(), + )?; + + assert!(!result); + Ok(()) + } + + #[test] + fn eval_true_for_nan_lower_bound_literal_inside_upper_is_in() -> Result<()> { + // NaN lower is treated as unbounded. upper = 3.0 with IN (2.0, 4.0) + // must still match because 2.0 is inside the finite upper bound. + let row_group_metadata = create_row_group_metadata( + 1, + 1, + Some(Statistics::float( + Some(f32::NAN), + Some(3.0), + None, + Some(0), + false, + )), + 1, + None, + )?; + + let (iceberg_schema_ref, field_id_map) = build_iceberg_schema_and_field_map()?; + + let filter = Reference::new("col_float") + .is_in([Datum::float(2.0_f32), Datum::float(4.0_f32)]) + .bind(iceberg_schema_ref.clone(), false)?; + + let result = RowGroupMetricsEvaluator::eval( + &filter, + &row_group_metadata, + &field_id_map, + iceberg_schema_ref.as_ref(), + )?; + + assert!(result); + Ok(()) + } + #[test] fn eval_false_for_upper_bound_below_all_vals_is_in() -> Result<()> { let row_group_metadata = create_row_group_metadata( @@ -1936,6 +1994,41 @@ mod tests { Ok(()) } + #[test] + fn eval_false_for_literals_straddling_bounds_is_in() -> Result<()> { + // Bounds are [4.0, 6.0]; IN (2.0, 8.0) straddles the range with no + // literal inside it and must be pruned. + let row_group_metadata = create_row_group_metadata( + 1, + 1, + Some(Statistics::float( + Some(4.0), + Some(6.0), + None, + Some(0), + false, + )), + 1, + None, + )?; + + let (iceberg_schema_ref, field_id_map) = build_iceberg_schema_and_field_map()?; + + let filter = Reference::new("col_float") + .is_in([Datum::float(2.0_f32), Datum::float(8.0_f32)]) + .bind(iceberg_schema_ref.clone(), false)?; + + let result = RowGroupMetricsEvaluator::eval( + &filter, + &row_group_metadata, + &field_id_map, + iceberg_schema_ref.as_ref(), + )?; + + assert!(!result); + Ok(()) + } + #[test] fn eval_true_for_not_in() -> Result<()> { let row_group_metadata = create_row_group_metadata(
