You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iceberg.apache.org by gi...@apache.org on 2026/09/15 20:17:42 UTC
(iceberg-rust) 01/01: feat: bloom filter pushdown (#2398)
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-2398-930c10298e43daeb7316b20b83049e9f724ae58c
in repository https://gitbox.apache.org/repos/asf/iceberg-rust.git
commit 8193cce4b3cfe4608738cdf36e0ddf74a15a415b
Author: Xander <za...@googlemail.com>
AuthorDate: Tue Sep 15 20:17:20 2026 +0000
feat: bloom filter pushdown (#2398)
* feat: bloom filter pushdown
* test
* avoid copy
* new name
* fmt
* doc string
* handle type widening
* widen decimals
* pub crate
* full import
* lifetime
* log
* add not supported comment
* make it more safe
* Add tests
* fix
* fmt
* don't read not predicates
* tests
* remove boolean
* doc
* update 0 test
* UUID
* update comment
* update test doc
---
crates/iceberg/public-api.txt | 2 +
crates/iceberg/src/arrow/reader/mod.rs | 19 +
crates/iceberg/src/arrow/reader/pipeline.rs | 102 ++
crates/iceberg/src/arrow/reader/row_filter.rs | 479 +++++-
.../src/expr/visitors/bloom_filter_evaluator.rs | 1615 ++++++++++++++++++++
crates/iceberg/src/expr/visitors/mod.rs | 1 +
crates/iceberg/src/scan/mod.rs | 22 +-
crates/iceberg/src/spec/values/decimal_utils.rs | 100 ++
8 files changed, 2338 insertions(+), 2 deletions(-)
diff --git a/crates/iceberg/public-api.txt b/crates/iceberg/public-api.txt
index 9ba84036b..7d03d6b1f 100644
--- a/crates/iceberg/public-api.txt
+++ b/crates/iceberg/public-api.txt
@@ -72,6 +72,7 @@ impl iceberg::arrow::ArrowReaderBuilder
pub fn iceberg::arrow::ArrowReaderBuilder::build(self) -> iceberg::arrow::ArrowReader
pub fn iceberg::arrow::ArrowReaderBuilder::new(file_io: iceberg::io::FileIO, runtime: iceberg::Runtime) -> Self
pub fn iceberg::arrow::ArrowReaderBuilder::with_batch_size(self, batch_size: usize) -> Self
+pub fn iceberg::arrow::ArrowReaderBuilder::with_bloom_filter_enabled(self, bloom_filter_enabled: bool) -> Self
pub fn iceberg::arrow::ArrowReaderBuilder::with_data_file_concurrency_limit(self, val: usize) -> Self
pub fn iceberg::arrow::ArrowReaderBuilder::with_metadata_size_hint(self, metadata_size_hint: usize) -> Self
pub fn iceberg::arrow::ArrowReaderBuilder::with_range_coalesce_bytes(self, range_coalesce_bytes: u64) -> Self
@@ -1363,6 +1364,7 @@ pub fn iceberg::scan::TableScanBuilder<'a>::select_all(self) -> Self
pub fn iceberg::scan::TableScanBuilder<'a>::select_empty(self) -> Self
pub fn iceberg::scan::TableScanBuilder<'a>::snapshot_id(self, snapshot_id: i64) -> Self
pub fn iceberg::scan::TableScanBuilder<'a>::with_batch_size(self, batch_size: core::option::Option<usize>) -> Self
+pub fn iceberg::scan::TableScanBuilder<'a>::with_bloom_filter_enabled(self, bloom_filter_enabled: bool) -> Self
pub fn iceberg::scan::TableScanBuilder<'a>::with_case_sensitive(self, case_sensitive: bool) -> Self
pub fn iceberg::scan::TableScanBuilder<'a>::with_concurrency_limit(self, limit: usize) -> Self
pub fn iceberg::scan::TableScanBuilder<'a>::with_data_file_concurrency_limit(self, limit: usize) -> Self
diff --git a/crates/iceberg/src/arrow/reader/mod.rs b/crates/iceberg/src/arrow/reader/mod.rs
index 495283f47..9d9c8be48 100644
--- a/crates/iceberg/src/arrow/reader/mod.rs
+++ b/crates/iceberg/src/arrow/reader/mod.rs
@@ -57,6 +57,7 @@ pub struct ArrowReaderBuilder {
concurrency_limit_data_files: usize,
row_group_filtering_enabled: bool,
row_selection_enabled: bool,
+ bloom_filter_enabled: bool,
parquet_read_options: ParquetReadOptions,
runtime: Runtime,
}
@@ -72,6 +73,7 @@ impl ArrowReaderBuilder {
concurrency_limit_data_files: num_cpus,
row_group_filtering_enabled: true,
row_selection_enabled: false,
+ bloom_filter_enabled: false,
parquet_read_options: ParquetReadOptions::builder().build(),
runtime,
}
@@ -102,6 +104,21 @@ impl ArrowReaderBuilder {
self
}
+ /// Determines whether to enable bloom filter-based row group filtering.
+ ///
+ /// When enabled, if a read is performed with an equality or IN predicate,
+ /// the bloom filter for relevant columns in each row group is read and
+ /// checked. Row groups where the bloom filter proves the value is absent
+ /// are skipped entirely.
+ ///
+ /// Defaults to disabled. Each bloom filter is a separate read, and they are
+ /// issued serially — one round trip per relevant column per row group, before
+ /// any data is read. TODO(#3191)
+ pub fn with_bloom_filter_enabled(mut self, bloom_filter_enabled: bool) -> Self {
+ self.bloom_filter_enabled = bloom_filter_enabled;
+ self
+ }
+
/// Provide a hint as to the number of bytes to prefetch for parsing the Parquet metadata
///
/// This hint can help reduce the number of fetch requests. For more details see the
@@ -141,6 +158,7 @@ impl ArrowReaderBuilder {
concurrency_limit_data_files: self.concurrency_limit_data_files,
row_group_filtering_enabled: self.row_group_filtering_enabled,
row_selection_enabled: self.row_selection_enabled,
+ bloom_filter_enabled: self.bloom_filter_enabled,
parquet_read_options: self.parquet_read_options,
}
}
@@ -158,5 +176,6 @@ pub struct ArrowReader {
row_group_filtering_enabled: bool,
row_selection_enabled: bool,
+ bloom_filter_enabled: bool,
parquet_read_options: ParquetReadOptions,
}
diff --git a/crates/iceberg/src/arrow/reader/pipeline.rs b/crates/iceberg/src/arrow/reader/pipeline.rs
index 5354c7204..7ec9bf4d5 100644
--- a/crates/iceberg/src/arrow/reader/pipeline.rs
+++ b/crates/iceberg/src/arrow/reader/pipeline.rs
@@ -44,6 +44,10 @@ use crate::arrow::record_batch_transformer::RecordBatchTransformerBuilder;
use crate::arrow::scan_metrics::{CountingFileRead, ScanMetrics, ScanResult};
use crate::encryption::StandardKeyMetadata;
use crate::error::Result;
+use crate::expr::BoundPredicate;
+use crate::expr::visitors::bloom_filter_evaluator::{
+ BloomFilterEvaluator, ColumnBloomFilter, collect_bloom_filter_field_ids,
+};
use crate::io::{FileIO, FileMetadata, FileRead};
use crate::metadata_columns::{
RESERVED_COL_NAME_LAST_UPDATED_SEQUENCE_NUMBER, RESERVED_COL_NAME_POS,
@@ -70,6 +74,7 @@ impl ArrowReader {
.with_scan_metrics(scan_metrics.clone()),
row_group_filtering_enabled: self.row_group_filtering_enabled,
row_selection_enabled: self.row_selection_enabled,
+ bloom_filter_enabled: self.bloom_filter_enabled,
parquet_read_options: self.parquet_read_options,
scan_metrics: scan_metrics.clone(),
};
@@ -123,6 +128,7 @@ struct FileScanTaskReader {
delete_file_loader: CachingDeleteFileLoader,
row_group_filtering_enabled: bool,
row_selection_enabled: bool,
+ bloom_filter_enabled: bool,
parquet_read_options: ParquetReadOptions,
scan_metrics: ScanMetrics,
}
@@ -632,6 +638,30 @@ impl FileScanTaskReader {
};
}
+ if self.bloom_filter_enabled {
+ let all_rgs;
+ let candidate_rgs = match &selected_row_group_indices {
+ Some(indices) => indices.as_slice(),
+ None => {
+ all_rgs = (0..record_batch_stream_builder.metadata().num_row_groups())
+ .collect::<Vec<_>>();
+ &all_rgs
+ }
+ };
+
+ let bloom_filtered = Self::filter_row_groups_by_bloom_filter(
+ &predicate,
+ &mut record_batch_stream_builder,
+ candidate_rgs,
+ &field_id_map,
+ )
+ .await?;
+
+ if bloom_filtered.len() < candidate_rgs.len() {
+ selected_row_group_indices = Some(bloom_filtered);
+ }
+ }
+
if self.row_selection_enabled {
row_selection = ArrowReader::get_row_selection_for_filter_predicate(
&predicate,
@@ -692,6 +722,78 @@ impl FileScanTaskReader {
Ok(Box::pin(record_batch_stream) as ArrowRecordBatchStream)
}
+
+ /// Reads bloom filters for relevant columns and evaluates the predicate
+ /// against them to filter out row groups that definitely don't match.
+ async fn filter_row_groups_by_bloom_filter(
+ predicate: &BoundPredicate,
+ builder: &mut ParquetRecordBatchStreamBuilder<ArrowFileReader>,
+ candidate_row_groups: &[usize],
+ field_id_map: &HashMap<i32, usize>,
+ ) -> Result<Vec<usize>> {
+ // Only collect field IDs from eq/in predicates — the only types
+ // bloom filters can help with. Skip columns not in the parquet schema.
+ let bloom_filter_field_ids: Vec<i32> = collect_bloom_filter_field_ids(predicate)?
+ .into_iter()
+ .filter(|id| field_id_map.contains_key(id))
+ .collect();
+
+ if bloom_filter_field_ids.is_empty() {
+ return Ok(candidate_row_groups.to_vec());
+ }
+
+ let mut result = Vec::with_capacity(candidate_row_groups.len());
+
+ for &rg_idx in candidate_row_groups {
+ let mut bloom_filters: HashMap<i32, ColumnBloomFilter> = HashMap::new();
+
+ for &field_id in &bloom_filter_field_ids {
+ let col_idx = field_id_map[&field_id];
+ let col_meta = builder.metadata().row_group(rg_idx).column(col_idx);
+
+ // Only attempt to load if this column chunk actually has a bloom filter
+ if col_meta.bloom_filter_offset().is_none() {
+ continue;
+ }
+
+ let physical_type = col_meta.column_type();
+ let type_length = col_meta.column_descr().type_length();
+
+ match builder
+ .get_row_group_column_bloom_filter(rg_idx, col_idx)
+ .await
+ {
+ Ok(Some(sbbf)) => {
+ bloom_filters.insert(
+ field_id,
+ ColumnBloomFilter::new(sbbf, physical_type, type_length),
+ );
+ }
+ Ok(None) => {}
+ Err(e) => {
+ // Left absent from the map, so the evaluator treats the column
+ // as might-match and the row group survives.
+ tracing::debug!(
+ "Bloom filter for field {field_id} in row group {rg_idx} could not be read: {e}"
+ );
+ }
+ }
+ }
+
+ match BloomFilterEvaluator::eval(predicate, &bloom_filters) {
+ Ok(true) => result.push(rg_idx),
+ Ok(false) => { /* Row group pruned by bloom filter */ }
+ Err(e) => {
+ tracing::debug!(
+ "Bloom filter evaluation failed for row group {rg_idx}, including it: {e}"
+ );
+ result.push(rg_idx);
+ }
+ }
+ }
+
+ Ok(result)
+ }
}
impl ArrowReader {
diff --git a/crates/iceberg/src/arrow/reader/row_filter.rs b/crates/iceberg/src/arrow/reader/row_filter.rs
index 389231c46..34b739113 100644
--- a/crates/iceberg/src/arrow/reader/row_filter.rs
+++ b/crates/iceberg/src/arrow/reader/row_filter.rs
@@ -217,7 +217,8 @@ mod tests {
use arrow_array::cast::AsArray;
use arrow_array::{
- ArrayRef, Int32Array, Int64Array, LargeStringArray, RecordBatch, StringArray,
+ ArrayRef, Decimal128Array, Float32Array, Int32Array, Int64Array, LargeStringArray,
+ RecordBatch, StringArray,
};
use arrow_schema::{DataType, Field, Schema as ArrowSchema};
use futures::TryStreamExt;
@@ -1280,4 +1281,480 @@ mod tests {
"positional deletes must be applied correctly even when page indexes are absent"
);
}
+
+ // Bloom filter pushdown: on-vs-off equivalence
+ // Pushdown must never change results. An encoding bug in the probe shows up as
+ // rows the bloom filter drops and the row filter keeps, so every case below
+ // reads the same file twice and compares. Fixtures spread each row group's
+ // values across the whole domain, so min/max statistics cannot prune and any
+ // reduction in bytes read is attributable to the bloom filter.
+
+ const ROWS_PER_GROUP: i32 = 20_000;
+ const GROUPS: i32 = 3;
+ /// Gap between consecutive values in a row group, so a value can be absent from
+ /// the file yet still sit inside every row group's min/max range.
+ const STRIDE: i32 = 30;
+
+ /// The `i`th value of row group `group`, spread across the whole domain.
+ fn interleaved(group: i32, i: i32) -> i32 {
+ i * STRIDE + group
+ }
+
+ fn field_with_id(name: &str, ty: DataType, id: i32) -> Field {
+ Field::new(name, ty, false).with_metadata(HashMap::from([(
+ PARQUET_FIELD_ID_META_KEY.to_string(),
+ id.to_string(),
+ )]))
+ }
+
+ /// Writes one row group per batch, optionally with bloom filters.
+ fn write_row_groups(
+ path: &str,
+ arrow_schema: Arc<ArrowSchema>,
+ row_groups: Vec<RecordBatch>,
+ with_bloom_filters: bool,
+ ) {
+ let mut props = WriterProperties::builder().set_compression(Compression::UNCOMPRESSED);
+ if with_bloom_filters {
+ props = props
+ .set_bloom_filter_enabled(true)
+ .set_bloom_filter_max_ndv(ROWS_PER_GROUP as u64);
+ }
+
+ let file = File::create(path).unwrap();
+ let mut writer = ArrowWriter::try_new(file, arrow_schema, Some(props.build())).unwrap();
+ for batch in row_groups {
+ writer.write(&batch).unwrap();
+ // Force a row group boundary so each batch is independently prunable.
+ writer.flush().unwrap();
+ }
+ writer.close().unwrap();
+ }
+
+ async fn read_once(
+ file_path: &str,
+ schema: Arc<Schema>,
+ project_field_ids: Vec<i32>,
+ predicate: Predicate,
+ bloom_enabled: bool,
+ ) -> (Vec<RecordBatch>, u64) {
+ let file_io = FileIO::new_with_fs();
+ let reader = ArrowReaderBuilder::new(file_io, Runtime::current())
+ .with_bloom_filter_enabled(bloom_enabled)
+ // Keep the fixed footer prefetch small so the byte measurement reflects
+ // row group I/O rather than a constant metadata read.
+ .with_metadata_size_hint(8 * 1024)
+ .build();
+
+ let task = FileScanTask::builder()
+ .with_file_size_in_bytes(std::fs::metadata(file_path).unwrap().len())
+ .with_start(0)
+ .with_length(0)
+ .with_data_file_path(file_path.to_string())
+ .with_data_file_format(DataFileFormat::Parquet)
+ .with_schema(schema.clone())
+ .with_project_field_ids(project_field_ids)
+ .with_predicate(Some(predicate.bind(schema, true).unwrap()))
+ .with_case_sensitive(false)
+ .build()
+ .unwrap();
+
+ let tasks = Box::pin(futures::stream::iter(vec![Ok(task)])) as FileScanTaskStream;
+ let result = reader.read(tasks).unwrap();
+ let metrics = result.metrics().clone();
+ let batches: Vec<RecordBatch> = result.stream().try_collect().await.unwrap();
+
+ (batches, metrics.bytes_read())
+ }
+
+ /// Batch boundaries differ when fewer row groups are read, so collapse to a
+ /// single batch before comparing. `None` means no rows at all.
+ fn collapse(batches: &[RecordBatch]) -> Option<RecordBatch> {
+ let first = batches.first()?;
+ Some(arrow_select::concat::concat_batches(&first.schema(), batches).unwrap())
+ }
+
+ /// Reads the file with pushdown on and off, asserts the rows are identical, and
+ /// returns the rows plus (bytes_on, bytes_off).
+ async fn assert_pushdown_agrees(
+ case: &str,
+ file_path: &str,
+ schema: Arc<Schema>,
+ project_field_ids: Vec<i32>,
+ predicate: Predicate,
+ ) -> (Option<RecordBatch>, u64, u64) {
+ let (off, bytes_off) = read_once(
+ file_path,
+ schema.clone(),
+ project_field_ids.clone(),
+ predicate.clone(),
+ false,
+ )
+ .await;
+ let (on, bytes_on) = read_once(file_path, schema, project_field_ids, predicate, true).await;
+
+ let off = collapse(&off);
+ let on = collapse(&on);
+ assert_eq!(
+ on, off,
+ "{case}: bloom filter pushdown changed the rows returned"
+ );
+
+ (on, bytes_on, bytes_off)
+ }
+
+ fn rows(batch: &Option<RecordBatch>) -> usize {
+ batch.as_ref().map_or(0, |b| b.num_rows())
+ }
+
+ fn value_schema(iceberg_type: Type) -> Arc<Schema> {
+ Arc::new(
+ Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![NestedField::required(1, "v", iceberg_type).into()])
+ .build()
+ .unwrap(),
+ )
+ }
+
+ /// Writes a single-column file, one row group per group index.
+ fn write_value_fixture(
+ path: &str,
+ data_type: DataType,
+ make_group: impl Fn(i32) -> ArrayRef,
+ with_bloom_filters: bool,
+ ) {
+ let arrow_schema = Arc::new(ArrowSchema::new(vec![field_with_id("v", data_type, 1)]));
+ let row_groups = (0..GROUPS)
+ .map(|g| RecordBatch::try_new(arrow_schema.clone(), vec![make_group(g)]).unwrap())
+ .collect();
+ write_row_groups(path, arrow_schema, row_groups, with_bloom_filters);
+ }
+
+ /// The core check for one physical encoding: a value that is present must
+ /// survive pushdown, and one that is absent must prune every row group. The
+ /// first catches a probe that encodes wrongly and drops real rows; the second
+ /// catches a probe that silently never prunes.
+ async fn assert_prunes_and_agrees(
+ case: &str,
+ file_path: &str,
+ schema: Arc<Schema>,
+ present: Datum,
+ absent: Datum,
+ ) {
+ let (on, bytes_on, bytes_off) = assert_pushdown_agrees(
+ &format!("{case}/present"),
+ file_path,
+ schema.clone(),
+ vec![1],
+ Reference::new("v").equal_to(present),
+ )
+ .await;
+ assert_eq!(rows(&on), 1, "{case}/present: expected one matching row");
+ assert!(
+ bytes_on < bytes_off,
+ "{case}/present: pushdown must skip row groups: {bytes_on} vs {bytes_off}"
+ );
+
+ let (on, bytes_on, bytes_off) = assert_pushdown_agrees(
+ &format!("{case}/absent"),
+ file_path,
+ schema,
+ vec![1],
+ Reference::new("v").equal_to(absent),
+ )
+ .await;
+ assert_eq!(rows(&on), 0, "{case}/absent: expected no matching rows");
+ assert!(
+ bytes_on * 2 < bytes_off,
+ "{case}/absent: pruning every row group should cut reads sharply: \
+ {bytes_on} vs {bytes_off}"
+ );
+ }
+
+ /// Value present in exactly one row group: `interleaved(1, 51)`.
+ const PRESENT_INT: i32 = 51 * STRIDE + 1;
+ /// Not congruent to any group index mod STRIDE, so absent from the file while
+ /// still inside every row group's min/max range.
+ const ABSENT_INT: i32 = 7;
+
+ fn int_group(g: i32) -> ArrayRef {
+ Arc::new(Int32Array::from(
+ (0..ROWS_PER_GROUP)
+ .map(|i| interleaved(g, i))
+ .collect::<Vec<_>>(),
+ ))
+ }
+
+ #[tokio::test]
+ async fn test_bloom_pushdown_int32_eq() {
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/int32.parquet", tmp.path().to_str().unwrap());
+ write_value_fixture(&path, DataType::Int32, int_group, true);
+
+ assert_prunes_and_agrees(
+ "int32",
+ &path,
+ value_schema(Type::Primitive(PrimitiveType::Int)),
+ Datum::int(PRESENT_INT),
+ Datum::int(ABSENT_INT),
+ )
+ .await;
+ }
+
+ /// `IN` takes a different evaluator path from `eq`: it must keep the row group
+ /// when any literal might be present, and prune only when all are absent.
+ #[tokio::test]
+ async fn test_bloom_pushdown_int32_in() {
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/int32_in.parquet", tmp.path().to_str().unwrap());
+ write_value_fixture(&path, DataType::Int32, int_group, true);
+ let schema = value_schema(Type::Primitive(PrimitiveType::Int));
+
+ // One present literal keeps its row group; the absent one must not suppress it.
+ let (on, bytes_on, bytes_off) = assert_pushdown_agrees(
+ "int32_in/mixed",
+ &path,
+ schema.clone(),
+ vec![1],
+ Reference::new("v").is_in([Datum::int(PRESENT_INT), Datum::int(ABSENT_INT)]),
+ )
+ .await;
+ assert_eq!(rows(&on), 1);
+ assert!(bytes_on < bytes_off, "{bytes_on} vs {bytes_off}");
+
+ // All literals absent: every row group prunes.
+ let (on, bytes_on, bytes_off) = assert_pushdown_agrees(
+ "int32_in/all_absent",
+ &path,
+ schema,
+ vec![1],
+ Reference::new("v").is_in([Datum::int(ABSENT_INT), Datum::int(ABSENT_INT + 1)]),
+ )
+ .await;
+ assert_eq!(rows(&on), 0);
+ assert!(bytes_on * 2 < bytes_off, "{bytes_on} vs {bytes_off}");
+ }
+
+ #[tokio::test]
+ async fn test_bloom_pushdown_string_eq() {
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/string.parquet", tmp.path().to_str().unwrap());
+ write_value_fixture(
+ &path,
+ DataType::Utf8,
+ |g| {
+ Arc::new(StringArray::from(
+ (0..ROWS_PER_GROUP)
+ .map(|i| format!("{:016}", interleaved(g, i)))
+ .collect::<Vec<_>>(),
+ ))
+ },
+ true,
+ );
+
+ assert_prunes_and_agrees(
+ "string",
+ &path,
+ value_schema(Type::Primitive(PrimitiveType::String)),
+ Datum::string(format!("{PRESENT_INT:016}")),
+ Datum::string(format!("{ABSENT_INT:016}")),
+ )
+ .await;
+ }
+
+ /// Decimal precision decides the Parquet physical type, and the probe has to be
+ /// encoded to match: precision 9 -> INT32, 15 -> INT64, 25 -> FIXED_LEN_BYTE_ARRAY.
+ /// Each width is a separate arm of `check_in_bloom_filter`.
+ async fn check_decimal_width(name: &str, precision: u32) {
+ const SCALE: u32 = 2;
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/{name}.parquet", tmp.path().to_str().unwrap());
+
+ write_value_fixture(
+ &path,
+ DataType::Decimal128(precision as u8, SCALE as i8),
+ |g| {
+ let values: Vec<i128> = (0..ROWS_PER_GROUP)
+ .map(|i| i128::from(interleaved(g, i)))
+ .collect();
+ Arc::new(
+ Decimal128Array::from(values)
+ .with_precision_and_scale(precision as u8, SCALE as i8)
+ .unwrap(),
+ )
+ },
+ true,
+ );
+
+ let datum = |mantissa: i32| {
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(
+ i128::from(mantissa),
+ SCALE,
+ ),
+ precision,
+ )
+ .unwrap()
+ };
+
+ assert_prunes_and_agrees(
+ name,
+ &path,
+ value_schema(Type::Primitive(PrimitiveType::Decimal {
+ precision,
+ scale: SCALE,
+ })),
+ datum(PRESENT_INT),
+ datum(ABSENT_INT),
+ )
+ .await;
+ }
+
+ #[tokio::test]
+ async fn test_bloom_pushdown_decimal_int32() {
+ check_decimal_width("decimal_int32", 9).await;
+ }
+
+ #[tokio::test]
+ async fn test_bloom_pushdown_decimal_int64() {
+ check_decimal_width("decimal_int64", 15).await;
+ }
+
+ #[tokio::test]
+ async fn test_bloom_pushdown_decimal_fixed_len_byte_array() {
+ check_decimal_width("decimal_flba", 25).await;
+ }
+
+ /// Widening a decimal's precision does not rewrite existing files, so the file
+ /// keeps its original physical width while the bound literal arrives at the new
+ /// precision. Deriving the probe encoding from the schema instead of the file
+ /// would miss every entry the writer inserted and prune matching row groups.
+ #[tokio::test]
+ async fn test_bloom_pushdown_decimal_widened_precision() {
+ const SCALE: u32 = 2;
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/decimal_widened.parquet", tmp.path().to_str().unwrap());
+
+ // File written at precision 9 -> INT32.
+ write_value_fixture(
+ &path,
+ DataType::Decimal128(9, SCALE as i8),
+ |g| {
+ let values: Vec<i128> = (0..ROWS_PER_GROUP)
+ .map(|i| i128::from(interleaved(g, i)))
+ .collect();
+ Arc::new(
+ Decimal128Array::from(values)
+ .with_precision_and_scale(9, SCALE as i8)
+ .unwrap(),
+ )
+ },
+ true,
+ );
+
+ // Table schema has since widened to precision 30.
+ let schema = value_schema(Type::Primitive(PrimitiveType::Decimal {
+ precision: 30,
+ scale: SCALE,
+ }));
+ let datum = |mantissa: i32| {
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(
+ i128::from(mantissa),
+ SCALE,
+ ),
+ 30,
+ )
+ .unwrap()
+ };
+
+ assert_prunes_and_agrees(
+ "decimal_widened",
+ &path,
+ schema,
+ datum(PRESENT_INT),
+ datum(ABSENT_INT),
+ )
+ .await;
+ }
+
+ /// `Sbbf` hashes raw IEEE bytes, so `-0.0` and `0.0` are distinct entries. Arrow's
+ /// float equality is bitwise too, for an independent reason: `ArrowNativeTypeOp::is_eq`
+ /// implements total-order (`total_cmp`) semantics as `to_bits() == to_bits()`, so
+ /// `-0.0 != 0.0` and `NaN == NaN` there. That agreement is what makes it safe to prune
+ /// a row group holding only the opposite zero: if `is_eq` ever became IEEE-lenient,
+ /// those pruned rows would be rows the row filter should have returned. A probe that
+ /// canonicalized the sign instead only over-keeps, costing pruning rather than
+ /// correctness — but it would also hide such a change from this test.
+ ///
+ /// Each row group pairs its zero with a larger filler value so its min/max range spans
+ /// the other zero. Neither statistics path can prune it, so the bloom-off read really
+ /// does evaluate `is_eq` against `ROWS_PER_GROUP - 1` copies of the opposite zero: that
+ /// arm is the control pinning arrow's semantics, and IEEE-lenient equality would double
+ /// the row count it returns. Pairing with a filler also avoids relying on the writer
+ /// widening a single-value group's bounds to `[-0.0, +0.0]`.
+ #[tokio::test]
+ async fn test_bloom_pushdown_float_signed_zero() {
+ const FILLER: f32 = 5.0;
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/float_zero.parquet", tmp.path().to_str().unwrap());
+
+ // Row group 0 holds -0.0 and never +0.0; row group 1 the reverse; row group 2
+ // neither zero.
+ write_value_fixture(
+ &path,
+ DataType::Float32,
+ |g| {
+ let zero = match g {
+ 0 => -0.0f32,
+ 1 => 0.0f32,
+ _ => 7.5f32,
+ };
+ let mut values = vec![zero; ROWS_PER_GROUP as usize - 1];
+ values.push(FILLER);
+ Arc::new(Float32Array::from(values))
+ },
+ true,
+ );
+
+ let schema = value_schema(Type::Primitive(PrimitiveType::Float));
+ let zero_rows = ROWS_PER_GROUP as usize - 1;
+
+ for (label, probe) in [("positive_zero", 0.0f32), ("negative_zero", -0.0f32)] {
+ let (on, _, _) = assert_pushdown_agrees(
+ label,
+ &path,
+ schema.clone(),
+ vec![1],
+ Reference::new("v").equal_to(Datum::float(probe)),
+ )
+ .await;
+ // Only the group holding this exact zero matches, on both paths.
+ assert_eq!(
+ rows(&on),
+ zero_rows,
+ "{label}: expected only the row group holding this zero to match"
+ );
+ }
+ }
+
+ /// A file with no bloom filters at all must read identically with the option on,
+ /// exercising the conservative might-match path end to end.
+ #[tokio::test]
+ async fn test_bloom_pushdown_file_without_bloom_filters() {
+ let tmp = TempDir::new().unwrap();
+ let path = format!("{}/no_filters.parquet", tmp.path().to_str().unwrap());
+ write_value_fixture(&path, DataType::Int32, int_group, false);
+
+ let (on, _, _) = assert_pushdown_agrees(
+ "no_filters",
+ &path,
+ value_schema(Type::Primitive(PrimitiveType::Int)),
+ vec![1],
+ Reference::new("v").equal_to(Datum::int(PRESENT_INT)),
+ )
+ .await;
+ assert_eq!(rows(&on), 1);
+ }
}
diff --git a/crates/iceberg/src/expr/visitors/bloom_filter_evaluator.rs b/crates/iceberg/src/expr/visitors/bloom_filter_evaluator.rs
new file mode 100644
index 000000000..3dfc8ec4a
--- /dev/null
+++ b/crates/iceberg/src/expr/visitors/bloom_filter_evaluator.rs
@@ -0,0 +1,1615 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Evaluates predicates against Parquet bloom filters to determine whether
+//! a row group can be skipped.
+
+use std::collections::{HashMap, HashSet};
+
+use fnv::FnvHashSet;
+use parquet::basic::Type as PhysicalType;
+use parquet::bloom_filter::Sbbf;
+use parquet::data_type::ByteArray;
+
+use crate::Result;
+use crate::expr::visitors::bound_predicate_visitor::{BoundPredicateVisitor, visit};
+use crate::expr::{BoundPredicate, BoundReference};
+use crate::spec::decimal_utils::decimal_to_fixed_length_bytes_exact;
+use crate::spec::{Datum, PrimitiveLiteral, PrimitiveType, Type};
+
+const ROW_GROUP_MIGHT_MATCH: Result<bool> = Ok(true);
+const ROW_GROUP_CANT_MATCH: Result<bool> = Ok(false);
+
+/// A column's bloom filter for one row group, together with the file's physical
+/// encoding of that column. A probe must be encoded the way the writer encoded
+/// the values it inserted, so the encoding travels with the filter.
+pub(crate) struct ColumnBloomFilter {
+ sbbf: Sbbf,
+ physical_type: PhysicalType,
+ /// `type_length` from the file's column descriptor. Only meaningful for
+ /// `FIXED_LEN_BYTE_ARRAY`.
+ type_length: i32,
+}
+
+impl ColumnBloomFilter {
+ pub(crate) fn new(sbbf: Sbbf, physical_type: PhysicalType, type_length: i32) -> Self {
+ Self {
+ sbbf,
+ physical_type,
+ type_length,
+ }
+ }
+}
+
+pub(crate) struct BloomFilterEvaluator<'a> {
+ /// Maps Iceberg field_id -> bloom filter for this row group
+ bloom_filters: &'a HashMap<i32, ColumnBloomFilter>,
+}
+
+impl BloomFilterEvaluator<'_> {
+ /// Evaluate the predicate against the provided bloom filters.
+ /// Returns `false` if the row group definitely does not match,
+ /// `true` if it might match.
+ pub(crate) fn eval(
+ filter: &BoundPredicate,
+ bloom_filters: &HashMap<i32, ColumnBloomFilter>,
+ ) -> Result<bool> {
+ if bloom_filters.is_empty() {
+ return ROW_GROUP_MIGHT_MATCH;
+ }
+
+ let mut evaluator = BloomFilterEvaluator { bloom_filters };
+ visit(&mut evaluator, filter)
+ }
+
+ fn check_datum(&self, reference: &BoundReference, datum: &Datum) -> bool {
+ let field_id = reference.field().id;
+ let Some(column) = self.bloom_filters.get(&field_id) else {
+ // No bloom filter for this column — conservatively might match
+ return true;
+ };
+
+ check_in_bloom_filter(column, datum)
+ }
+}
+
+/// Collects field IDs that appear in `eq` or `in` predicates — the only
+/// predicate types that benefit from bloom filter checks.
+///
+/// Each node returns the field IDs its subtree contributes, mirroring
+/// [`BloomFilterEvaluator`]'s structure so that a field is collected only where
+/// the evaluator can act on it. In particular `not` discards its subtree: the
+/// evaluator's `not` returns might-match regardless, so a filter fetched for a
+/// field under a `NOT` could never prune and would be pure wasted I/O.
+///
+/// Boolean fields are skipped for the same reason: with only two possible values,
+/// a column chunk's min/max statistics already determine membership exactly, so a
+/// bloom filter cannot prune anything statistics did not, and reading one costs a
+/// round trip to learn nothing.
+pub(crate) fn collect_bloom_filter_field_ids(predicate: &BoundPredicate) -> Result<HashSet<i32>> {
+ visit(&mut BloomFilterFieldIdCollector, predicate)
+}
+
+struct BloomFilterFieldIdCollector;
+
+/// Field IDs worth fetching a bloom filter for: none if probing the column could
+/// never prune.
+fn probeable_field_id(reference: &BoundReference) -> HashSet<i32> {
+ if matches!(
+ reference.field().field_type.as_ref(),
+ Type::Primitive(PrimitiveType::Boolean)
+ ) {
+ return HashSet::new();
+ }
+ HashSet::from([reference.field().id])
+}
+
+impl BoundPredicateVisitor for BloomFilterFieldIdCollector {
+ type T = HashSet<i32>;
+
+ fn always_true(&mut self) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn always_false(&mut self) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn and(&mut self, mut lhs: Self::T, rhs: Self::T) -> Result<Self::T> {
+ lhs.extend(rhs);
+ Ok(lhs)
+ }
+
+ fn or(&mut self, mut lhs: Self::T, rhs: Self::T) -> Result<Self::T> {
+ lhs.extend(rhs);
+ Ok(lhs)
+ }
+
+ fn not(&mut self, _inner: Self::T) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn is_null(&mut self, _r: &BoundReference, _p: &BoundPredicate) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn not_null(&mut self, _r: &BoundReference, _p: &BoundPredicate) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn is_nan(&mut self, _r: &BoundReference, _p: &BoundPredicate) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn not_nan(&mut self, _r: &BoundReference, _p: &BoundPredicate) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn less_than(
+ &mut self,
+ _r: &BoundReference,
+ _l: &Datum,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn less_than_or_eq(
+ &mut self,
+ _r: &BoundReference,
+ _l: &Datum,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn greater_than(
+ &mut self,
+ _r: &BoundReference,
+ _l: &Datum,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn greater_than_or_eq(
+ &mut self,
+ _r: &BoundReference,
+ _l: &Datum,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn eq(&mut self, r: &BoundReference, _l: &Datum, _p: &BoundPredicate) -> Result<Self::T> {
+ Ok(probeable_field_id(r))
+ }
+
+ fn not_eq(&mut self, _r: &BoundReference, _l: &Datum, _p: &BoundPredicate) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn starts_with(
+ &mut self,
+ _r: &BoundReference,
+ _l: &Datum,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn not_starts_with(
+ &mut self,
+ _r: &BoundReference,
+ _l: &Datum,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+
+ fn r#in(
+ &mut self,
+ r: &BoundReference,
+ _literals: &FnvHashSet<Datum>,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(probeable_field_id(r))
+ }
+
+ fn not_in(
+ &mut self,
+ _r: &BoundReference,
+ _literals: &FnvHashSet<Datum>,
+ _p: &BoundPredicate,
+ ) -> Result<Self::T> {
+ Ok(HashSet::new())
+ }
+}
+
+/// Check whether a datum value might be present in the bloom filter.
+///
+/// The value must be checked using the same physical encoding the Parquet
+/// writer used when inserting into the bloom filter. We use the actual
+/// physical type from the column metadata to ensure correctness regardless
+/// of which writer produced the file.
+fn check_in_bloom_filter(column: &ColumnBloomFilter, datum: &Datum) -> bool {
+ let ColumnBloomFilter {
+ sbbf,
+ physical_type,
+ type_length,
+ } = column;
+ let physical_type = *physical_type;
+
+ match datum.literal() {
+ // Parquet does not define bloom filter semantics for BOOLEAN — parquet-java
+ // only hashes int/long/float/double/binary. arrow-rs does write them, but min/max
+ // statistics already decide membership for a two-valued domain, so there is nothing to gain.
+ PrimitiveLiteral::Boolean(_) => true,
+ // A promoted column (int -> long, float -> double) keeps its original
+ // physical width in files written before the promotion, and the writer
+ // hashed that width, so probe at the file's width rather than the
+ // predicate's.
+ PrimitiveLiteral::Int(v) => match physical_type {
+ PhysicalType::INT32 => sbbf.check(v),
+ PhysicalType::INT64 => sbbf.check(&i64::from(*v)),
+ _ => true,
+ },
+ PrimitiveLiteral::Long(v) => match physical_type {
+ PhysicalType::INT64 => sbbf.check(v),
+ PhysicalType::INT32 => match i32::try_from(*v) {
+ Ok(narrowed) => sbbf.check(&narrowed),
+ // Too wide for an INT32 column to hold, so the value is provably
+ // absent and pruning here would be sound; kept conservative for now.
+ Err(_) => true,
+ },
+ _ => true,
+ },
+ PrimitiveLiteral::Float(v) => match physical_type {
+ PhysicalType::FLOAT => sbbf.check(&v.0),
+ PhysicalType::DOUBLE => sbbf.check(&f64::from(v.0)),
+ _ => true,
+ },
+ PrimitiveLiteral::Double(v) => match physical_type {
+ PhysicalType::DOUBLE => sbbf.check(&v.0),
+ PhysicalType::FLOAT => {
+ let narrowed = v.0 as f32;
+ // Only an exactly representable value can equal a widened f32.
+ if f64::from(narrowed) == v.0 {
+ sbbf.check(&narrowed)
+ } else {
+ true
+ }
+ }
+ _ => true,
+ },
+ PrimitiveLiteral::String(v) => sbbf.check(v.as_str()),
+ PrimitiveLiteral::Binary(v) => sbbf.check(v.as_slice()),
+ PrimitiveLiteral::Int128(v) => {
+ // Decimal: dispatch based on the actual Parquet physical type
+ // from the file, not inferred from precision.
+ match physical_type {
+ // Narrow only when the mantissa round-trips; a truncated copy would
+ // hash to an unrelated slot.
+ PhysicalType::INT32 => match i32::try_from(*v) {
+ Ok(narrowed) => sbbf.check(&narrowed),
+ Err(_) => true,
+ },
+ PhysicalType::INT64 => match i64::try_from(*v) {
+ Ok(narrowed) => sbbf.check(&narrowed),
+ Err(_) => true,
+ },
+ PhysicalType::FIXED_LEN_BYTE_ARRAY => {
+ // Encode to the file's declared length, not one derived from
+ // the Iceberg precision: a widened precision would change the
+ // length and miss every entry the writer inserted.
+ match usize::try_from(*type_length)
+ .ok()
+ .and_then(|len| decimal_to_fixed_length_bytes_exact(*v, len))
+ {
+ Some(bytes) => sbbf.check(&ByteArray::from(bytes)),
+ // Unusable length, or a value too large for the column to
+ // hold — conservatively might match.
+ None => true,
+ }
+ }
+ // Known gap: BYTE_ARRAY decimals are valid in Parquet (though not in
+ // Iceberg's Appendix A) and some older Spark writers emit them. Not
+ // probed because BYTE_ARRAY carries no `type_length` and sign-extension
+ // padding is writer-dependent, so a single-length probe would miss
+ // padded entries and prune row groups that do hold the value. A sound
+ // version ORs a check over every length from minimal..=16.
+ _ => true, // Conservatively might match
+ }
+ }
+ PrimitiveLiteral::UInt128(v) => {
+ // UUID: stored as FIXED_LEN_BYTE_ARRAY(16), big-endian
+ let bytes = v.to_be_bytes();
+ sbbf.check(bytes.as_slice())
+ }
+ PrimitiveLiteral::AboveMax | PrimitiveLiteral::BelowMin => true,
+ }
+}
+
+impl BoundPredicateVisitor for BloomFilterEvaluator<'_> {
+ type T = bool;
+
+ fn always_true(&mut self) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn always_false(&mut self) -> Result<Self::T> {
+ ROW_GROUP_CANT_MATCH
+ }
+
+ fn and(&mut self, lhs: Self::T, rhs: Self::T) -> Result<Self::T> {
+ Ok(lhs && rhs)
+ }
+
+ fn or(&mut self, lhs: Self::T, rhs: Self::T) -> Result<Self::T> {
+ Ok(lhs || rhs)
+ }
+
+ fn not(&mut self, _inner: Self::T) -> Result<Self::T> {
+ // Bloom filters are not invertible — we cannot prove presence,
+ // so NOT of any result must conservatively return "might match".
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn is_null(
+ &mut self,
+ _reference: &BoundReference,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn not_null(
+ &mut self,
+ _reference: &BoundReference,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn is_nan(
+ &mut self,
+ _reference: &BoundReference,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn not_nan(
+ &mut self,
+ _reference: &BoundReference,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn less_than(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn less_than_or_eq(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn greater_than(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn greater_than_or_eq(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn eq(
+ &mut self,
+ reference: &BoundReference,
+ literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ if self.check_datum(reference, literal) {
+ ROW_GROUP_MIGHT_MATCH
+ } else {
+ ROW_GROUP_CANT_MATCH
+ }
+ }
+
+ fn not_eq(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn starts_with(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn not_starts_with(
+ &mut self,
+ _reference: &BoundReference,
+ _literal: &Datum,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+
+ fn r#in(
+ &mut self,
+ reference: &BoundReference,
+ literals: &FnvHashSet<Datum>,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ let field_id = reference.field().id;
+ let Some(column) = self.bloom_filters.get(&field_id) else {
+ return ROW_GROUP_MIGHT_MATCH;
+ };
+
+ // If ANY literal might be present, the row group might match
+ for literal in literals {
+ if check_in_bloom_filter(column, literal) {
+ return ROW_GROUP_MIGHT_MATCH;
+ }
+ }
+
+ // All literals are definitely absent
+ ROW_GROUP_CANT_MATCH
+ }
+
+ fn not_in(
+ &mut self,
+ _reference: &BoundReference,
+ _literals: &FnvHashSet<Datum>,
+ _predicate: &BoundPredicate,
+ ) -> Result<Self::T> {
+ ROW_GROUP_MIGHT_MATCH
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use std::collections::HashMap;
+ use std::ops::Not;
+
+ use parquet::basic::Type as PhysicalType;
+ use parquet::bloom_filter::Sbbf;
+ use parquet::data_type::ByteArray;
+
+ use super::{BloomFilterEvaluator, ColumnBloomFilter, collect_bloom_filter_field_ids};
+ use crate::expr::{Bind, BoundPredicate, Reference};
+ use crate::spec::decimal_utils::decimal_to_fixed_length_bytes_exact;
+ use crate::spec::{Datum, NestedField, PrimitiveType, Schema, Type};
+
+ fn create_test_schema() -> Schema {
+ Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![
+ NestedField::required(1, "id", Type::Primitive(PrimitiveType::Int)).into(),
+ NestedField::optional(2, "name", Type::Primitive(PrimitiveType::String)).into(),
+ ])
+ .build()
+ .unwrap()
+ }
+
+ fn create_bloom_filter_with_values_i32(values: &[i32]) -> Sbbf {
+ let mut sbbf = Sbbf::new_with_ndv_fpp(values.len() as u64, 0.01).unwrap();
+ for v in values {
+ sbbf.insert(v);
+ }
+ sbbf
+ }
+
+ fn create_bloom_filter_with_values_str(values: &[&str]) -> Sbbf {
+ let mut sbbf = Sbbf::new_with_ndv_fpp(values.len() as u64, 0.01).unwrap();
+ for v in values {
+ sbbf.insert(*v);
+ }
+ sbbf
+ }
+
+ #[test]
+ fn test_eq_value_present() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(2))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "Row group should might-match when value is present");
+ }
+
+ #[test]
+ fn test_eq_value_absent() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(999))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ !result,
+ "Row group should not match when value is absent from bloom filter"
+ );
+ }
+
+ #[test]
+ fn test_eq_no_bloom_filter_for_column() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::new(); // No bloom filters
+
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(1))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "Row group should might-match when no bloom filter available"
+ );
+ }
+
+ #[test]
+ fn test_in_all_absent() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .is_in([Datum::int(100), Datum::int(200), Datum::int(300)])
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ !result,
+ "Row group should not match when all IN values are absent"
+ );
+ }
+
+ #[test]
+ fn test_in_some_present() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .is_in([Datum::int(2), Datum::int(200)])
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "Row group should might-match when at least one IN value is present"
+ );
+ }
+
+ #[test]
+ fn test_and_one_absent() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([
+ (
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ ),
+ (
+ 2,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_str(&["alice", "bob"]),
+ PhysicalType::BYTE_ARRAY,
+ 0,
+ ),
+ ),
+ ]);
+
+ // id = 999 AND name = 'alice'
+ // id=999 is absent, so AND should be false
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(999))
+ .and(Reference::new("name").equal_to(Datum::string("alice")))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ !result,
+ "AND should be false when one operand is definitely absent"
+ );
+ }
+
+ #[test]
+ fn test_or_one_present() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ // id = 999 OR id = 2
+ // id=2 is present, so OR should be true
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(999))
+ .or(Reference::new("id").equal_to(Datum::int(2)))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "OR should be true when one operand might match");
+ }
+
+ #[test]
+ fn test_not_always_might_match() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ // NOT(id = 999) — even though 999 is absent, NOT should still return true
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(999))
+ .not()
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "NOT should always return might-match");
+ }
+
+ // --- Field ID collection ---
+ //
+ // The collector decides which bloom filters get fetched, one round trip per
+ // column per row group, so anything it reports that the evaluator cannot act
+ // on is wasted I/O.
+
+ fn collected_ids(predicate: BoundPredicate) -> Vec<i32> {
+ let mut ids: Vec<i32> = collect_bloom_filter_field_ids(&predicate)
+ .unwrap()
+ .into_iter()
+ .collect();
+ ids.sort_unstable();
+ ids
+ }
+
+ #[test]
+ fn test_collects_eq_and_in_field_ids() {
+ let schema = create_test_schema();
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(1))
+ .and(Reference::new("name").is_in([Datum::string("alice")]))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ assert_eq!(collected_ids(predicate), vec![1, 2]);
+ }
+
+ /// `not` discards its subtree, so `eq`/`in` beneath a `NOT` are not collected.
+ /// The evaluator's `not` returns might-match regardless, so fetching those
+ /// filters could never prune.
+ #[test]
+ fn test_does_not_collect_eq_under_not() {
+ let schema = create_test_schema();
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(1))
+ .not()
+ .bind(schema.into(), true)
+ .unwrap();
+
+ assert!(collected_ids(predicate).is_empty());
+ }
+
+ #[test]
+ fn test_does_not_collect_in_under_not() {
+ let schema = create_test_schema();
+ let predicate = Reference::new("id")
+ .is_in([Datum::int(1), Datum::int(2)])
+ .not()
+ .bind(schema.into(), true)
+ .unwrap();
+
+ assert!(collected_ids(predicate).is_empty());
+ }
+
+ /// A `NOT` must not suppress collection for its siblings.
+ #[test]
+ fn test_collects_sibling_of_not() {
+ let schema = create_test_schema();
+ let predicate = Reference::new("id")
+ .equal_to(Datum::int(1))
+ .not()
+ .and(Reference::new("name").equal_to(Datum::string("alice")))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ assert_eq!(collected_ids(predicate), vec![2]);
+ }
+
+ /// A boolean column's min/max statistics already determine membership exactly,
+ /// so fetching a bloom filter for one can never prune and is pure wasted I/O.
+ #[test]
+ fn test_does_not_collect_boolean_field_ids() {
+ let schema = Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![
+ NestedField::required(1, "flag", Type::Primitive(PrimitiveType::Boolean)).into(),
+ NestedField::required(2, "id", Type::Primitive(PrimitiveType::Int)).into(),
+ ])
+ .build()
+ .unwrap();
+
+ let predicate = Reference::new("flag")
+ .equal_to(Datum::bool(true))
+ .and(Reference::new("flag").is_in([Datum::bool(false)]))
+ .and(Reference::new("id").equal_to(Datum::int(1)))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ assert_eq!(
+ collected_ids(predicate),
+ vec![2],
+ "only the non-boolean field should be collected"
+ );
+ }
+
+ /// Even given a filter, a boolean probe stays conservative: Parquet does not
+ /// define bloom filter semantics for BOOLEAN, so the encoding is not portable.
+ #[test]
+ fn test_boolean_probe_never_prunes() {
+ let schema = Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![
+ NestedField::required(1, "flag", Type::Primitive(PrimitiveType::Boolean)).into(),
+ ])
+ .build()
+ .unwrap();
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&true);
+ let filters = HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::BOOLEAN, 0))]);
+
+ // `false` was never inserted, yet the row group must survive.
+ let predicate = Reference::new("flag")
+ .equal_to(Datum::bool(false))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(result, "boolean probes must never prune");
+ }
+
+ /// Range and `not_eq` predicates cannot be probed, so they contribute nothing.
+ #[test]
+ fn test_does_not_collect_unprobeable_operators() {
+ let schema = create_test_schema();
+ let predicate = Reference::new("id")
+ .less_than(Datum::int(1))
+ .and(Reference::new("id").not_equal_to(Datum::int(2)))
+ .and(Reference::new("name").is_not_null())
+ .bind(schema.into(), true)
+ .unwrap();
+
+ assert!(collected_ids(predicate).is_empty());
+ }
+
+ #[test]
+ fn test_range_predicates_always_might_match() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .less_than(Datum::int(0))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "Range predicates should always return might-match");
+ }
+
+ #[test]
+ fn test_string_eq_present() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 2,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_str(&["alice", "bob"]),
+ PhysicalType::BYTE_ARRAY,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("name")
+ .equal_to(Datum::string("alice"))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "Should might-match when string is in bloom filter");
+ }
+
+ #[test]
+ fn test_string_eq_absent() {
+ let schema = create_test_schema();
+ let bloom_filters = HashMap::from([(
+ 2,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_str(&["alice", "bob"]),
+ PhysicalType::BYTE_ARRAY,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("name")
+ .equal_to(Datum::string("charlie"))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ !result,
+ "Should not match when string is absent from bloom filter"
+ );
+ }
+
+ // --- Decimal tests ---
+
+ fn create_decimal_schema(precision: u32, scale: u32) -> Schema {
+ Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![
+ NestedField::required(
+ 1,
+ "amount",
+ Type::Primitive(PrimitiveType::Decimal { precision, scale }),
+ )
+ .into(),
+ ])
+ .build()
+ .unwrap()
+ }
+
+ /// Decimal with precision <= 9 is stored as INT32 in Parquet.
+ /// The bloom filter contains i32 values (the unscaled mantissa).
+ #[test]
+ fn test_decimal_int32_present() {
+ let schema = create_decimal_schema(9, 2);
+
+ // Parquet stores decimal(9,2) as INT32 with unscaled value
+ // Value "123.45" has mantissa 12345
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&12345_i32);
+ sbbf.insert(&67890_i32);
+
+ let bloom_filters =
+ HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT32, 0))]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(12345, 2),
+ 9,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "Decimal INT32 value present should might-match");
+ }
+
+ #[test]
+ fn test_decimal_int32_absent() {
+ let schema = create_decimal_schema(9, 2);
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&12345_i32);
+ sbbf.insert(&67890_i32);
+
+ let bloom_filters =
+ HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT32, 0))]);
+
+ // Value "999.99" has mantissa 99999, not in the bloom filter
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(99999, 2),
+ 9,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(!result, "Decimal INT32 value absent should not match");
+ }
+
+ /// Decimal with precision 10-18 is stored as INT64 in Parquet.
+ #[test]
+ fn test_decimal_int64_present() {
+ let schema = create_decimal_schema(15, 2);
+
+ // "1234567890123.45" has mantissa 123456789012345
+ let mantissa: i64 = 123456789012345;
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&mantissa);
+
+ let bloom_filters =
+ HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT64, 0))]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(mantissa as i128, 2),
+ 15,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "Decimal INT64 value present should might-match");
+ }
+
+ #[test]
+ fn test_decimal_int64_absent() {
+ let schema = create_decimal_schema(15, 2);
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&123456789012345_i64);
+
+ let bloom_filters =
+ HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT64, 0))]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(999999999999999, 2),
+ 15,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(!result, "Decimal INT64 value absent should not match");
+ }
+
+ /// Decimal with precision 19+ is stored as FIXED_LEN_BYTE_ARRAY in Parquet.
+ #[test]
+ fn test_decimal_fixed_bytes_present() {
+ let schema = create_decimal_schema(25, 2);
+
+ // Large mantissa that requires FIXED_LEN_BYTE_ARRAY
+ let mantissa: i128 = 12345678901234567890;
+ let bytes = decimal_to_fixed_length_bytes_exact(mantissa, 11).unwrap();
+ let type_length = bytes.len() as i32;
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(bytes));
+
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(sbbf, PhysicalType::FIXED_LEN_BYTE_ARRAY, type_length),
+ )]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(mantissa, 2),
+ 25,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "Decimal FIXED_LEN_BYTE_ARRAY value present should might-match"
+ );
+ }
+
+ #[test]
+ fn test_decimal_fixed_bytes_absent() {
+ let schema = create_decimal_schema(25, 2);
+
+ let mantissa: i128 = 12345678901234567890;
+ let bytes = decimal_to_fixed_length_bytes_exact(mantissa, 11).unwrap();
+ let type_length = bytes.len() as i32;
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(bytes));
+
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(sbbf, PhysicalType::FIXED_LEN_BYTE_ARRAY, type_length),
+ )]);
+
+ // Different value not in the bloom filter
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(
+ 99999999999999999999,
+ 2,
+ ),
+ 25,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ !result,
+ "Decimal FIXED_LEN_BYTE_ARRAY value absent should not match"
+ );
+ }
+
+ fn create_uuid_schema() -> Schema {
+ Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![
+ NestedField::required(1, "u", Type::Primitive(PrimitiveType::Uuid)).into(),
+ ])
+ .build()
+ .unwrap()
+ }
+
+ /// The probe hands the 16 big-endian bytes to `check` as a slice while the writer
+ /// inserts them as a `ByteArray`; both hash the same bytes, so a present UUID must
+ /// still might-match.
+ #[test]
+ fn test_uuid_fixed_bytes_present() {
+ let uuid = uuid::Uuid::parse_str("f79c3e09-677c-4bbd-a479-3f349cb785e7").unwrap();
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(uuid.as_u128().to_be_bytes().to_vec()));
+
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(sbbf, PhysicalType::FIXED_LEN_BYTE_ARRAY, 16),
+ )]);
+
+ let predicate = Reference::new("u")
+ .equal_to(Datum::uuid(uuid))
+ .bind(create_uuid_schema().into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "UUID present should might-match");
+ }
+
+ #[test]
+ fn test_uuid_fixed_bytes_absent() {
+ let present = uuid::Uuid::parse_str("f79c3e09-677c-4bbd-a479-3f349cb785e7").unwrap();
+ let absent = uuid::Uuid::parse_str("00000000-0000-4000-8000-000000000001").unwrap();
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(present.as_u128().to_be_bytes().to_vec()));
+
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(sbbf, PhysicalType::FIXED_LEN_BYTE_ARRAY, 16),
+ )]);
+
+ let predicate = Reference::new("u")
+ .equal_to(Datum::uuid(absent))
+ .bind(create_uuid_schema().into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(!result, "UUID absent should not match");
+ }
+
+ /// Negative decimal values should also work correctly.
+ #[test]
+ fn test_decimal_negative_int32() {
+ let schema = create_decimal_schema(9, 2);
+
+ // "-123.45" has mantissa -12345
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&(-12345_i32));
+
+ let bloom_filters =
+ HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT32, 0))]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(-12345, 2),
+ 9,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "Negative decimal INT32 present should might-match");
+ }
+
+ #[test]
+ fn test_decimal_negative_fixed_bytes() {
+ let schema = create_decimal_schema(25, 2);
+
+ let mantissa: i128 = -12345678901234567890;
+ let bytes = decimal_to_fixed_length_bytes_exact(mantissa, 11).unwrap();
+ let type_length = bytes.len() as i32;
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(bytes));
+
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(sbbf, PhysicalType::FIXED_LEN_BYTE_ARRAY, type_length),
+ )]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(mantissa, 2),
+ 25,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "Negative decimal FIXED_LEN_BYTE_ARRAY present should might-match"
+ );
+ }
+
+ /// A Parquet writer other than arrow-rs (e.g. Spark, Java Parquet) might
+ /// choose FIXED_LEN_BYTE_ARRAY for a low-precision decimal rather than INT32.
+ /// The evaluator must use the physical type from the file metadata, not assume
+ /// a mapping based on precision.
+ #[test]
+ fn test_decimal_low_precision_stored_as_fixed_len_byte_array() {
+ let schema = create_decimal_schema(5, 2);
+
+ // Simulate a file where decimal(5,2) was stored as FIXED_LEN_BYTE_ARRAY
+ let mantissa: i128 = 12345;
+ let bytes = decimal_to_fixed_length_bytes_exact(mantissa, 3).unwrap();
+ let type_length = bytes.len() as i32;
+
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(bytes));
+
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(sbbf, PhysicalType::FIXED_LEN_BYTE_ARRAY, type_length),
+ )]);
+
+ let predicate = Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(mantissa, 2),
+ 5,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "Should match when physical type is FIXED_LEN_BYTE_ARRAY even for low-precision decimal"
+ );
+ }
+
+ /// Builds the (schema, bloom filter) pair for a `decimal` column that the file
+ /// stored at `file_type_length` bytes while the table schema now declares
+ /// `schema_precision`, as a precision-widening evolution produces.
+ fn widened_decimal_case(
+ mantissa: i128,
+ file_type_length: usize,
+ schema_precision: u32,
+ ) -> (Schema, HashMap<i32, ColumnBloomFilter>) {
+ let bytes = decimal_to_fixed_length_bytes_exact(mantissa, file_type_length).unwrap();
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(bytes));
+
+ let filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ sbbf,
+ PhysicalType::FIXED_LEN_BYTE_ARRAY,
+ file_type_length as i32,
+ ),
+ )]);
+
+ (create_decimal_schema(schema_precision, 2), filters)
+ }
+
+ fn decimal_eq_predicate(schema: Schema, mantissa: i128, precision: u32) -> BoundPredicate {
+ Reference::new("amount")
+ .equal_to(
+ Datum::decimal_with_precision(
+ crate::spec::decimal_utils::decimal_from_i128_with_scale(mantissa, 2),
+ precision,
+ )
+ .unwrap(),
+ )
+ .bind(schema.into(), true)
+ .unwrap()
+ }
+
+ /// Widening a decimal's precision does not rewrite existing files, so the
+ /// column keeps its original `type_length`. Deriving the probe length from the
+ /// widened precision changed the encoding and missed every entry the writer
+ /// inserted, silently pruning row groups holding matching rows.
+ #[test]
+ fn test_decimal_widened_precision_present_is_not_pruned() {
+ let mantissa: i128 = 12345678901234567890;
+ // File written as decimal(20,2) -> 9 bytes; schema since widened to 38.
+ let (schema, filters) = widened_decimal_case(mantissa, 9, 38);
+ let predicate = decimal_eq_predicate(schema, mantissa, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(
+ result,
+ "widened decimal precision must still find the value at the file's length"
+ );
+ }
+
+ #[test]
+ fn test_decimal_widened_precision_absent_still_prunes() {
+ let mantissa: i128 = 12345678901234567890;
+ let (schema, filters) = widened_decimal_case(mantissa, 9, 38);
+ let predicate = decimal_eq_predicate(schema, 999999999999999999, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(!result, "genuinely absent value must still prune");
+ }
+
+ /// A value too wide for the column's `type_length` cannot be present, but
+ /// truncating it would probe an unrelated slot, so stay conservative.
+ #[test]
+ fn test_decimal_value_wider_than_column_does_not_prune() {
+ let (schema, filters) = widened_decimal_case(1234, 2, 38);
+ let predicate = decimal_eq_predicate(schema, i64::MAX as i128, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(result, "value too wide for the column must not prune");
+ }
+
+ /// The `INT32` / `INT64` counterparts of the case above: after a precision
+ /// widening the bound literal can carry a mantissa wider than the file's
+ /// physical column, and a truncated probe would hash an unrelated slot.
+ #[test]
+ fn test_decimal_wider_than_int32_column_does_not_prune() {
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&12345_i32);
+ let filters = HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT32, 0))]);
+
+ // File written as decimal(9,2) -> INT32; schema since widened to decimal(38,2).
+ let predicate = decimal_eq_predicate(create_decimal_schema(38, 2), i64::MAX as i128, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(
+ result,
+ "mantissa too wide for an INT32 column must not prune"
+ );
+ }
+
+ #[test]
+ fn test_decimal_wider_than_int64_column_does_not_prune() {
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&12345_i64);
+ let filters = HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT64, 0))]);
+
+ let predicate =
+ decimal_eq_predicate(create_decimal_schema(38, 2), i128::from(i64::MAX) + 1, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(
+ result,
+ "mantissa too wide for an INT64 column must not prune"
+ );
+ }
+
+ /// A mantissa that does fit must still prune when genuinely absent, so the
+ /// `try_from` guard above does not disable pruning outright.
+ #[test]
+ fn test_decimal_within_int64_column_still_prunes() {
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&12345_i64);
+ let filters = HashMap::from([(1, ColumnBloomFilter::new(sbbf, PhysicalType::INT64, 0))]);
+
+ let predicate = decimal_eq_predicate(create_decimal_schema(38, 2), 999_999, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(!result, "absent in-range mantissa must still prune");
+ }
+
+ /// A zero or oversized `type_length` is unusable; never prune on it.
+ #[test]
+ fn test_decimal_unusable_type_length_does_not_prune() {
+ let mantissa: i128 = 1234;
+ let bytes = decimal_to_fixed_length_bytes_exact(mantissa, 4).unwrap();
+ let mut sbbf = Sbbf::new_with_ndv_fpp(10, 0.01).unwrap();
+ sbbf.insert(&ByteArray::from(bytes));
+
+ for bogus_length in [0, -1, 17] {
+ let filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ Sbbf::new_with_ndv_fpp(10, 0.01).unwrap(),
+ PhysicalType::FIXED_LEN_BYTE_ARRAY,
+ bogus_length,
+ ),
+ )]);
+ let predicate = decimal_eq_predicate(create_decimal_schema(38, 2), mantissa, 38);
+
+ let result = BloomFilterEvaluator::eval(&predicate, &filters).unwrap();
+ assert!(
+ result,
+ "type_length {bogus_length} is unusable and must not prune"
+ );
+ }
+ }
+
+ fn single_field_schema(name: &str, ty: PrimitiveType) -> Schema {
+ Schema::builder()
+ .with_schema_id(1)
+ .with_fields(vec![
+ NestedField::required(1, name, Type::Primitive(ty)).into(),
+ ])
+ .build()
+ .unwrap()
+ }
+
+ /// After an `int` -> `long` promotion the predicate carries a `long`, but files
+ /// written before the promotion store the column as `INT32` and hashed it at
+ /// that width. Probing at the predicate's width made every lookup miss and
+ /// silently pruned row groups holding matching rows.
+ #[test]
+ fn test_promoted_int_to_long_present_is_not_pruned() {
+ let schema = single_field_schema("id", PrimitiveType::Long);
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[100, 150, 199]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .equal_to(Datum::long(150))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "long predicate against an INT32 column must find the promoted value"
+ );
+ }
+
+ #[test]
+ fn test_promoted_int_to_long_absent_still_prunes() {
+ let schema = single_field_schema("id", PrimitiveType::Long);
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[100, 150, 199]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .equal_to(Datum::long(4242))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(!result, "genuinely absent value must still prune");
+ }
+
+ /// A `long` predicate outside `i32` range cannot be present in an `INT32`
+ /// column; stay conservative rather than probe a truncated value.
+ #[test]
+ fn test_long_out_of_int32_range_does_not_prune() {
+ let schema = single_field_schema("id", PrimitiveType::Long);
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_i32(&[1, 2, 3]),
+ PhysicalType::INT32,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("id")
+ .equal_to(Datum::long(i64::from(i32::MAX) + 1))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "out-of-range long must not prune");
+ }
+
+ fn create_bloom_filter_with_values_f32(values: &[f32]) -> Sbbf {
+ let mut sbbf = Sbbf::new_with_ndv_fpp(values.len() as u64, 0.01).unwrap();
+ for v in values {
+ sbbf.insert(v);
+ }
+ sbbf
+ }
+
+ /// The `float` -> `double` counterpart of the `int` -> `long` promotion above.
+ #[test]
+ fn test_promoted_float_to_double_present_is_not_pruned() {
+ let schema = single_field_schema("val", PrimitiveType::Double);
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_f32(&[1.5, 2.25, 4.0]),
+ PhysicalType::FLOAT,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("val")
+ .equal_to(Datum::double(1.5))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(
+ result,
+ "double predicate against a FLOAT column must find the promoted value"
+ );
+ }
+
+ #[test]
+ fn test_promoted_float_to_double_absent_still_prunes() {
+ let schema = single_field_schema("val", PrimitiveType::Double);
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_f32(&[1.5, 2.25, 4.0]),
+ PhysicalType::FLOAT,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("val")
+ .equal_to(Datum::double(9.75))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(!result, "genuinely absent value must still prune");
+ }
+
+ /// A double with no exact `f32` representation cannot equal any widened
+ /// `f32` in the column, so probing it would be meaningless; stay conservative.
+ #[test]
+ fn test_double_not_representable_as_f32_does_not_prune() {
+ let schema = single_field_schema("val", PrimitiveType::Double);
+ let bloom_filters = HashMap::from([(
+ 1,
+ ColumnBloomFilter::new(
+ create_bloom_filter_with_values_f32(&[1.5, 2.25]),
+ PhysicalType::FLOAT,
+ 0,
+ ),
+ )]);
+
+ let predicate = Reference::new("val")
+ .equal_to(Datum::double(0.1))
+ .bind(schema.into(), true)
+ .unwrap();
+
+ let result = BloomFilterEvaluator::eval(&predicate, &bloom_filters).unwrap();
+ assert!(result, "non-representable double must not prune");
+ }
+}
diff --git a/crates/iceberg/src/expr/visitors/mod.rs b/crates/iceberg/src/expr/visitors/mod.rs
index 38332ea6a..c5aca6838 100644
--- a/crates/iceberg/src/expr/visitors/mod.rs
+++ b/crates/iceberg/src/expr/visitors/mod.rs
@@ -15,6 +15,7 @@
// specific language governing permissions and limitations
// under the License.
+pub(crate) mod bloom_filter_evaluator;
pub(crate) mod bound_predicate_visitor;
pub(crate) mod expression_evaluator;
pub(crate) mod inclusive_metrics_evaluator;
diff --git a/crates/iceberg/src/scan/mod.rs b/crates/iceberg/src/scan/mod.rs
index 9bdf42beb..081d64273 100644
--- a/crates/iceberg/src/scan/mod.rs
+++ b/crates/iceberg/src/scan/mod.rs
@@ -142,6 +142,7 @@ pub struct TableScanBuilder<'a> {
concurrency_limit_manifest_files: usize,
row_group_filtering_enabled: bool,
row_selection_enabled: bool,
+ bloom_filter_enabled: bool,
}
impl<'a> TableScanBuilder<'a> {
@@ -160,6 +161,7 @@ impl<'a> TableScanBuilder<'a> {
concurrency_limit_manifest_files: num_cpus,
row_group_filtering_enabled: true,
row_selection_enabled: false,
+ bloom_filter_enabled: false,
}
}
@@ -266,6 +268,20 @@ impl<'a> TableScanBuilder<'a> {
self
}
+ /// Determines whether to enable bloom filter-based row group filtering.
+ ///
+ /// When enabled, if a read is performed with an equality or IN predicate,
+ /// the bloom filter for relevant columns in each row group is read and
+ /// checked. Row groups where the bloom filter proves the value is absent
+ /// are skipped entirely.
+ ///
+ /// Defaults to disabled, as reading bloom filters requires additional I/O
+ /// per column per row group.
+ pub fn with_bloom_filter_enabled(mut self, bloom_filter_enabled: bool) -> Self {
+ self.bloom_filter_enabled = bloom_filter_enabled;
+ self
+ }
+
/// Build the table scan.
pub fn build(self) -> Result<TableScan> {
let snapshot = match self.snapshot_id {
@@ -292,6 +308,7 @@ impl<'a> TableScanBuilder<'a> {
concurrency_limit_manifest_files: self.concurrency_limit_manifest_files,
row_group_filtering_enabled: self.row_group_filtering_enabled,
row_selection_enabled: self.row_selection_enabled,
+ bloom_filter_enabled: self.bloom_filter_enabled,
runtime: self.table.runtime().clone(),
});
};
@@ -349,6 +366,7 @@ impl<'a> TableScanBuilder<'a> {
concurrency_limit_manifest_files: self.concurrency_limit_manifest_files,
row_group_filtering_enabled: self.row_group_filtering_enabled,
row_selection_enabled: self.row_selection_enabled,
+ bloom_filter_enabled: self.bloom_filter_enabled,
runtime: self.table.runtime().clone(),
})
}
@@ -378,6 +396,7 @@ pub struct TableScan {
row_group_filtering_enabled: bool,
row_selection_enabled: bool,
+ bloom_filter_enabled: bool,
runtime: Runtime,
}
@@ -510,7 +529,8 @@ impl TableScan {
ArrowReaderBuilder::new(self.file_io.clone(), self.runtime.clone())
.with_data_file_concurrency_limit(self.concurrency_limit_data_files)
.with_row_group_filtering_enabled(self.row_group_filtering_enabled)
- .with_row_selection_enabled(self.row_selection_enabled);
+ .with_row_selection_enabled(self.row_selection_enabled)
+ .with_bloom_filter_enabled(self.bloom_filter_enabled);
if let Some(batch_size) = self.batch_size {
arrow_reader_builder = arrow_reader_builder.with_batch_size(batch_size);
diff --git a/crates/iceberg/src/spec/values/decimal_utils.rs b/crates/iceberg/src/spec/values/decimal_utils.rs
index 97225113c..3d09d6f25 100644
--- a/crates/iceberg/src/spec/values/decimal_utils.rs
+++ b/crates/iceberg/src/spec/values/decimal_utils.rs
@@ -196,6 +196,33 @@ pub fn i128_to_be_bytes_min(value: i128) -> Vec<u8> {
bytes[start..].to_vec()
}
+/// Encode an i128 as exactly `len` big-endian two's complement bytes, matching a
+/// Parquet `FIXED_LEN_BYTE_ARRAY` column of that declared `type_length`.
+///
+/// Returns `None` if `value` does not fit in `len` bytes, since a truncated
+/// encoding would represent a different number.
+pub(crate) fn decimal_to_fixed_length_bytes_exact(value: i128, len: usize) -> Option<Vec<u8>> {
+ if len == 0 || len > 16 {
+ return None;
+ }
+
+ let be_bytes = value.to_be_bytes();
+ let offset = 16 - len;
+ let sign_byte = if value < 0 { 0xFF } else { 0x00 };
+
+ // The bytes being dropped must be pure sign extension.
+ if be_bytes[..offset].iter().any(|&b| b != sign_byte) {
+ return None;
+ }
+
+ // The retained leading byte must carry the value's sign.
+ if (be_bytes[offset] & 0x80 != 0) != (value < 0) {
+ return None;
+ }
+
+ Some(be_bytes[offset..].to_vec())
+}
+
#[cfg(test)]
mod tests {
use super::*;
@@ -356,4 +383,77 @@ mod tests {
);
}
}
+
+ #[test]
+ fn test_decimal_to_fixed_length_bytes_exact_positive() {
+ let bytes = decimal_to_fixed_length_bytes_exact(12345, 9).unwrap();
+ assert_eq!(bytes.len(), 9);
+ // Big-endian, zero-padded on the left: 12345 = 0x3039
+ assert_eq!(bytes[7], 0x30);
+ assert_eq!(bytes[8], 0x39);
+ assert!(bytes[..7].iter().all(|&b| b == 0x00));
+ }
+
+ #[test]
+ fn test_decimal_to_fixed_length_bytes_exact_negative() {
+ let bytes = decimal_to_fixed_length_bytes_exact(-1, 9).unwrap();
+ assert_eq!(bytes.len(), 9);
+ assert!(bytes.iter().all(|&b| b == 0xFF));
+ }
+
+ #[test]
+ fn test_decimal_to_fixed_length_bytes_exact_round_trip() {
+ for value in [
+ 0i128,
+ 1,
+ -1,
+ 12345,
+ -12345,
+ i64::MAX as i128,
+ i64::MIN as i128,
+ ] {
+ let bytes = decimal_to_fixed_length_bytes_exact(value, 16).unwrap();
+ assert_eq!(bytes.len(), 16);
+ assert_eq!(
+ i128_from_be_bytes(&bytes),
+ Some(value),
+ "Round trip failed for value={value}"
+ );
+ }
+ }
+
+ /// The length must be honoured exactly: a value needing more bytes cannot be
+ /// truncated into the column's width, because the truncation would encode a
+ /// different number and probe the wrong bloom filter slot.
+ #[test]
+ fn test_decimal_to_fixed_length_bytes_exact_rejects_overflow() {
+ // 200 needs a leading zero byte to stay positive in two's complement.
+ assert_eq!(decimal_to_fixed_length_bytes_exact(200, 1), None);
+ assert_eq!(
+ decimal_to_fixed_length_bytes_exact(200, 2),
+ Some(vec![0x00, 0xC8])
+ );
+
+ assert_eq!(decimal_to_fixed_length_bytes_exact(-200, 1), None);
+ assert_eq!(
+ decimal_to_fixed_length_bytes_exact(-200, 2),
+ Some(vec![0xFF, 0x38])
+ );
+
+ // Exactly representable boundaries.
+ assert_eq!(
+ decimal_to_fixed_length_bytes_exact(127, 1),
+ Some(vec![0x7F])
+ );
+ assert_eq!(decimal_to_fixed_length_bytes_exact(128, 1), None);
+ assert_eq!(
+ decimal_to_fixed_length_bytes_exact(-128, 1),
+ Some(vec![0x80])
+ );
+ assert_eq!(decimal_to_fixed_length_bytes_exact(-129, 1), None);
+
+ assert_eq!(decimal_to_fixed_length_bytes_exact(i128::MAX, 15), None);
+ assert_eq!(decimal_to_fixed_length_bytes_exact(0, 0), None);
+ assert_eq!(decimal_to_fixed_length_bytes_exact(0, 17), None);
+ }
}