alamb commented on code in PR #23014:
URL: https://github.com/apache/datafusion/pull/23014#discussion_r3632044957
##########
datafusion/physical-expr/src/expressions/in_list/strategy.rs:
##########
@@ -20,32 +20,102 @@ use std::sync::Arc;
use arrow::array::ArrayRef;
use arrow::compute::cast;
use arrow::datatypes::{
- DataType, Float16Type, Int8Type, Int16Type, UInt8Type, UInt16Type,
+ DataType, Date32Type, Date64Type, Decimal128Type, DurationMicrosecondType,
+ DurationMillisecondType, DurationNanosecondType, DurationSecondType,
Float16Type,
+ Float32Type, Float64Type, Int8Type, Int16Type, Int32Type, Int64Type,
+ IntervalMonthDayNanoType, IntervalUnit, Time32MillisecondType,
Time32SecondType,
+ Time64MicrosecondType, Time64NanosecondType, TimeUnit,
TimestampMicrosecondType,
+ TimestampMillisecondType, TimestampNanosecondType, TimestampSecondType,
UInt8Type,
+ UInt16Type, UInt32Type, UInt64Type,
};
use datafusion_common::Result;
use super::array_static_filter::ArrayStaticFilter;
use super::primitive_filter::*;
use super::static_filter::StaticFilter;
-pub(super) fn instantiate_static_filter(
- in_array: ArrayRef,
-) -> Result<Arc<dyn StaticFilter + Send + Sync>> {
+type StaticFilterRef = Arc<dyn StaticFilter + Send + Sync>;
+
+pub(super) fn instantiate_static_filter(in_array: ArrayRef) ->
Result<StaticFilterRef> {
+ let in_array = flatten_dictionary_haystack(in_array)?;
+
+ if let Some(filter) = instantiate_branchless_filter(&in_array)? {
+ return Ok(filter);
+ }
+
+ instantiate_standard_filter(in_array)
+}
+
+fn flatten_dictionary_haystack(in_array: ArrayRef) -> Result<ArrayRef> {
// Flatten dictionary-encoded haystacks to their value type so that
// specialized filters (e.g. Int32StaticFilter) are used instead of
// falling through to the generic ArrayStaticFilter.
- let in_array = match in_array.data_type() {
- DataType::Dictionary(_, value_type) => cast(&in_array,
value_type.as_ref())?,
- _ => in_array,
- };
match in_array.data_type() {
- DataType::Int8 =>
Ok(Arc::new(BitmapFilter::<Int8Type>::try_new(&in_array)?)),
- DataType::UInt8 =>
Ok(Arc::new(BitmapFilter::<UInt8Type>::try_new(&in_array)?)),
- DataType::Int16 =>
Ok(Arc::new(BitmapFilter::<Int16Type>::try_new(&in_array)?)),
- DataType::UInt16 =>
Ok(Arc::new(BitmapFilter::<UInt16Type>::try_new(&in_array)?)),
- DataType::Float16 => {
- Ok(Arc::new(BitmapFilter::<Float16Type>::try_new(&in_array)?))
+ DataType::Dictionary(_, value_type) => Ok(cast(&in_array,
value_type.as_ref())?),
+ _ => Ok(in_array),
+ }
+}
+
+fn instantiate_branchless_filter(in_array: &ArrayRef) ->
Result<Option<StaticFilterRef>> {
+ let non_null_count = in_array.len() - in_array.null_count();
+
+ macro_rules! filter {
+ ($arrow_type:ty) => {
+ branchless_filter::<$arrow_type>(in_array, non_null_count)
+ };
+ }
+
+ match in_array.data_type() {
Review Comment:
i found it somewhat hard to follow by reading the code to understand what
cases would use the branchless filter and what would use the bitmap filter for
small integer types -- because the cases that are covered by branchless filters
are behind some macros and then the bitmap filtering happens only if there
isn't a matchess branchless filter
I am not sure there is a concrete action to take from this observation
##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -222,6 +223,241 @@ where
}
}
+pub(super) type BranchlessNative<T> =
+ <<T as BranchlessFilterType>::CompareType as ArrowPrimitiveType>::Native;
+
+/// Maximum list size for branchless lookup on 1-byte primitives.
+///
+/// Sixteen 1-byte values fit in one 128-bit SIMD vector, so this keeps the
+/// branchless list small enough for a single vectorized membership check.
+const BRANCHLESS_MAX_1B: usize = 16;
+
+/// Maximum list size for branchless lookup on 2-byte primitives.
+///
+/// Eight 2-byte values fit in one 128-bit SIMD vector, so this keeps the
+/// branchless list small enough for a single vectorized membership check.
+const BRANCHLESS_MAX_2B: usize = 8;
+
+/// Maximum list size for branchless lookup on 4-byte primitives.
+///
+/// Thirty-two 4-byte values keep the inline list at 128 bytes. Beyond that,
+/// the comparison chain and filter footprint grow enough that the hash/generic
+/// fallback is a better fit.
+const BRANCHLESS_MAX_4B: usize = 32;
+
+/// Maximum list size for branchless lookup on 8-byte primitives.
+///
+/// Sixteen 8-byte values use the same 128-byte inline-list budget as 4-byte
+/// primitives. Larger lists are left to the hash/generic fallback.
+const BRANCHLESS_MAX_8B: usize = 16;
+
+/// Maximum list size for branchless lookup on 16-byte primitives.
+///
+/// These comparisons are wider, so this path is limited to four values.
+/// Larger lists are left to the generic fallback.
+const BRANCHLESS_MAX_16B: usize = 4;
+
+/// Arrow primitive types supported by [`BranchlessFilter`].
+///
+/// `T` is the logical Arrow type accepted by the filter. `CompareType` is the
+/// same-width type used for the fixed comparison chain. Signed integers,
+/// floats, and temporal values use an unsigned comparison type so they compare
+/// by their raw bit pattern.
+pub(super) trait BranchlessFilterType:
+ ArrowPrimitiveType + Send + Sync + 'static
+{
+ type CompareType: ArrowPrimitiveType + Send + Sync + 'static;
+
+ /// Maximum number of non-null IN-list values to handle with
+ /// [`BranchlessFilter`] for this primitive type.
+ const MAX_LIST_LEN: usize;
+}
+
+macro_rules! branchless_filter_type {
+ ($logical:ty, $compare:ty, $max_len:expr) => {
+ // The branchless filter reads the same Arrow value buffer as the
+ // comparison type. That is only valid when both native types have the
+ // same width, so catch any bad mapping here at compile time.
+ const _: () = assert!(
+ size_of::<<$logical as ArrowPrimitiveType>::Native>()
+ == size_of::<<$compare as ArrowPrimitiveType>::Native>(),
+ "BranchlessFilterType::CompareType must use the same native width"
+ );
+
+ impl BranchlessFilterType for $logical {
+ type CompareType = $compare;
+ const MAX_LIST_LEN: usize = $max_len;
+ }
+ };
+}
+
+branchless_filter_type!(Int8Type, UInt8Type, BRANCHLESS_MAX_1B);
Review Comment:
Given we now have fast bitmap filter implementations for 8 and 16 bit
integer types, what extra value do branchless filters give over those bitmaps?
UNless the performance win is compelling, I suggest we simply use the bitmap
implementation for those types
##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -222,6 +223,241 @@ where
}
}
+pub(super) type BranchlessNative<T> =
+ <<T as BranchlessFilterType>::CompareType as ArrowPrimitiveType>::Native;
+
+/// Maximum list size for branchless lookup on 1-byte primitives.
+///
+/// Sixteen 1-byte values fit in one 128-bit SIMD vector, so this keeps the
+/// branchless list small enough for a single vectorized membership check.
+const BRANCHLESS_MAX_1B: usize = 16;
+
+/// Maximum list size for branchless lookup on 2-byte primitives.
+///
+/// Eight 2-byte values fit in one 128-bit SIMD vector, so this keeps the
+/// branchless list small enough for a single vectorized membership check.
+const BRANCHLESS_MAX_2B: usize = 8;
+
+/// Maximum list size for branchless lookup on 4-byte primitives.
+///
+/// Thirty-two 4-byte values keep the inline list at 128 bytes. Beyond that,
+/// the comparison chain and filter footprint grow enough that the hash/generic
+/// fallback is a better fit.
+const BRANCHLESS_MAX_4B: usize = 32;
+
+/// Maximum list size for branchless lookup on 8-byte primitives.
+///
+/// Sixteen 8-byte values use the same 128-byte inline-list budget as 4-byte
+/// primitives. Larger lists are left to the hash/generic fallback.
+const BRANCHLESS_MAX_8B: usize = 16;
+
+/// Maximum list size for branchless lookup on 16-byte primitives.
+///
+/// These comparisons are wider, so this path is limited to four values.
+/// Larger lists are left to the generic fallback.
+const BRANCHLESS_MAX_16B: usize = 4;
+
+/// Arrow primitive types supported by [`BranchlessFilter`].
+///
+/// `T` is the logical Arrow type accepted by the filter. `CompareType` is the
+/// same-width type used for the fixed comparison chain. Signed integers,
+/// floats, and temporal values use an unsigned comparison type so they compare
+/// by their raw bit pattern.
+pub(super) trait BranchlessFilterType:
+ ArrowPrimitiveType + Send + Sync + 'static
+{
+ type CompareType: ArrowPrimitiveType + Send + Sync + 'static;
+
+ /// Maximum number of non-null IN-list values to handle with
+ /// [`BranchlessFilter`] for this primitive type.
+ const MAX_LIST_LEN: usize;
+}
+
+macro_rules! branchless_filter_type {
+ ($logical:ty, $compare:ty, $max_len:expr) => {
+ // The branchless filter reads the same Arrow value buffer as the
+ // comparison type. That is only valid when both native types have the
+ // same width, so catch any bad mapping here at compile time.
+ const _: () = assert!(
Review Comment:
my reading of this loop is that it instantiates max_len copies of the
branchless filter
##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -222,6 +223,241 @@ where
}
}
+pub(super) type BranchlessNative<T> =
Review Comment:
as a follow on, it might be nice to reorganize the branchless filters in
their own module (where then the branchless filtering strategy could be
documented more concretely)
##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -222,6 +223,241 @@ where
}
}
+pub(super) type BranchlessNative<T> =
+ <<T as BranchlessFilterType>::CompareType as ArrowPrimitiveType>::Native;
+
+/// Maximum list size for branchless lookup on 1-byte primitives.
+///
+/// Sixteen 1-byte values fit in one 128-bit SIMD vector, so this keeps the
+/// branchless list small enough for a single vectorized membership check.
+const BRANCHLESS_MAX_1B: usize = 16;
+
+/// Maximum list size for branchless lookup on 2-byte primitives.
+///
+/// Eight 2-byte values fit in one 128-bit SIMD vector, so this keeps the
+/// branchless list small enough for a single vectorized membership check.
+const BRANCHLESS_MAX_2B: usize = 8;
+
+/// Maximum list size for branchless lookup on 4-byte primitives.
+///
+/// Thirty-two 4-byte values keep the inline list at 128 bytes. Beyond that,
+/// the comparison chain and filter footprint grow enough that the hash/generic
+/// fallback is a better fit.
+const BRANCHLESS_MAX_4B: usize = 32;
+
+/// Maximum list size for branchless lookup on 8-byte primitives.
+///
+/// Sixteen 8-byte values use the same 128-byte inline-list budget as 4-byte
+/// primitives. Larger lists are left to the hash/generic fallback.
+const BRANCHLESS_MAX_8B: usize = 16;
+
+/// Maximum list size for branchless lookup on 16-byte primitives.
+///
+/// These comparisons are wider, so this path is limited to four values.
+/// Larger lists are left to the generic fallback.
+const BRANCHLESS_MAX_16B: usize = 4;
+
+/// Arrow primitive types supported by [`BranchlessFilter`].
+///
+/// `T` is the logical Arrow type accepted by the filter. `CompareType` is the
+/// same-width type used for the fixed comparison chain. Signed integers,
+/// floats, and temporal values use an unsigned comparison type so they compare
+/// by their raw bit pattern.
+pub(super) trait BranchlessFilterType:
+ ArrowPrimitiveType + Send + Sync + 'static
+{
+ type CompareType: ArrowPrimitiveType + Send + Sync + 'static;
+
+ /// Maximum number of non-null IN-list values to handle with
+ /// [`BranchlessFilter`] for this primitive type.
+ const MAX_LIST_LEN: usize;
+}
+
+macro_rules! branchless_filter_type {
+ ($logical:ty, $compare:ty, $max_len:expr) => {
+ // The branchless filter reads the same Arrow value buffer as the
+ // comparison type. That is only valid when both native types have the
+ // same width, so catch any bad mapping here at compile time.
+ const _: () = assert!(
+ size_of::<<$logical as ArrowPrimitiveType>::Native>()
+ == size_of::<<$compare as ArrowPrimitiveType>::Native>(),
+ "BranchlessFilterType::CompareType must use the same native width"
+ );
+
+ impl BranchlessFilterType for $logical {
+ type CompareType = $compare;
+ const MAX_LIST_LEN: usize = $max_len;
+ }
+ };
+}
+
+branchless_filter_type!(Int8Type, UInt8Type, BRANCHLESS_MAX_1B);
+branchless_filter_type!(UInt8Type, UInt8Type, BRANCHLESS_MAX_1B);
+branchless_filter_type!(Int16Type, UInt16Type, BRANCHLESS_MAX_2B);
+branchless_filter_type!(UInt16Type, UInt16Type, BRANCHLESS_MAX_2B);
+branchless_filter_type!(Float16Type, UInt16Type, BRANCHLESS_MAX_2B);
+
+branchless_filter_type!(Int32Type, UInt32Type, BRANCHLESS_MAX_4B);
Review Comment:
> const BRANCHLESS_MAX_4B: usize = 32;
do I read the code above that this is creating 32 specializations (just) for
UInt32 IN lists
--
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]
