You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/11 21:32:48 UTC
(datafusion) branch gh-readonly-queue/main/pr-24088-f8cc678272c50c781a56b74b49912b999aebd89e created (now 3fe41a225f)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-24088-f8cc678272c50c781a56b74b49912b999aebd89e
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 3fe41a225f IN LIST: optimize Utf8View and BinaryView filters (#24088)
This branch includes the following new commits:
new 3fe41a225f IN LIST: optimize Utf8View and BinaryView filters (#24088)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: IN LIST: optimize Utf8View and BinaryView filters (#24088)
Posted by gi...@apache.org.
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-24088-f8cc678272c50c781a56b74b49912b999aebd89e
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 3fe41a225ffbbc0d09ba16c0757afa40604fcd1c
Author: Geoffrey Claude <ge...@gmail.com>
AuthorDate: Fri Sep 11 21:32:25 2026 +0000
IN LIST: optimize Utf8View and BinaryView filters (#24088)
## Which issue does this PR close?
- Part of #19241.
- Stacked on [#24102](https://github.com/apache/datafusion/pull/24102).
## Rationale for this change
Arrow represents every `Utf8View` and `BinaryView` value with a 16-byte
view. When a value is at most 12 bytes long, the complete value is
stored directly in that view:
```text
32-bit length | up to 12 value bytes, zero-padded
```
Equal short values therefore have the same 128-bit view. DataFusion can
look up that view directly, without reading another buffer or using
Arrow's general value comparison.
This PR uses that faster path when every non-null value in the `IN` list
is at most 12 bytes long. The byte-view adapter treats each inline view
as a `Decimal128` key and passes it to the shared primitive selector
from [#24283](https://github.com/apache/datafusion/pull/24283), the same
selector used by #24102:
- Lists with up to four non-null values use the direct-comparison filter
from #23014.
- Lists with 5 or more use the shared 128-bit hash-set filter.
`Decimal128` is only a 16-byte container here; no decimal operations are
performed.
A longer input value cannot match a short list value because its encoded
length is different, so it can be rejected without reading its backing
bytes. If the list itself contains a value longer than 12 bytes,
DataFusion keeps using the general filter.
Null list entries do not affect this choice, but are still recorded for
SQL null behavior. After unwrapping any dictionary, the input and list
must use the same view type: `Utf8View` is not mixed with `BinaryView`,
and regular `Utf8` and `Binary` keep their existing paths.
## What changes are included in this PR?
- Adds the short-value path for `Utf8View` and `BinaryView`.
- Passes the 128-bit keys to the shared primitive selector instead of
making a separate filter choice.
- Keeps the general filter for longer list values or mismatched types.
- Preserves slices, dictionaries, nulls, `IN`, and `NOT IN`.
## Are these changes tested?
Tests cover both view types and both faster paths; the 4/5-value and
12/13-byte boundaries; long inputs and lists that require the general
filter; exact-type routing; slices and dictionaries; input and list
nulls; and `IN` and `NOT IN`.
## Are there any user-facing changes?
No. SQL results and public APIs are unchanged.
## Automated benchmark snapshot
[Automated
run](https://github.com/apache/datafusion/pull/24088#issuecomment-5280507974)
on an aarch64 Neoverse V2 runner, comparing
[#24102](https://github.com/apache/datafusion/pull/24102) with this PR
at exact commit `00dd083e`. The benchmark evaluates 8,192-row batches
after filter construction. Lower is better.
All 15 reported rows improved, with a 35.9% geometric-mean time
reduction.
| Benchmark | Before | After | Change |
|---|---:|---:|---:|
| `utf8view/short_8b/list=4/match=0%` | 18.7 us | 11.6 us | -38.0%
(1.61x faster) |
| `utf8view/short_8b/list=4/match=50%` | 39.3 us | 11.6 us | -70.5%
(3.39x faster) |
| `utf8view/short_8b/list=16/match=0%` | 18.9 us | 14.1 us | -25.4%
(1.34x faster) |
| `utf8view/short_8b/list=16/match=50%` | 39.6 us | 30.1 us | -24.0%
(1.32x faster) |
| `utf8view/short_8b/list=64/match=0%` | 18.6 us | 13.4 us | -28.0%
(1.39x faster) |
| `utf8view/short_8b/list=64/match=50%` | 38.5 us | 28.4 us | -26.2%
(1.36x faster) |
| `utf8view/short_8b/list=256/match=0%` | 18.5 us | 13.4 us | -27.6%
(1.38x faster) |
| `utf8view/short_8b/list=256/match=50%` | 38.3 us | 25.7 us | -32.9%
(1.49x faster) |
| `utf8view/len_12b/list=16/match=0%` | 18.6 us | 15.4 us | -17.2%
(1.21x faster) |
| `utf8view/len_12b/list=16/match=50%` | 40.0 us | 18.3 us | -54.2%
(2.19x faster) |
| `utf8view/len_12b/list=64/match=0%` | 18.7 us | 13.7 us | -26.7%
(1.36x faster) |
| `utf8view/len_12b/list=64/match=50%` | 39.6 us | 25.9 us | -34.6%
(1.53x faster) |
| `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%` | 38.7 us | 25.8
us | -33.3% (1.50x faster) |
| `nulls/utf8view/short_8b/list=16/match=50%/nulls=20%/NOT_IN` | 38.5 us
| 24.7 us | -35.8% (1.56x faster) |
| `nulls/utf8view/short_8b/list=16/match=50%/nulls=50%` | 29.2 us | 17.8
us | -39.0% (1.64x faster) |
---
.../physical-expr/src/expressions/in_list.rs | 18 ++
.../src/expressions/in_list/byte_view_filter.rs | 227 +++++++++++++++++++++
.../src/expressions/in_list/strategy.rs | 35 +++-
3 files changed, 279 insertions(+), 1 deletion(-)
diff --git a/datafusion/physical-expr/src/expressions/in_list.rs b/datafusion/physical-expr/src/expressions/in_list.rs
index 0a4ad0b804..7a7cb25317 100644
--- a/datafusion/physical-expr/src/expressions/in_list.rs
+++ b/datafusion/physical-expr/src/expressions/in_list.rs
@@ -38,6 +38,7 @@ use datafusion_expr::{ColumnarValue, expr_vec_fmt};
mod array_static_filter;
mod branchless_filter;
+mod byte_view_filter;
mod dictionary_filter;
mod fixed_size_binary_filter;
mod primitive_filter;
@@ -3648,6 +3649,23 @@ mod tests {
)?
);
+ // Utf8View in_array, Utf8View and Dict(Utf8View) needles
+ let utf8view_in =
+ Arc::new(StringViewArray::from(vec!["a", "b", "c", "d", "e"])) as ArrayRef;
+ let utf8view_needle =
+ Arc::new(StringViewArray::from(vec!["a", "missing", "b"])) as ArrayRef;
+ assert_eq!(
+ expected,
+ eval_in_list_from_array(
+ Arc::clone(&utf8view_needle),
+ Arc::clone(&utf8view_in),
+ )?
+ );
+ assert_eq!(
+ expected,
+ eval_in_list_from_array(wrap_in_dict(utf8view_needle), utf8view_in)?
+ );
+
// Struct in_array, Struct needle: multi-column join
let struct_fields = Fields::from(vec![
Field::new("c0", DataType::Utf8, true),
diff --git a/datafusion/physical-expr/src/expressions/in_list/byte_view_filter.rs b/datafusion/physical-expr/src/expressions/in_list/byte_view_filter.rs
new file mode 100644
index 0000000000..9d4ea1fdfb
--- /dev/null
+++ b/datafusion/physical-expr/src/expressions/in_list/byte_view_filter.rs
@@ -0,0 +1,227 @@
+// 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.
+
+//! Filters for `Utf8View` and `BinaryView` `IN` lists whose non-null values are
+//! at most 12 bytes.
+//!
+//! Arrow stores such values directly in a `u128` view: the low 32 bits contain
+//! the length and the remaining bits contain zero-padded bytes. Comparing two
+//! inline views compares their complete values. Long views contain a prefix and
+//! buffer location instead, so a list containing one uses the generic filter.
+//!
+//! Lists with up to four non-null values use the existing 128-bit branchless
+//! filter. Larger lists use the primitive hash-set filter over the same 128
+//! bits. `Decimal128Type` is only a carrier; no decimal operations are used.
+//! A long input value cannot match an inline list value because its length is
+//! part of the view.
+
+use std::sync::Arc;
+
+use arrow::array::{
+ Array, ArrayRef, AsArray, BooleanArray, MAX_INLINE_VIEW_LEN, PrimitiveArray,
+};
+use arrow::buffer::{NullBuffer, ScalarBuffer};
+use arrow::datatypes::{DataType, Decimal128Type};
+use arrow::util::bit_iterator::BitIndexIterator;
+use datafusion_common::{Result, exec_datafusion_err, internal_datafusion_err};
+
+use super::primitive_filter::instantiate_primitive_filter;
+use super::static_filter::{StaticFilter, StaticFilterRef};
+
+fn is_inline(view: u128) -> bool {
+ (view as u32) <= MAX_INLINE_VIEW_LEN
+}
+
+fn all_inline(views: &ScalarBuffer<u128>, nulls: Option<&NullBuffer>) -> bool {
+ match nulls {
+ Some(nulls) => {
+ BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
+ .all(|idx| is_inline(views[idx]))
+ }
+ None => views.iter().copied().all(is_inline),
+ }
+}
+
+fn as_decimal128(
+ views: &ScalarBuffer<u128>,
+ nulls: Option<&NullBuffer>,
+) -> PrimitiveArray<Decimal128Type> {
+ // `views.inner()` is already sliced to the array's offset.
+ let values = ScalarBuffer::<i128>::new(views.inner().clone(), 0, views.len());
+ PrimitiveArray::<Decimal128Type>::new(values, nulls.cloned())
+}
+
+/// Adapts the selected primitive filter to the original byte-view type.
+///
+/// Arrow requires unused inline bytes to be zero, so equal values have equal
+/// `u128` views.
+struct ByteViewFilter {
+ data_type: DataType,
+ inner: StaticFilterRef,
+}
+
+impl StaticFilter for ByteViewFilter {
+ fn null_count(&self) -> usize {
+ self.inner.null_count()
+ }
+
+ fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
+ let (views, nulls) = match &self.data_type {
+ DataType::Utf8View => v.as_string_view_opt().map(|a| (a.views(), a.nulls())),
+ DataType::BinaryView => {
+ v.as_binary_view_opt().map(|a| (a.views(), a.nulls()))
+ }
+ _ => unreachable!(),
+ }
+ .ok_or_else(|| {
+ exec_datafusion_err!(
+ "Expected concrete {} array, got {}",
+ self.data_type,
+ v.data_type()
+ )
+ })?;
+ // List values are all inline (len <= 12). Long input views cannot match
+ // because their encoded length (> 12) is part of the 128-bit key, so
+ // input lengths do not need to be checked.
+ let decimal = as_decimal128(views, nulls);
+ self.inner.contains(&decimal, negated)
+ }
+}
+
+/// Returns a filter when every non-null byte view is inline.
+pub(super) fn instantiate_byte_view_filter(
+ in_array: &ArrayRef,
+) -> Result<Option<StaticFilterRef>> {
+ let views = match in_array.data_type() {
+ DataType::Utf8View => in_array.as_string_view().views(),
+ DataType::BinaryView => in_array.as_binary_view().views(),
+ _ => return Ok(None),
+ };
+
+ if !all_inline(views, in_array.nulls()) {
+ return Ok(None);
+ }
+
+ let primitive: ArrayRef = Arc::new(as_decimal128(views, in_array.nulls()));
+ let inner = instantiate_primitive_filter(&primitive)?.ok_or_else(|| {
+ internal_datafusion_err!(
+ "Byte view filter: no primitive filter for {}",
+ primitive.data_type()
+ )
+ })?;
+ Ok(Some(Arc::new(ByteViewFilter {
+ data_type: in_array.data_type().clone(),
+ inner,
+ })))
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use arrow::array::{BinaryViewArray, StringViewArray};
+
+ fn assert_contains(
+ filter: &dyn StaticFilter,
+ needles: &dyn Array,
+ expected: Vec<Option<bool>>,
+ ) -> Result<()> {
+ assert_eq!(
+ filter.contains(needles, false)?,
+ BooleanArray::from(expected)
+ );
+ Ok(())
+ }
+
+ #[test]
+ fn large_list_nulls_and_slices() -> Result<()> {
+ let haystack: ArrayRef = Arc::new(
+ StringViewArray::from(vec![
+ Some("outside"),
+ Some("a"),
+ Some("b"),
+ None,
+ Some("c"),
+ Some("d"),
+ Some("e"),
+ Some("tail"),
+ ])
+ .slice(1, 6),
+ );
+ let filter = instantiate_byte_view_filter(&haystack)?.unwrap();
+ let needles = StringViewArray::from(vec![
+ Some("outside"),
+ Some("b"),
+ Some("missing"),
+ None,
+ Some("e"),
+ Some("tail"),
+ ])
+ .slice(1, 4);
+
+ assert_contains(&*filter, &needles, vec![Some(true), None, None, Some(true)])?;
+ assert_eq!(
+ filter.contains(&needles, true)?,
+ BooleanArray::from(vec![Some(false), None, None, Some(false)])
+ );
+ Ok(())
+ }
+
+ #[test]
+ fn routing_and_boundaries() -> Result<()> {
+ let inline = "abcdefghijkl";
+ let long = "abcdefghijklm";
+ let needles = StringViewArray::from(vec![inline, long, "missing"]);
+
+ // Covers both sides of the shared primitive-filter cutoff.
+ for values in [
+ vec![inline, "one", "two", "three"],
+ vec![inline, "one", "two", "three", "four"],
+ ] {
+ let haystack = Arc::new(StringViewArray::from(values)) as ArrayRef;
+ let filter = instantiate_byte_view_filter(&haystack)?.unwrap();
+ assert_contains(
+ &*filter,
+ &needles,
+ vec![Some(true), Some(false), Some(false)],
+ )?;
+ }
+
+ let mixed: ArrayRef = Arc::new(StringViewArray::from(vec!["short", long]));
+ assert!(instantiate_byte_view_filter(&mixed)?.is_none());
+
+ let binary: ArrayRef = Arc::new(BinaryViewArray::from(vec![
+ b"a".as_slice(),
+ b"b".as_slice(),
+ b"c".as_slice(),
+ b"d".as_slice(),
+ b"e".as_slice(),
+ ]));
+ let filter = instantiate_byte_view_filter(&binary)?.unwrap();
+ let needles = BinaryViewArray::from(vec![b"a".as_slice(), b"z".as_slice()]);
+ assert_contains(&*filter, &needles, vec![Some(true), Some(false)])?;
+
+ let mismatch_err = filter
+ .contains(&StringViewArray::from(vec!["a"]), false)
+ .unwrap_err();
+ assert!(
+ mismatch_err
+ .to_string()
+ .contains("Expected concrete BinaryView array, got Utf8View")
+ );
+ Ok(())
+ }
+}
diff --git a/datafusion/physical-expr/src/expressions/in_list/strategy.rs b/datafusion/physical-expr/src/expressions/in_list/strategy.rs
index 093752cce0..5cbdf8cd74 100644
--- a/datafusion/physical-expr/src/expressions/in_list/strategy.rs
+++ b/datafusion/physical-expr/src/expressions/in_list/strategy.rs
@@ -23,6 +23,7 @@ use arrow::datatypes::DataType;
use datafusion_common::Result;
use super::array_static_filter::ArrayStaticFilter;
+use super::byte_view_filter::instantiate_byte_view_filter;
use super::dictionary_filter::DictionaryFilter;
use super::fixed_size_binary_filter::instantiate_fixed_size_binary_filter;
use super::primitive_filter::instantiate_primitive_filter;
@@ -34,7 +35,11 @@ pub(super) fn instantiate_static_filter(
) -> Result<StaticFilterRef> {
let in_array = flatten_dictionary_haystack(in_array)?;
- let filter = if let Some(filter) = instantiate_fixed_size_binary_filter(&in_array)? {
+ let filter = if view_types_match(needle_data_type, in_array.data_type())
+ && let Some(filter) = instantiate_byte_view_filter(&in_array)?
+ {
+ filter
+ } else if let Some(filter) = instantiate_fixed_size_binary_filter(&in_array)? {
filter
} else if let Some(filter) = instantiate_primitive_filter(&in_array)? {
filter
@@ -51,6 +56,20 @@ pub(super) fn instantiate_static_filter(
}
}
+/// Raw view access requires the expression and list to use the same view type.
+/// Dictionary wrappers do not change the expression's value type.
+fn view_types_match(needle_type: &DataType, list_type: &DataType) -> bool {
+ matches!(list_type, DataType::Utf8View | DataType::BinaryView)
+ && dictionary_value_type(needle_type) == list_type
+}
+
+fn dictionary_value_type(mut data_type: &DataType) -> &DataType {
+ while let DataType::Dictionary(_, value_type) = data_type {
+ data_type = value_type;
+ }
+ data_type
+}
+
fn flatten_dictionary_haystack(mut in_array: ArrayRef) -> Result<ArrayRef> {
// Flatten every dictionary layer so the final value type can use a
// specialized filter.
@@ -109,4 +128,18 @@ mod tests {
Ok(())
}
+
+ #[test]
+ fn byte_view_routing_requires_same_physical_type() {
+ let dict_view =
+ DataType::Dictionary(Box::new(DataType::Int8), Box::new(DataType::Utf8View));
+
+ assert!(view_types_match(&DataType::Utf8View, &DataType::Utf8View));
+ assert!(view_types_match(&dict_view, &DataType::Utf8View));
+ assert!(!view_types_match(
+ &DataType::Utf8View,
+ &DataType::BinaryView
+ ));
+ assert!(!view_types_match(&DataType::Utf8, &DataType::Utf8View));
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org