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]

Reply via email to