Skip to content

Commit 33a3f38

Browse files
Handle dictionary IN LIST inputs in one place
Wrap the selected filter when the input is dictionary encoded, instead of teaching every filter implementation how to unpack dictionary keys. Plain inputs continue to use their filter directly. Flatten nested dictionary values before choosing a filter, and cover dictionary key types, nested dictionaries, nulls, timestamps, decimals, and scalar inputs.
1 parent c396e6a commit 33a3f38

8 files changed

Lines changed: 291 additions & 80 deletions

File tree

‎datafusion/physical-expr/src/expressions/in_list.rs‎

Lines changed: 28 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@ use datafusion_expr::{ColumnarValue, expr_vec_fmt};
3838

3939
mod array_static_filter;
4040
mod branchless_filter;
41+
mod dictionary_filter;
4142
mod fixed_size_binary_filter;
4243
mod primitive_filter;
4344
mod result;
@@ -216,7 +217,7 @@ impl InListExpr {
216217
expr,
217218
list,
218219
negated,
219-
Some(instantiate_static_filter(array)?),
220+
Some(instantiate_static_filter(array, &expr_data_type)?),
220221
))
221222
}
222223

@@ -243,7 +244,7 @@ impl InListExpr {
243244

244245
// Try to create a static filter if all list expressions are constants
245246
let static_filter = match try_evaluate_constant_list(&list, schema)? {
246-
Some(in_array) => Some(instantiate_static_filter(in_array)?),
247+
Some(in_array) => Some(instantiate_static_filter(in_array, &expr_data_type)?),
247248
None => None, // Non-constant expressions, fall back to dynamic evaluation
248249
};
249250

@@ -1265,6 +1266,31 @@ mod tests {
12651266
Ok(())
12661267
}
12671268

1269+
#[test]
1270+
fn in_list_nested_dictionary_scalar() -> Result<()> {
1271+
let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
1272+
let batch = RecordBatch::try_new(
1273+
Arc::new(schema.clone()),
1274+
vec![Arc::new(Int32Array::from(vec![0, 0, 0]))],
1275+
)?;
1276+
let needle = lit(ScalarValue::Dictionary(
1277+
Box::new(DataType::Int16),
1278+
Box::new(ScalarValue::Dictionary(
1279+
Box::new(DataType::Int8),
1280+
Box::new(ScalarValue::Int32(Some(2))),
1281+
)),
1282+
));
1283+
1284+
let expr = in_list(needle, vec![lit(1_i32), lit(2_i32)], &false, &schema)?;
1285+
let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
1286+
assert_eq!(
1287+
as_boolean_array(&result),
1288+
&BooleanArray::from(vec![true, true, true])
1289+
);
1290+
1291+
Ok(())
1292+
}
1293+
12681294
#[test]
12691295
fn in_list_utf8_with_dict_types() -> Result<()> {
12701296
fn dict_lit(key_type: DataType, value: &str) -> Arc<dyn PhysicalExpr> {

‎datafusion/physical-expr/src/expressions/in_list/array_static_filter.rs‎

Lines changed: 2 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -15,12 +15,9 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
use arrow::array::{
19-
Array, ArrayRef, BooleanArray, downcast_array, downcast_dictionary_array,
20-
make_comparator,
21-
};
18+
use arrow::array::{Array, ArrayRef, BooleanArray, make_comparator};
2219
use arrow::buffer::{BooleanBuffer, NullBuffer};
23-
use arrow::compute::{SortOptions, take};
20+
use arrow::compute::SortOptions;
2421
use arrow::datatypes::DataType;
2522
use arrow::util::bit_iterator::BitIndexIterator;
2623
use datafusion_common::Result;
@@ -141,22 +138,6 @@ impl StaticFilter for ArrayStaticFilter {
141138
));
142139
}
143140

144-
// Unwrap dictionary-encoded needles when the value type matches
145-
// in_array, evaluating against the dictionary values and mapping
146-
// back via keys.
147-
downcast_dictionary_array! {
148-
v => {
149-
// Only unwrap when the haystack (in_array) type matches
150-
// the dictionary value type
151-
if v.values().data_type() == self.in_array.data_type() {
152-
let values_contains = self.contains(v.values().as_ref(), negated)?;
153-
let result = take(&values_contains, v.keys(), None)?;
154-
return Ok(downcast_array(result.as_ref()));
155-
}
156-
}
157-
_ => {}
158-
}
159-
160141
self.find_needles_in_haystack(v, negated)
161142
}
162143
}

‎datafusion/physical-expr/src/expressions/in_list/branchless_filter.rs‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -77,7 +77,7 @@ use arrow::util::bit_iterator::BitIndexIterator;
7777
use datafusion_common::{Result, exec_datafusion_err, internal_datafusion_err};
7878

7979
use super::result::build_result_from_contains;
80-
use super::static_filter::{StaticFilter, handle_dictionary};
80+
use super::static_filter::StaticFilter;
8181

8282
pub(super) type BranchlessNative<T> =
8383
<<T as BranchlessFilterType>::CompareType as ArrowPrimitiveType>::Native;
@@ -256,8 +256,6 @@ where
256256
}
257257

258258
fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
259-
handle_dictionary!(self, v, negated);
260-
261259
// Arrow compatibility ignores timestamp timezone and decimal precision/scale
262260
// while still requiring the same primitive representation.
263261
if !PrimitiveArray::<T>::is_compatible(v.data_type()) {
Lines changed: 161 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,161 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
use arrow::array::{Array, AsArray, BooleanArray};
19+
use arrow::compute::take;
20+
use arrow::datatypes::DataType;
21+
use datafusion_common::Result;
22+
23+
use super::static_filter::{StaticFilter, StaticFilterRef};
24+
25+
/// Adds dictionary-encoded needle support to a filter that expects plain arrays.
26+
/// This wrapper is only used when the input expression returns dictionaries.
27+
pub(super) struct DictionaryFilter {
28+
inner: StaticFilterRef,
29+
}
30+
31+
impl DictionaryFilter {
32+
pub(super) fn new(inner: StaticFilterRef) -> Self {
33+
Self { inner }
34+
}
35+
}
36+
37+
impl StaticFilter for DictionaryFilter {
38+
fn null_count(&self) -> usize {
39+
self.inner.null_count()
40+
}
41+
42+
fn contains(&self, needles: &dyn Array, negated: bool) -> Result<BooleanArray> {
43+
let Some(dictionary) = needles.as_any_dictionary_opt() else {
44+
return self.inner.contains(needles, negated);
45+
};
46+
let values = dictionary.values();
47+
let values_contains = if matches!(values.data_type(), DataType::Dictionary(_, _))
48+
{
49+
self.contains(values.as_ref(), negated)?
50+
} else {
51+
self.inner.contains(values.as_ref(), negated)?
52+
};
53+
let result = take(&values_contains, dictionary.keys(), None)?;
54+
Ok(result.as_boolean().clone())
55+
}
56+
}
57+
58+
#[cfg(test)]
59+
mod tests {
60+
use std::sync::Arc;
61+
62+
use arrow::array::{
63+
ArrayRef, Decimal128Array, DictionaryArray, Int8Array, Int16Array, Int32Array,
64+
Int64Array, TimestampNanosecondArray, UInt8Array, UInt16Array, UInt32Array,
65+
UInt64Array,
66+
};
67+
68+
use super::super::strategy::instantiate_static_filter;
69+
use super::*;
70+
71+
#[test]
72+
fn dictionary_needles_support_all_key_types() -> Result<()> {
73+
let values: ArrayRef = Arc::new(Int32Array::from(vec![1, 2]));
74+
let expected = BooleanArray::from(vec![Some(true), Some(false), None]);
75+
76+
macro_rules! check_keys {
77+
($keys:expr) => {{
78+
let needles = DictionaryArray::try_new($keys, Arc::clone(&values))?;
79+
let filter = instantiate_static_filter(
80+
Arc::new(Int32Array::from(vec![1, 3])),
81+
needles.data_type(),
82+
)?;
83+
assert_eq!(filter.contains(&needles, false)?, expected);
84+
}};
85+
}
86+
87+
check_keys!(Int8Array::from(vec![Some(0), Some(1), None]));
88+
check_keys!(Int16Array::from(vec![Some(0), Some(1), None]));
89+
check_keys!(Int32Array::from(vec![Some(0), Some(1), None]));
90+
check_keys!(Int64Array::from(vec![Some(0), Some(1), None]));
91+
check_keys!(UInt8Array::from(vec![Some(0), Some(1), None]));
92+
check_keys!(UInt16Array::from(vec![Some(0), Some(1), None]));
93+
check_keys!(UInt32Array::from(vec![Some(0), Some(1), None]));
94+
check_keys!(UInt64Array::from(vec![Some(0), Some(1), None]));
95+
96+
Ok(())
97+
}
98+
99+
#[test]
100+
fn nested_dictionary_needles_preserve_nulls() -> Result<()> {
101+
let values: ArrayRef = Arc::new(Int32Array::from(vec![Some(1), Some(2), None]));
102+
let inner: ArrayRef = Arc::new(DictionaryArray::try_new(
103+
Int8Array::from(vec![0, 1, 2]),
104+
values,
105+
)?);
106+
let needles = DictionaryArray::try_new(
107+
Int16Array::from(vec![Some(0), Some(1), Some(2), None]),
108+
inner,
109+
)?;
110+
let filter = instantiate_static_filter(
111+
Arc::new(Int32Array::from(vec![1, 3])),
112+
needles.data_type(),
113+
)?;
114+
115+
assert_eq!(
116+
filter.contains(&needles, false)?,
117+
BooleanArray::from(vec![Some(true), Some(false), None, None])
118+
);
119+
assert_eq!(
120+
filter.contains(&needles, true)?,
121+
BooleanArray::from(vec![Some(false), Some(true), None, None])
122+
);
123+
124+
Ok(())
125+
}
126+
127+
#[test]
128+
fn dictionary_timestamp_needles_keep_timezone_compatibility() -> Result<()> {
129+
let timestamps: ArrayRef =
130+
Arc::new(TimestampNanosecondArray::from(vec![1, 3]).with_timezone("UTC"));
131+
let values: ArrayRef = Arc::new(
132+
TimestampNanosecondArray::from(vec![1, 2]).with_timezone("Europe/Paris"),
133+
);
134+
let needles = DictionaryArray::try_new(Int8Array::from(vec![0, 1]), values)?;
135+
let filter = instantiate_static_filter(timestamps, needles.data_type())?;
136+
assert_eq!(
137+
filter.contains(&needles, false)?,
138+
BooleanArray::from(vec![true, false])
139+
);
140+
141+
Ok(())
142+
}
143+
144+
#[test]
145+
fn dictionary_decimal_needles_keep_precision_scale_compatibility() -> Result<()> {
146+
// Five list values use the hash-set filter.
147+
let decimals: ArrayRef = Arc::new(
148+
Decimal128Array::from(vec![1, 3, 5, 7, 9]).with_precision_and_scale(10, 2)?,
149+
);
150+
let values: ArrayRef =
151+
Arc::new(Decimal128Array::from(vec![1, 2]).with_precision_and_scale(11, 3)?);
152+
let needles = DictionaryArray::try_new(Int8Array::from(vec![0, 1]), values)?;
153+
let filter = instantiate_static_filter(decimals, needles.data_type())?;
154+
assert_eq!(
155+
filter.contains(&needles, false)?,
156+
BooleanArray::from(vec![true, false])
157+
);
158+
159+
Ok(())
160+
}
161+
}

‎datafusion/physical-expr/src/expressions/in_list/fixed_size_binary_filter.rs‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ use arrow::datatypes::{
5353
use datafusion_common::{Result, exec_datafusion_err, internal_datafusion_err};
5454

5555
use super::primitive_filter::instantiate_primitive_filter;
56-
use super::static_filter::{StaticFilter, StaticFilterRef, handle_dictionary};
56+
use super::static_filter::{StaticFilter, StaticFilterRef};
5757

5858
/// Reinterpret fixed-size binary values as same-width primitive values.
5959
///
@@ -99,8 +99,6 @@ where
9999
}
100100

101101
fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
102-
handle_dictionary!(self, v, negated);
103-
104102
if v.data_type() != &self.data_type {
105103
return Err(exec_datafusion_err!(
106104
"FixedSizeBinary filter: expected {} array, got {}",
@@ -165,6 +163,7 @@ mod tests {
165163
use arrow::buffer::{Buffer, MutableBuffer, NullBuffer};
166164
use arrow::datatypes::Int8Type;
167165

166+
use super::super::dictionary_filter::DictionaryFilter;
168167
use super::*;
169168

170169
fn value(width: i32, index: usize, miss: bool) -> Vec<u8> {
@@ -268,7 +267,7 @@ mod tests {
268267

269268
#[test]
270269
fn handles_dictionary_needles() -> Result<()> {
271-
let filter = make_filter(4, &[Some(value(4, 7, false))])?;
270+
let filter = DictionaryFilter::new(make_filter(4, &[Some(value(4, 7, false))])?);
272271
let dictionary_values: ArrayRef = Arc::new(array(
273272
4,
274273
&[Some(value(4, 7, false)), Some(value(4, 8, false))],

‎datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs‎

Lines changed: 15 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -19,17 +19,18 @@
1919
//!
2020
//! This module provides membership tests for Arrow primitive types.
2121
22+
use std::hash::{Hash, Hasher};
23+
use std::marker::PhantomData;
24+
use std::sync::Arc;
25+
2226
use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
2327
use arrow::datatypes::*;
2428
use arrow::util::bit_iterator::BitIndexIterator;
2529
use datafusion_common::{HashSet, Result, exec_datafusion_err};
26-
use std::hash::{Hash, Hasher};
27-
use std::marker::PhantomData;
28-
use std::sync::Arc;
2930

3031
use super::branchless_filter::{BranchlessFilter, BranchlessFilterType};
3132
use super::result::build_in_list_result;
32-
use super::static_filter::{StaticFilter, StaticFilterRef, handle_dictionary};
33+
use super::static_filter::{StaticFilter, StaticFilterRef};
3334

3435
/// Selects an optimized filter for a primitive representation.
3536
///
@@ -311,7 +312,6 @@ where
311312
}
312313

313314
fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
314-
handle_dictionary!(self, v, negated);
315315
let v = v.as_primitive_opt::<T>().ok_or_else(|| {
316316
exec_datafusion_err!("BitmapFilter: expected {} array", T::DATA_TYPE)
317317
})?;
@@ -432,8 +432,6 @@ where
432432
}
433433

434434
fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
435-
handle_dictionary!(self, v, negated);
436-
437435
let v = v.as_primitive_opt::<T>().ok_or_else(|| {
438436
exec_datafusion_err!(
439437
"PrimitiveHashSetFilter: expected {} array",
@@ -465,6 +463,8 @@ mod tests {
465463
};
466464
use half::f16;
467465

466+
use super::super::dictionary_filter::DictionaryFilter;
467+
468468
fn uint32_array(values: Vec<Option<u32>>) -> ArrayRef {
469469
Arc::new(UInt32Array::from(values))
470470
}
@@ -553,13 +553,19 @@ mod tests {
553553
#[test]
554554
fn bitmap_filter_u8_handles_dictionary_needles() -> Result<()> {
555555
let haystack: ArrayRef = Arc::new(UInt8Array::from(vec![Some(1), None, Some(3)]));
556-
let filter = BitmapFilter::<UInt8Type>::try_new(&haystack)?;
556+
let inner: StaticFilterRef =
557+
Arc::new(BitmapFilter::<UInt8Type>::try_new(&haystack)?);
558+
let filter = DictionaryFilter::new(inner);
557559

558560
let keys = Int8Array::from(vec![Some(0), Some(1), None, Some(2)]);
559561
let values = Arc::new(UInt8Array::from(vec![Some(1), Some(2), Some(3)]));
560562
let needles = DictionaryArray::try_new(keys, values)?;
561563

562-
assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])
564+
assert_eq!(
565+
filter.contains(&needles, false)?,
566+
BooleanArray::from(vec![Some(true), None, None, Some(true)])
567+
);
568+
Ok(())
563569
}
564570

565571
#[test]

0 commit comments

Comments
 (0)