Skip to content

Commit 1bf24c9

Browse files
IN LIST: Handle dictionary inputs once (apache#24662)
## Which issue does this PR close? - Closes apache#24658. - Stacked on apache#24102. ## Rationale for this change Dictionary handling is currently repeated in each concrete `IN LIST` filter. That makes `datafusion-physical-expr` substantially larger to compile and link. ## What changes are included in this PR? Dictionary-encoded inputs use one small wrapper around the selected filter. The filter checks each dictionary value once, then maps those results through the dictionary keys. Plain inputs continue to call their selected filter directly. Nested dictionary list values are flattened before choosing a filter. This preserves SQL null behavior while still allowing the final value type to use its specialized filter. The PR also adds small-batch Criterion cases for both plain and dictionary inputs. ### Measurements Measured locally on an M1 Max against the exact apache#24102 head plus the benchmark-only commit. | Size measurement | Before | After | Change | |---|---:|---:|---:| | `datafusion-physical-expr` LLVM IR | 675,256 lines | 647,201 lines | -4.15% | | `StaticFilter::contains` LLVM IR | 33,502 lines | 5,343 lines | -84.05% | | Release benchmark Mach-O `__text` | 8,713,520 bytes | 8,500,880 bytes | -2.44% | Focused Criterion benchmarks found no material regression. In the automated AArch64 run, dictionary inputs had 15–26% lower latency at batch sizes 1–64, while 8,192-row and plain-input cases were unchanged ([full results](apache#24662 (comment))). ## Are these changes tested? Yes. Tests cover every dictionary key type, nested dictionaries, dictionary nulls, unreferenced null values, timestamp timezones, decimal metadata, and nested dictionary scalar inputs. - `cargo test -p datafusion-physical-expr --all-features` (1,694 passed, 1 ignored; 13 doctests passed) - `cargo clippy --all-targets --all-features -- -D warnings` - `cargo fmt --all` ## Are there any user-facing changes? No. This keeps the existing `IN LIST` behavior while reducing generated code.
1 parent 2d2f82c commit 1bf24c9

9 files changed

Lines changed: 340 additions & 81 deletions

File tree

‎datafusion/physical-expr/benches/in_list_strategy.rs‎

Lines changed: 56 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,7 @@
4545
//! | Utf8View length-12 cases | Utf8View | 12-byte strings | 16, 64 |
4646
//! | Utf8View long-string cases | Utf8View | 24-byte strings | 4, 16, 64, 256 |
4747
//! | Shared-prefix string cases | Utf8, Utf8View | same prefix, different suffix | 16, 32, 64 |
48+
//! | Dictionary dispatch cases | Int32, Dictionary<Int32> | per-batch dispatch overhead | 4, 64 |
4849
//! | Fixed-size binary direct-comparison case | FixedSizeBinary(1) | direct-comparison cutoff | 16 |
4950
//! | Fixed-size binary direct-comparison case | FixedSizeBinary(16) | direct-comparison cutoff | 4 |
5051
//! | Fixed-size binary bitmap case | FixedSizeBinary(2) | bitmap lookup | 64 |
@@ -871,6 +872,60 @@ fn bench_dictionary(c: &mut Criterion) {
871872
bench_dict_string(c, "utf8_short/dict=500/list=20", 500, 20, 10);
872873
}
873874

875+
/// Measures the fixed per-batch cost of handling dictionary and plain inputs.
876+
/// Small batches make dispatch overhead visible, while the standard 8,192-row
877+
/// batch shows whether it matters in the usual vectorized case.
878+
fn bench_dictionary_dispatch(c: &mut Criterion) {
879+
for list_size in [4_usize, 64] {
880+
let strategy = if list_size == 4 {
881+
"branchless"
882+
} else {
883+
"hash_set"
884+
};
885+
let haystack = (0..list_size as i32).collect::<Vec<_>>();
886+
887+
for batch_size in [1, 8, 64, ARRAY_SIZE] {
888+
let keys = (0..batch_size)
889+
.map(|index| (index % 8) as i32)
890+
.collect::<Vec<_>>();
891+
let values = keys.iter().map(|key| key * 2).collect::<Vec<_>>();
892+
893+
for dictionary in [false, true] {
894+
let array: ArrayRef = if dictionary {
895+
Arc::new(
896+
DictionaryArray::<Int32Type>::try_new(
897+
Int32Array::from(keys.clone()),
898+
Arc::new(Int32Array::from_iter_values((0..8).map(|v| v * 2))),
899+
)
900+
.unwrap(),
901+
)
902+
} else {
903+
Arc::new(Int32Array::from(values.clone()))
904+
};
905+
906+
let schema =
907+
Schema::new(vec![Field::new("a", array.data_type().clone(), false)]);
908+
let exprs = haystack.iter().map(|value| lit(*value)).collect();
909+
let expr =
910+
in_list(col("a", &schema).unwrap(), exprs, &false, &schema).unwrap();
911+
let batch = RecordBatch::try_new(Arc::new(schema), vec![array]).unwrap();
912+
let encoding = if dictionary { "dictionary" } else { "plain" };
913+
914+
c.bench_with_input(
915+
BenchmarkId::new(
916+
"dictionary_dispatch",
917+
format!(
918+
"i32/{strategy}/{encoding}/list={list_size}/batch={batch_size}"
919+
),
920+
),
921+
&batch,
922+
|b, batch| b.iter(|| expr.evaluate(batch).unwrap()),
923+
);
924+
}
925+
}
926+
}
927+
}
928+
874929
// =============================================================================
875930
// NULL HANDLING BENCHMARKS
876931
// =============================================================================
@@ -1204,7 +1259,7 @@ fn bench_fixed_size_binary(c: &mut Criterion) {
12041259
criterion_group! {
12051260
name = benches;
12061261
config = Criterion::default();
1207-
targets = bench_narrow_integer, bench_primitive, bench_f32, bench_timestamp_ns, bench_interval_month_day_nano, bench_utf8, bench_utf8view, bench_dictionary, bench_nulls, bench_fixed_size_binary
1262+
targets = bench_narrow_integer, bench_primitive, bench_f32, bench_timestamp_ns, bench_interval_month_day_nano, bench_utf8, bench_utf8view, bench_dictionary, bench_dictionary_dispatch, bench_nulls, bench_fixed_size_binary
12081263
}
12091264

12101265
criterion_main!(benches);

‎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: 154 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,154 @@
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 datafusion_common::Result;
21+
22+
use super::static_filter::{StaticFilter, StaticFilterRef};
23+
24+
/// Adds dictionary-encoded needle support to a filter that expects plain arrays.
25+
/// This wrapper is only used when the input expression returns dictionaries.
26+
pub(super) struct DictionaryFilter {
27+
inner: StaticFilterRef,
28+
}
29+
30+
impl DictionaryFilter {
31+
pub(super) fn new(inner: StaticFilterRef) -> Self {
32+
Self { inner }
33+
}
34+
}
35+
36+
impl StaticFilter for DictionaryFilter {
37+
fn null_count(&self) -> usize {
38+
self.inner.null_count()
39+
}
40+
41+
fn contains(&self, needles: &dyn Array, negated: bool) -> Result<BooleanArray> {
42+
let Some(dictionary) = needles.as_any_dictionary_opt() else {
43+
return self.inner.contains(needles, negated);
44+
};
45+
let values_contains = self.contains(dictionary.values().as_ref(), negated)?;
46+
let result = take(&values_contains, dictionary.keys(), None)?;
47+
Ok(result.as_boolean().clone())
48+
}
49+
}
50+
51+
#[cfg(test)]
52+
mod tests {
53+
use std::sync::Arc;
54+
55+
use arrow::array::{
56+
ArrayRef, Decimal128Array, DictionaryArray, Int8Array, Int16Array, Int32Array,
57+
Int64Array, TimestampNanosecondArray, UInt8Array, UInt16Array, UInt32Array,
58+
UInt64Array,
59+
};
60+
61+
use super::super::strategy::instantiate_static_filter;
62+
use super::*;
63+
64+
#[test]
65+
fn dictionary_needles_support_all_key_types() -> Result<()> {
66+
let values: ArrayRef = Arc::new(Int32Array::from(vec![1, 2]));
67+
let expected = BooleanArray::from(vec![Some(true), Some(false), None]);
68+
69+
macro_rules! check_keys {
70+
($keys:expr) => {{
71+
let needles = DictionaryArray::try_new($keys, Arc::clone(&values))?;
72+
let filter = instantiate_static_filter(
73+
Arc::new(Int32Array::from(vec![1, 3])),
74+
needles.data_type(),
75+
)?;
76+
assert_eq!(filter.contains(&needles, false)?, expected);
77+
}};
78+
}
79+
80+
check_keys!(Int8Array::from(vec![Some(0), Some(1), None]));
81+
check_keys!(Int16Array::from(vec![Some(0), Some(1), None]));
82+
check_keys!(Int32Array::from(vec![Some(0), Some(1), None]));
83+
check_keys!(Int64Array::from(vec![Some(0), Some(1), None]));
84+
check_keys!(UInt8Array::from(vec![Some(0), Some(1), None]));
85+
check_keys!(UInt16Array::from(vec![Some(0), Some(1), None]));
86+
check_keys!(UInt32Array::from(vec![Some(0), Some(1), None]));
87+
check_keys!(UInt64Array::from(vec![Some(0), Some(1), None]));
88+
89+
Ok(())
90+
}
91+
92+
#[test]
93+
fn nested_dictionary_needles_preserve_nulls() -> Result<()> {
94+
let values: ArrayRef = Arc::new(Int32Array::from(vec![Some(1), Some(2), None]));
95+
let inner: ArrayRef = Arc::new(DictionaryArray::try_new(
96+
Int8Array::from(vec![0, 1, 2]),
97+
values,
98+
)?);
99+
let needles = DictionaryArray::try_new(
100+
Int16Array::from(vec![Some(0), Some(1), Some(2), None]),
101+
inner,
102+
)?;
103+
let filter = instantiate_static_filter(
104+
Arc::new(Int32Array::from(vec![1, 3])),
105+
needles.data_type(),
106+
)?;
107+
108+
assert_eq!(
109+
filter.contains(&needles, false)?,
110+
BooleanArray::from(vec![Some(true), Some(false), None, None])
111+
);
112+
assert_eq!(
113+
filter.contains(&needles, true)?,
114+
BooleanArray::from(vec![Some(false), Some(true), None, None])
115+
);
116+
117+
Ok(())
118+
}
119+
120+
#[test]
121+
fn dictionary_timestamp_needles_keep_timezone_compatibility() -> Result<()> {
122+
let timestamps: ArrayRef =
123+
Arc::new(TimestampNanosecondArray::from(vec![1, 3]).with_timezone("UTC"));
124+
let values: ArrayRef = Arc::new(
125+
TimestampNanosecondArray::from(vec![1, 2]).with_timezone("Europe/Paris"),
126+
);
127+
let needles = DictionaryArray::try_new(Int8Array::from(vec![0, 1]), values)?;
128+
let filter = instantiate_static_filter(timestamps, needles.data_type())?;
129+
assert_eq!(
130+
filter.contains(&needles, false)?,
131+
BooleanArray::from(vec![true, false])
132+
);
133+
134+
Ok(())
135+
}
136+
137+
#[test]
138+
fn dictionary_decimal_needles_keep_precision_scale_compatibility() -> Result<()> {
139+
// Five list values use the hash-set filter.
140+
let decimals: ArrayRef = Arc::new(
141+
Decimal128Array::from(vec![1, 3, 5, 7, 9]).with_precision_and_scale(10, 2)?,
142+
);
143+
let values: ArrayRef =
144+
Arc::new(Decimal128Array::from(vec![1, 2]).with_precision_and_scale(11, 3)?);
145+
let needles = DictionaryArray::try_new(Int8Array::from(vec![0, 1]), values)?;
146+
let filter = instantiate_static_filter(decimals, needles.data_type())?;
147+
assert_eq!(
148+
filter.contains(&needles, false)?,
149+
BooleanArray::from(vec![true, false])
150+
);
151+
152+
Ok(())
153+
}
154+
}

‎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))],

0 commit comments

Comments
 (0)