Skip to content

Commit 2af7118

Browse files
committed
perf(datasource-parquet): evaluate Parquet Bloom filters incrementally during row group pruning
- Evaluate Bloom filters column-by-column incrementally to short-circuit multi-column pruning before loading remaining column filters. - Re-evaluate only newly loaded column guarantees to avoid redundant full-predicate tree evaluations. - Preserve upstream early-exit Done state when all row groups are pruned. - Add unit tests covering full matching, stats pruning, and I/O error fallback.
1 parent 06d618f commit 2af7118

3 files changed

Lines changed: 574 additions & 110 deletions

File tree

‎datafusion/datasource-parquet/src/bloom_filter.rs‎

Lines changed: 72 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,25 @@ impl BloomFilterStatistics {
8585
);
8686
}
8787

88+
/// Returns `true` if the Bloom filter definitely does not contain any of the given values.
89+
///
90+
/// If all values are confirmed absent by the Bloom filter, returns `true`.
91+
/// If any value might be present (or checking is unsupported), returns `false`.
92+
#[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key
93+
pub fn is_known_not_present(
94+
sbbf: &Sbbf,
95+
values: &HashSet<ScalarValue>,
96+
parquet_type: &Type,
97+
type_length: i32,
98+
) -> bool {
99+
if values.is_empty() {
100+
return false;
101+
}
102+
values
103+
.iter()
104+
.all(|value| !Self::check_scalar(sbbf, value, parquet_type, type_length))
105+
}
106+
88107
/// Helper function for checking if [`Sbbf`] filter contains [`ScalarValue`].
89108
///
90109
/// In case the type of scalar is not supported, returns `true`, assuming that the
@@ -209,20 +228,12 @@ impl PruningStatistics for BloomFilterStatistics {
209228
// positives (i.e. it might return true even if the value is not
210229
// present) however, the bloom filter will return `false` if the value is
211230
// definitely not present.
212-
213-
let known_not_present = values
214-
.iter()
215-
.map(|value| {
216-
BloomFilterStatistics::check_scalar(
217-
&column_bloom_filter.sbbf,
218-
value,
219-
&column_bloom_filter.physical_type,
220-
column_bloom_filter.type_length,
221-
)
222-
})
223-
// The row group doesn't contain any of the values if
224-
// all the checks are false
225-
.all(|v| !v);
231+
let known_not_present = Self::is_known_not_present(
232+
&column_bloom_filter.sbbf,
233+
values,
234+
&column_bloom_filter.physical_type,
235+
column_bloom_filter.type_length,
236+
);
226237

227238
let contains = if known_not_present {
228239
Some(false)
@@ -720,4 +731,51 @@ mod tests {
720731

721732
Ok(pruned_row_groups)
722733
}
734+
735+
#[test]
736+
#[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key
737+
fn test_is_known_not_present() {
738+
let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
739+
// 1. Empty values -> returns false
740+
assert!(!BloomFilterStatistics::is_known_not_present(
741+
&sbbf,
742+
&HashSet::new(),
743+
&Type::INT32,
744+
0,
745+
));
746+
747+
// 2. Insert 42
748+
sbbf.insert(&42_i32);
749+
750+
// Value 42 is present -> is_known_not_present should be false
751+
let mut present_set = HashSet::new();
752+
present_set.insert(ScalarValue::Int32(Some(42)));
753+
assert!(!BloomFilterStatistics::is_known_not_present(
754+
&sbbf,
755+
&present_set,
756+
&Type::INT32,
757+
0,
758+
));
759+
760+
// Value 99 is absent -> is_known_not_present should be true
761+
let mut absent_set = HashSet::new();
762+
absent_set.insert(ScalarValue::Int32(Some(99)));
763+
assert!(BloomFilterStatistics::is_known_not_present(
764+
&sbbf,
765+
&absent_set,
766+
&Type::INT32,
767+
0,
768+
));
769+
770+
// Mixed set containing present and absent -> is_known_not_present should be false
771+
let mut mixed_set = HashSet::new();
772+
mixed_set.insert(ScalarValue::Int32(Some(42)));
773+
mixed_set.insert(ScalarValue::Int32(Some(99)));
774+
assert!(!BloomFilterStatistics::is_known_not_present(
775+
&sbbf,
776+
&mixed_set,
777+
&Type::INT32,
778+
0,
779+
));
780+
}
723781
}

0 commit comments

Comments
 (0)