Skip to content

Commit 5141088

Browse files
committed
Optimize Int8 and Int16 IN bitmap filters
1 parent 01bf68c commit 5141088

2 files changed

Lines changed: 96 additions & 15 deletions

File tree

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

Lines changed: 91 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -78,23 +78,57 @@ impl BitmapStorage for Box<[u64; 1024]> {
7878
/// Arrow primitive types supported by [`BitmapFilter`].
7979
///
8080
/// Arrow already defines the Rust value type as `T::Native`. This trait only
81-
/// supplies the bitmap storage size for the two integer domains that are small
82-
/// enough to represent with one bit per possible value.
81+
/// supplies the bitmap storage size and maps values to their bit-pattern index
82+
/// for the two integer domains that are small enough to represent with one bit
83+
/// per possible value.
8384
pub(super) trait BitmapFilterType:
8485
ArrowPrimitiveType + Send + Sync + 'static
8586
{
8687
type Storage: BitmapStorage;
88+
89+
fn index(value: Self::Native) -> usize;
90+
}
91+
92+
/// `Int8` has 256 possible bit patterns, so four `u64` words cover the full domain.
93+
impl BitmapFilterType for Int8Type {
94+
type Storage = [u64; 4];
95+
96+
#[inline(always)]
97+
fn index(value: Self::Native) -> usize {
98+
value as u8 as usize
99+
}
87100
}
88101

89102
/// `UInt8` has 256 possible values, so four `u64` words cover the full domain.
90103
impl BitmapFilterType for UInt8Type {
91104
type Storage = [u64; 4];
105+
106+
#[inline(always)]
107+
fn index(value: Self::Native) -> usize {
108+
value as usize
109+
}
110+
}
111+
112+
/// `Int16` has 65,536 possible bit patterns, so 1,024 `u64` words cover the full
113+
/// domain.
114+
impl BitmapFilterType for Int16Type {
115+
type Storage = Box<[u64; 1024]>;
116+
117+
#[inline(always)]
118+
fn index(value: Self::Native) -> usize {
119+
value as u16 as usize
120+
}
92121
}
93122

94123
/// `UInt16` has 65,536 possible values, so 1,024 `u64` words cover the full
95124
/// domain.
96125
impl BitmapFilterType for UInt16Type {
97126
type Storage = Box<[u64; 1024]>;
127+
128+
#[inline(always)]
129+
fn index(value: Self::Native) -> usize {
130+
value as usize
131+
}
98132
}
99133

100134
/// `IN` filter backed by one bit per possible value.
@@ -121,14 +155,14 @@ where
121155
match prim_array.nulls() {
122156
None => {
123157
for &v in values {
124-
bits.set_bit(v.as_usize());
158+
bits.set_bit(T::index(v));
125159
}
126160
}
127161
Some(nulls) => {
128162
for i in
129163
BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
130164
{
131-
bits.set_bit(values[i].as_usize());
165+
bits.set_bit(T::index(values[i]));
132166
}
133167
}
134168
}
@@ -140,7 +174,7 @@ where
140174

141175
#[inline(always)]
142176
fn check(&self, needle: T::Native) -> bool {
143-
self.bits.get_bit(needle.as_usize())
177+
self.bits.get_bit(T::index(needle))
144178
}
145179
}
146180

@@ -359,9 +393,6 @@ macro_rules! primitive_static_filter {
359393
};
360394
}
361395

362-
// Generate specialized filters for all integer primitive types
363-
primitive_static_filter!(Int8StaticFilter, Int8Type);
364-
primitive_static_filter!(Int16StaticFilter, Int16Type);
365396
primitive_static_filter!(Int32StaticFilter, Int32Type);
366397
primitive_static_filter!(Int64StaticFilter, Int64Type);
367398
primitive_static_filter!(UInt32StaticFilter, UInt32Type);
@@ -384,7 +415,7 @@ mod tests {
384415
use super::*;
385416
use std::sync::Arc;
386417

387-
use arrow::array::{DictionaryArray, Int8Array, UInt8Array, UInt16Array};
418+
use arrow::array::{DictionaryArray, Int8Array, Int16Array, UInt8Array, UInt16Array};
388419

389420
fn assert_contains(
390421
filter: &dyn StaticFilter,
@@ -425,6 +456,28 @@ mod tests {
425456
assert_contains(&filter, &needles, vec![Some(true), None, None, Some(true)])
426457
}
427458

459+
#[test]
460+
fn bitmap_filter_i8_handles_signed_boundaries_and_slices() -> Result<()> {
461+
let haystack: ArrayRef = Arc::new(
462+
Int8Array::from(vec![Some(99), Some(i8::MIN), None, Some(-1), Some(42)])
463+
.slice(1, 3),
464+
);
465+
let filter = BitmapFilter::<Int8Type>::try_new(&haystack)?;
466+
let needles =
467+
Int8Array::from(vec![Some(7), Some(i8::MIN), Some(-1), None]).slice(1, 3);
468+
469+
assert_eq!(
470+
filter.contains(&needles, false)?,
471+
BooleanArray::from(vec![Some(true), Some(true), None])
472+
);
473+
assert_eq!(
474+
filter.contains(&needles, true)?,
475+
BooleanArray::from(vec![Some(false), Some(false), None])
476+
);
477+
478+
Ok(())
479+
}
480+
428481
#[test]
429482
fn bitmap_filter_u16_handles_boundaries_and_nulls() -> Result<()> {
430483
let haystack: ArrayRef = Arc::new(UInt16Array::from(vec![
@@ -449,4 +502,33 @@ mod tests {
449502

450503
Ok(())
451504
}
505+
506+
#[test]
507+
fn bitmap_filter_i16_handles_signed_boundaries_and_slices() -> Result<()> {
508+
let haystack: ArrayRef = Arc::new(
509+
Int16Array::from(vec![
510+
Some(123),
511+
Some(i16::MIN),
512+
None,
513+
Some(-1),
514+
Some(i16::MAX),
515+
])
516+
.slice(1, 4),
517+
);
518+
let filter = BitmapFilter::<Int16Type>::try_new(&haystack)?;
519+
let needles =
520+
Int16Array::from(vec![Some(0), Some(i16::MIN), Some(7), Some(i16::MAX)])
521+
.slice(1, 3);
522+
523+
assert_eq!(
524+
filter.contains(&needles, false)?,
525+
BooleanArray::from(vec![Some(true), None, Some(true)])
526+
);
527+
assert_eq!(
528+
filter.contains(&needles, true)?,
529+
BooleanArray::from(vec![Some(false), None, Some(false)])
530+
);
531+
532+
Ok(())
533+
}
452534
}

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

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ use std::sync::Arc;
1919

2020
use arrow::array::ArrayRef;
2121
use arrow::compute::cast;
22-
use arrow::datatypes::{DataType, UInt8Type, UInt16Type};
22+
use arrow::datatypes::{DataType, Int8Type, Int16Type, UInt8Type, UInt16Type};
2323
use datafusion_common::Result;
2424

2525
use super::array_static_filter::ArrayStaticFilter;
@@ -37,13 +37,12 @@ pub(super) fn instantiate_static_filter(
3737
_ => in_array,
3838
};
3939
match in_array.data_type() {
40-
// Integer primitive types
41-
DataType::Int8 => Ok(Arc::new(Int8StaticFilter::try_new(&in_array)?)),
42-
DataType::Int16 => Ok(Arc::new(Int16StaticFilter::try_new(&in_array)?)),
43-
DataType::Int32 => Ok(Arc::new(Int32StaticFilter::try_new(&in_array)?)),
44-
DataType::Int64 => Ok(Arc::new(Int64StaticFilter::try_new(&in_array)?)),
40+
DataType::Int8 => Ok(Arc::new(BitmapFilter::<Int8Type>::try_new(&in_array)?)),
4541
DataType::UInt8 => Ok(Arc::new(BitmapFilter::<UInt8Type>::try_new(&in_array)?)),
42+
DataType::Int16 => Ok(Arc::new(BitmapFilter::<Int16Type>::try_new(&in_array)?)),
4643
DataType::UInt16 => Ok(Arc::new(BitmapFilter::<UInt16Type>::try_new(&in_array)?)),
44+
DataType::Int32 => Ok(Arc::new(Int32StaticFilter::try_new(&in_array)?)),
45+
DataType::Int64 => Ok(Arc::new(Int64StaticFilter::try_new(&in_array)?)),
4746
DataType::UInt32 => Ok(Arc::new(UInt32StaticFilter::try_new(&in_array)?)),
4847
DataType::UInt64 => Ok(Arc::new(UInt64StaticFilter::try_new(&in_array)?)),
4948
// Float primitive types (use ordered wrappers for Hash/Eq)

0 commit comments

Comments
 (0)