mbutrovich commented on code in PR #3739:
URL: https://github.com/apache/iceberg-rust/pull/3739#discussion_r4648112922
##########
crates/iceberg/src/arrow/reader/predicate_visitor.rs:
##########
@@ -278,6 +331,31 @@ fn project_column(
}
}
+fn probe_set(index: &SetIndex, column: &ArrayRef, negated: bool) ->
Option<BooleanArray> {
+ Some(match (index, column.data_type()) {
+ (SetIndex::Int(keys), DataType::Int32) => {
+ BooleanArray::from_unary(column.as_primitive::<Int32Type>(), |x| {
+ keys.contains(&x) ^ negated
+ })
+ }
+ (SetIndex::Long(keys), DataType::Int64) => {
+ BooleanArray::from_unary(column.as_primitive::<Int64Type>(), |x| {
+ keys.contains(&x) ^ negated
+ })
+ }
+ (SetIndex::String(keys), DataType::Utf8) => {
+ BooleanArray::from_unary(column.as_string::<i32>(), |s|
keys.contains(s) ^ negated)
+ }
+ (SetIndex::String(keys), DataType::LargeUtf8) => {
+ BooleanArray::from_unary(column.as_string::<i64>(), |s|
keys.contains(s) ^ negated)
+ }
+ (SetIndex::String(keys), DataType::Utf8View) => {
+ BooleanArray::from_unary(column.as_string_view(), |s|
keys.contains(s) ^ negated)
+ }
+ _ => return None,
+ })
+}
Review Comment:
Should `probe_set` handle dictionary-encoded columns? A Parquet file whose
embedded `ARROW:schema` declares a dictionary type comes back from the decoder
as a dictionary array. Files migrated from non-Iceberg writers often carry
Arrow types like this. I wrote a `Dictionary(Int32, Utf8)` column with
`ArrowWriter` and read it through `ArrowReader` with a 64-string `IN`.
`set_predicate` saw `Dictionary(Int32, Utf8)`, the index was built, and
`probe_set` returned `None`, so every batch took the per-literal loop.
DataFusion's `InListExpr` handles this case with
[`DictionaryFilter`](https://github.com/apache/datafusion/blob/904afffc731637c4c927c8e095ed07fb195a6c79/datafusion/physical-expr/src/expressions/in_list/dictionary_filter.rs#L28-L33).
It probes the dictionary values once and then uses `take` with the keys, which
carries key nulls through. The same shape fits here:
```suggestion
fn probe_set(
index: &SetIndex,
column: &dyn Array,
negated: bool,
) -> std::result::Result<Option<BooleanArray>, ArrowError> {
if let Some(dictionary) = column.as_any_dictionary_opt() {
let Some(values) = probe_set(index, dictionary.values().as_ref(),
negated)? else {
return Ok(None);
};
return Ok(Some(
take(&values, dictionary.keys(), None)?.as_boolean().clone(),
));
}
Ok(Some(match (index, column.data_type()) {
(SetIndex::Int(keys), DataType::Int32) => {
BooleanArray::from_unary(column.as_primitive::<Int32Type>(), |x|
{
keys.contains(&x) ^ negated
})
}
(SetIndex::Long(keys), DataType::Int64) => {
BooleanArray::from_unary(column.as_primitive::<Int64Type>(), |x|
{
keys.contains(&x) ^ negated
})
}
(SetIndex::String(keys), DataType::Utf8) => {
BooleanArray::from_unary(column.as_string::<i32>(), |s|
keys.contains(s) ^ negated)
}
(SetIndex::String(keys), DataType::LargeUtf8) => {
BooleanArray::from_unary(column.as_string::<i64>(), |s|
keys.contains(s) ^ negated)
}
(SetIndex::String(keys), DataType::Utf8View) => {
BooleanArray::from_unary(column.as_string_view(), |s|
keys.contains(s) ^ negated)
}
_ => return Ok(None),
}))
}
```
This needs `use arrow_select::take::take;`, and the call in `set_predicate`
becomes:
```rust
if let Some(index) = &index
&& let Some(result) = probe_set(index, column.as_ref(),
negated)?
{
return Ok(result);
}
```
Adding `DataType::Dictionary(Box::new(DataType::Int32),
Box::new(DataType::Utf8))` to the encodings in
`string_set_filters_match_across_arrow_encodings` covers it. This probes every
dictionary value in each batch, including values no key references. That is
still one pass over the dictionary, where the current loop makes one pass per
literal.
##########
crates/iceberg/src/arrow/reader/predicate_visitor.rs:
##########
@@ -791,6 +825,85 @@ mod tests {
predicate_fn(batch).unwrap()
}
+ fn check_set_filter(column: ArrayRef, ty: PrimitiveType, literals:
Vec<Datum>) {
Review Comment:
`check_set_filter` compares results, and the hash probe and the scalar loop
return the same results. So these tests pass whether or not the index is used.
I deleted the `Int64` and `Utf8View` arms from `probe_set`, and both
`integer_set_filters_preserve_nulls_and_physical_casts` and
`string_set_filters_match_across_arrow_encodings` still passed. Could we add a
test that calls `probe_set` directly and checks that each supported column type
returns `Some`?
```rust
#[test]
fn set_index_probes_supported_column_types() {
use arrow_array::{Int32Array, Int64Array, StringArray};
use arrow_cast::cast::cast;
use super::probe_set;
use crate::expr::BoundPredicate;
let index = |ty, literals: Vec<Datum>| {
let schema = Arc::new(
Schema::builder()
.with_fields([NestedField::optional(1, "key",
Type::Primitive(ty)).into()])
.build()
.unwrap(),
);
let BoundPredicate::Set(set) = Reference::new("key")
.is_in(literals)
.bind(schema, true)
.unwrap()
else {
panic!("expected a set predicate");
};
set.membership_index().unwrap()
};
let ints = index(PrimitiveType::Int,
(0..64).map(Datum::int).collect());
let longs = index(PrimitiveType::Long,
(0..64).map(Datum::long).collect());
let strings = index(
PrimitiveType::String,
(0..64).map(|i| Datum::string(i.to_string())).collect(),
);
let int_column: ArrayRef = Arc::new(Int32Array::from(vec![1, 100]));
let long_column: ArrayRef = Arc::new(Int64Array::from(vec![1, 100]));
let string_column: ArrayRef = Arc::new(StringArray::from(vec!["1",
"100"]));
let expected = Some(BooleanArray::from(vec![true, false]));
assert_eq!(probe_set(&ints, &int_column, false), expected);
assert_eq!(probe_set(&longs, &long_column, false), expected);
for ty in [DataType::Utf8, DataType::LargeUtf8, DataType::Utf8View] {
let column = cast(&string_column, &ty).unwrap();
assert_eq!(probe_set(&strings, &column, false), expected);
}
// An Int32 file column under a promoted long field takes the scalar
path.
assert_eq!(probe_set(&longs, &int_column, false), None);
}
```
With the dictionary change, `probe_set` returns a `Result`, so each
assertion needs an `.unwrap()`, and the encodings loop can include the
dictionary type.
##########
crates/iceberg/src/expr/predicate.rs:
##########
@@ -286,7 +344,19 @@ impl<T> SetExpression<T> {
/// Return the hash set of values compared against the term in this
expression.
pub fn literals(&self) -> &FnvHashSet<Datum> {
- &self.literals
+ &self.literals.values
+ }
+
+ pub(crate) fn membership_index(&self) -> Option<Arc<SetIndex>> {
+ // Short lists benefit from Arrow's vectorized scalar comparisons.
+ const MIN_INDEX_SIZE: usize = 32;
+ if self.literals().len() < MIN_INDEX_SIZE {
+ return None;
+ }
+ self.literals
+ .index
+ .get_or_init(|| SetIndex::new(self.literals()).map(Arc::new))
+ .clone()
Review Comment:
Could the 32-literal cutoff live in the reader instead of in
`SetExpression`? The comment explains it in terms of Arrow's scalar comparison
kernels, which is a reader concern. `predicate.rs` doesn't otherwise know about
Arrow, and the Arrow evaluation lives in `PredicateConverter`.
`membership_index()` can build the index whenever it's asked, and
`set_predicate` can decide whether to ask:
```suggestion
pub(crate) fn membership_index(&self) -> Option<Arc<SetIndex>> {
self.literals
.index
.get_or_init(|| SetIndex::new(self.literals()).map(Arc::new))
.clone()
}
```
and in `predicate_visitor.rs`:
```rust
/// Shorter `IN` lists are faster with Arrow's vectorized scalar comparisons
than with a hash probe.
const MIN_INDEX_SIZE: usize = 32;
// in set_predicate
let index = if set.literals().len() >= MIN_INDEX_SIZE {
set.membership_index()
} else {
None
};
```
On the value itself, the DataFusion table in the description suggests the
hash set wins well below 32. At 31 keys this PR still runs the per-literal loop
and takes 16.11 ms. At 32 keys it switches to the hash set and takes 5.40 ms.
At 16 keys the loop takes 10.76 ms, twice what the hash set takes at 32.
DataFusion's `InListExpr` never runs one comparison pass per literal for a
constant list. It uses a [branchless compare for up to 32 four-byte or 16
eight-byte
values](https://github.com/apache/datafusion/blob/904afffc731637c4c927c8e095ed07fb195a6c79/datafusion/physical-expr/src/expressions/in_list/branchless_filter.rs#L84-L95)
and a hash set above that. I'm not suggesting we port the branchless filter.
Could you add cases at 4, 8, 16, and 32 literals, for strings and Int64, to the
harness in #3741, and set the cutoff from those numbers?
##########
crates/iceberg/src/expr/predicate.rs:
##########
@@ -820,9 +889,27 @@ mod tests {
use std::sync::Arc;
use crate::expr::Predicate::{AlwaysFalse, AlwaysTrue};
- use crate::expr::{Bind, BoundPredicate, Reference};
+ use crate::expr::{Bind, BoundPredicate, Predicate, Reference};
use crate::spec::{Datum, NestedField, PrimitiveType, Schema, SchemaRef,
Type};
+ #[test]
+ fn cloned_set_predicates_share_the_index_and_serialize_as_literals() {
+ let predicate = Reference::new("key").is_in((0..64).map(Datum::int));
+ let encoded = serde_json::to_value(&predicate).unwrap();
+ assert_eq!(encoded["Set"]["literals"].as_array().unwrap().len(), 64);
+ let restored: Predicate =
serde_json::from_value(encoded.clone()).unwrap();
+ let clone = predicate.clone().not().rewrite_not();
+ let (Predicate::Set(original), Predicate::Set(negated)) = (&predicate,
&clone) else {
+ panic!("expected set predicates");
+ };
+ assert!(Arc::ptr_eq(
+ &original.membership_index().unwrap(),
+ &negated.membership_index().unwrap()
+ ));
+ assert_eq!(predicate, restored);
+ assert_eq!(serde_json::to_value(&predicate).unwrap(), encoded);
+ }
+
Review Comment:
This test checks sharing on an unbound `Predicate`, but the reader shares
the index through a `BoundPredicate`. Each file task clones the bound
predicate, and the reader calls
[`rewrite_not`](https://github.com/apache/iceberg-rust/blob/0c658b41e4a7df48f3362aa21056783a87b05696/crates/iceberg/src/arrow/reader/pipeline.rs#L558)
on it, which goes through
[`BoundPredicate::negate`](https://github.com/apache/iceberg-rust/blob/0c658b41e4a7df48f3362aa21056783a87b05696/crates/iceberg/src/expr/predicate.rs#L824-L827)
for a `NOT`. If `BoundPredicate::negate` went back to
`SetExpression::new(...)`, this test would still pass and every file would
build its own index. Could the test bind first?
```suggestion
#[test]
fn cloned_set_predicates_share_the_index_and_serialize_as_literals() {
let predicate = Reference::new("bar")
.is_in((0..64).map(Datum::int))
.bind(table_schema_simple(), true)
.unwrap();
let encoded = serde_json::to_value(&predicate).unwrap();
assert_eq!(encoded["Set"]["literals"].as_array().unwrap().len(), 64);
let restored: BoundPredicate =
serde_json::from_value(encoded.clone()).unwrap();
let clone = predicate.clone().negate().rewrite_not();
let (BoundPredicate::Set(original), BoundPredicate::Set(negated)) =
(&predicate, &clone)
else {
panic!("expected set predicates");
};
assert!(Arc::ptr_eq(
&original.membership_index().unwrap(),
&negated.membership_index().unwrap()
));
assert_eq!(predicate, restored);
assert_eq!(serde_json::to_value(&predicate).unwrap(), encoded);
}
```
The `Predicate` import in the test module becomes unused with this change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]