You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "geoffreyclaude (via GitHub)" <gi...@apache.org> on 2026/06/19 05:36:42 UTC

[PR] IN LIST: unify bitmap filter implementations [datafusion]

geoffreyclaude opened a new pull request, #23035:
URL: https://github.com/apache/datafusion/pull/23035

   ## Which issue does this PR close?
   
   - Part of #19241.
   - Stacked on #23012.
   - Next in stack: #23013.
   - Extracted from #19390.
   
   ## Rationale for this change
   
   #23011 and #23012 intentionally introduce the `UInt8` and `UInt16` bitmap filters as concrete implementations. With both widths visible, the shared shape is now clear: each filter builds a fixed-size bitmap from non-null `IN` list values and probes it with the input value's integer bit pattern.
   
   This PR factors that duplicated bitmap machinery behind a small shared configuration trait. It does not add a new lookup strategy or change which data types use bitmap filters. The next PR uses this shared shape to let same-width signed integers reuse the unsigned bitmap storage.
   
   ## What changes are included in this PR?
   
   - Adds `BitmapStorage` for fixed-size bitmap backing stores.
   - Adds `BitmapFilterConfig` to describe the Arrow type, native value, storage, and index conversion for each bitmap domain.
   - Replaces the concrete `UInt8BitmapFilter` and `UInt16BitmapFilter` implementations with `BitmapFilter<C>`.
   - Adds `UInt8BitmapConfig` and `UInt16BitmapConfig`.
   - Keeps `UInt8` and `UInt16` routing behavior unchanged.
   
   ## Are these changes tested?
   
   Yes.
   
   - `cargo fmt --all`
   - `cargo test -p datafusion-physical-expr bitmap_filter_ --lib`
   - `cargo test -p datafusion-physical-expr in_list_int_types --lib`
   - `cargo test -p datafusion-physical-expr test_in_list_from_array_type_combinations --lib`
   - `cargo test -p datafusion-physical-expr test_in_list_dictionary_types --lib`
   - `cargo clippy -p datafusion-physical-expr --all-targets --all-features -- -D warnings`
   
   ## Are there any user-facing changes?
   
   No. This is an internal refactor only.
   
   <!-- codex-benchmark-start -->
   ## Benchmark note
   
   No local benchmark numbers are included for this PR because it is intended to be a behavior-preserving refactor of the bitmap filter implementation. Benchmarks were not rerun for this stack split.
   <!-- codex-benchmark-end -->
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#discussion_r3482819481


##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,106 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
+/// Storage for the bits used by [`BitmapFilter`].
 ///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+/// `BitmapFilter` represents an `IN` list with one bit for each possible
+/// value, so membership checks become direct bit tests. This trait lets the
+/// same filter code use different storage sizes for different integer widths.
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+// `UInt8` has 256 possible values, 0 through 255. One bit per value takes
+// 256 bits, which fits in four `u64` words.
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
-
     #[inline(always)]
-    fn check(&self, needle: u8) -> bool {
-        let index = needle as usize;
-        (self.bits[index / 64] >> (index % 64)) & 1 != 0
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-impl StaticFilter for UInt8BitmapFilter {
-    fn null_count(&self) -> usize {
-        self.null_count
+// `UInt16` has 65,536 possible values. One bit per value takes 65,536 bits,
+// which is 1,024 `u64` words, or 8 KiB. Box the array so the filter stores a
+// pointer instead of carrying an 8 KiB array inline.
+impl BitmapStorage for Box<[u64; 1024]> {
+    #[inline]
+    fn new_zeroed() -> Self {
+        Box::new([0u64; 1024])
     }
-
-    fn contains(&self, v: &dyn Array, negated: bool) -> Result<BooleanArray> {
-        handle_dictionary!(self, v, negated);
-        let v = v.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let input_values = v.values();
-        Ok(build_in_list_result(
-            v.len(),
-            v.nulls(),
-            self.null_count > 0,
-            negated,
-            #[inline(always)]
-            |i| {
-                // SAFETY: `build_in_list_result` invokes this closure for
-                // indices in `0..v.len()`, which matches `input_values.len()`.
-                let needle = unsafe { *input_values.get_unchecked(i) };
-                self.check(needle)
-            },
-        ))
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
+    }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-/// Bitmap filter for O(1) `UInt16` set membership via single bit test.
+/// Arrow primitive types supported by [`BitmapFilter`].
 ///
-/// `UInt16` has 65,536 possible values, so the filter stores membership in an
-/// 8 KiB heap-allocated bitmap instead of using a hash table.
-pub(super) struct UInt16BitmapFilter {
+/// Arrow already defines the Rust value type as `T::Native`. This trait only
+/// supplies the bitmap storage size for the two integer domains that are small
+/// enough to represent with one bit per possible value.
+pub(super) trait BitmapFilterType:

Review Comment:
   😍 



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#issuecomment-4811575397

   
   run benchmark in_list_strategy
   
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#issuecomment-4810253683

   
   run benchmark in_list_strategy
   
   


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#discussion_r3482662235


##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {

Review Comment:
   looks good



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#discussion_r3483020046


##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
+    }
+}
 
+impl BitmapStorage for Box<[u64; 1024]> {
+    #[inline]
+    fn new_zeroed() -> Self {
+        Box::new([0u64; 1024])
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
+    }
     #[inline(always)]
-    fn check(&self, needle: u8) -> bool {
-        let index = needle as usize;
-        (self.bits[index / 64] >> (index % 64)) & 1 != 0
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-impl StaticFilter for UInt8BitmapFilter {
-    fn null_count(&self) -> usize {
-        self.null_count
+pub(super) trait BitmapFilterConfig: Send + Sync + 'static {

Review Comment:
   Still not perfect, but much better I'd say! The LOC diff of the PR dropped, which is usually a good sign... I'm ok to merge as is 😃 



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#issuecomment-4810637051

   🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23035#issuecomment-4810253683)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                                                                HEAD                                   perf_in_list_unify_bitmap_filters
   -----                                                                ----                                   ---------------------------------
   dictionary/i32/dict=10/list=16                                       1.00      7.6±0.01µs        ? ?/sec    1.00      7.6±0.01µs        ? ?/sec
   dictionary/i32/dict=100/list=16                                      1.00      7.8±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=100/list=16/NOT_IN                               1.00      7.7±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=100/list=4                                       1.00      7.7±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=100/list=64                                      1.00      7.7±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=1000/list=16                                     1.00      9.0±0.01µs        ? ?/sec    1.00      9.0±0.01µs        ? ?/sec
   dictionary/utf8_long/dict=100/list=16                                1.00      8.3±0.01µs        ? ?/sec    1.00      8.3±0.01µs        ? ?/sec
   dictionary/utf8_short/dict=50/list=32                                1.00      8.1±0.01µs        ? ?/sec    1.00      8.1±0.01µs        ? ?/sec
   dictionary/utf8_short/dict=50/list=8                                 1.00      8.0±0.01µs        ? ?/sec    1.00      8.0±0.01µs        ? ?/sec
   dictionary/utf8_short/dict=500/list=20                               1.00      9.7±0.03µs        ? ?/sec    1.00      9.6±0.01µs        ? ?/sec
   f32/large_list/list=64/match=0%                                      1.03     16.0±0.11µs        ? ?/sec    1.00     15.5±0.01µs        ? ?/sec
   f32/large_list/list=64/match=50%                                     1.19     27.8±0.38µs        ? ?/sec    1.00     23.3±0.23µs        ? ?/sec
   f32/small_list/list=32/match=0%                                      1.02     16.0±0.23µs        ? ?/sec    1.00     15.6±0.01µs        ? ?/sec
   f32/small_list/list=32/match=50%                                     1.48     27.3±0.27µs        ? ?/sec    1.00     18.5±0.14µs        ? ?/sec
   f32/small_list/list=4/match=0%                                       1.01     15.7±0.02µs        ? ?/sec    1.00     15.5±0.02µs        ? ?/sec
   f32/small_list/list=4/match=50%                                      1.00     27.8±0.31µs        ? ?/sec    1.02     28.4±0.16µs        ? ?/sec
   fixed_size_binary/fsb16/list=10000/match=0%                          1.00     25.3±0.08µs        ? ?/sec    1.00     25.4±0.05µs        ? ?/sec
   fixed_size_binary/fsb16/list=10000/match=50%                         1.05     57.3±0.50µs        ? ?/sec    1.00     54.7±0.34µs        ? ?/sec
   fixed_size_binary/fsb16/list=256/match=0%                            1.03     24.4±0.14µs        ? ?/sec    1.00     23.8±0.23µs        ? ?/sec
   fixed_size_binary/fsb16/list=256/match=50%                           1.02     51.2±0.15µs        ? ?/sec    1.00     50.2±0.74µs        ? ?/sec
   fixed_size_binary/fsb16/list=4/match=0%                              1.00     23.0±0.22µs        ? ?/sec    1.00     23.1±0.06µs        ? ?/sec
   fixed_size_binary/fsb16/list=4/match=50%                             1.01     55.8±0.21µs        ? ?/sec    1.00     55.3±0.48µs        ? ?/sec
   fixed_size_binary/fsb16/list=64/match=0%                             1.02     23.3±0.11µs        ? ?/sec    1.00     22.9±0.02µs        ? ?/sec
   fixed_size_binary/fsb16/list=64/match=50%                            1.00     56.5±0.18µs        ? ?/sec    1.00     56.4±0.20µs        ? ?/sec
   narrow_integer/i16/list=256/match=0%                                 1.03     12.3±0.04µs        ? ?/sec    1.00     11.9±0.01µs        ? ?/sec
   narrow_integer/i16/list=256/match=50%                                1.06     21.0±0.43µs        ? ?/sec    1.00     19.8±0.20µs        ? ?/sec
   narrow_integer/i16/list=4/match=0%                                   1.00     11.9±0.02µs        ? ?/sec    1.00     11.9±0.01µs        ? ?/sec
   narrow_integer/i16/list=4/match=50%                                  1.00     23.4±0.48µs        ? ?/sec    1.02     23.8±0.80µs        ? ?/sec
   narrow_integer/i16/list=64/match=0%                                  1.00     12.7±0.03µs        ? ?/sec    1.01     12.9±0.08µs        ? ?/sec
   narrow_integer/i16/list=64/match=50%                                 1.00     18.4±0.17µs        ? ?/sec    1.11     20.4±0.21µs        ? ?/sec
   narrow_integer/u8/list=16/match=0%                                   1.00      5.2±0.00µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   narrow_integer/u8/list=16/match=50%                                  1.00      5.2±0.00µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   narrow_integer/u8/list=4/match=0%                                    1.00      5.2±0.00µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   narrow_integer/u8/list=4/match=50%                                   1.00      5.2±0.00µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   nulls/narrow_integer/u8/list=16/match=50%/nulls=20%                  1.00      5.3±0.05µs        ? ?/sec    1.00      5.3±0.00µs        ? ?/sec
   nulls/primitive/i32/large_list/list=64/match=50%/nulls=20%           1.22     23.1±0.11µs        ? ?/sec    1.00     18.9±0.14µs        ? ?/sec
   nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%           1.00     22.2±0.52µs        ? ?/sec    1.11     24.6±0.10µs        ? ?/sec
   nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%/NOT_IN    1.01     25.0±0.11µs        ? ?/sec    1.00     24.9±0.10µs        ? ?/sec
   nulls/primitive/i32/small_list/list=16/match=50%/nulls=50%           1.01     17.3±0.07µs        ? ?/sec    1.00     17.1±0.06µs        ? ?/sec
   nulls/utf8/long_24b/list=16/match=50%/nulls=20%                      1.00     71.2±0.36µs        ? ?/sec    1.00     71.2±0.37µs        ? ?/sec
   nulls/utf8/short_8b/list=16/match=50%/nulls=20%                      1.03     63.1±0.27µs        ? ?/sec    1.00     61.0±0.21µs        ? ?/sec
   nulls/utf8view/long_24b/list=16/match=50%/nulls=20%                  1.00     86.8±0.17µs        ? ?/sec    1.00     87.0±0.21µs        ? ?/sec
   nulls/utf8view/short_8b/list=16/match=50%/nulls=20%                  1.00     47.8±0.20µs        ? ?/sec    1.02     49.0±0.23µs        ? ?/sec
   nulls/utf8view/short_8b/list=16/match=50%/nulls=20%/NOT_IN           1.00     47.6±0.24µs        ? ?/sec    1.02     48.8±0.29µs        ? ?/sec
   nulls/utf8view/short_8b/list=16/match=50%/nulls=50%                  1.00     35.4±0.14µs        ? ?/sec    1.02     36.2±0.14µs        ? ?/sec
   primitive/i32/large_list/list=256/match=0%                           1.02     12.2±0.02µs        ? ?/sec    1.00     12.0±0.01µs        ? ?/sec
   primitive/i32/large_list/list=256/match=50%                          1.00     19.5±0.11µs        ? ?/sec    1.07     20.7±0.11µs        ? ?/sec
   primitive/i32/large_list/list=64/match=0%                            1.00     12.0±0.01µs        ? ?/sec    1.02     12.3±0.13µs        ? ?/sec
   primitive/i32/large_list/list=64/match=50%                           1.01     19.9±0.77µs        ? ?/sec    1.00     19.7±0.12µs        ? ?/sec
   primitive/i32/small_list/list=16/match=50%/NOT_IN                    1.00     24.4±0.20µs        ? ?/sec    1.08     26.2±0.28µs        ? ?/sec
   primitive/i32/small_list/list=32/match=0%                            1.06     13.0±0.02µs        ? ?/sec    1.00     12.2±0.03µs        ? ?/sec
   primitive/i32/small_list/list=32/match=50%                           1.00     19.8±0.11µs        ? ?/sec    1.21     24.0±0.44µs        ? ?/sec
   primitive/i32/small_list/list=4/match=0%                             1.00     12.0±0.01µs        ? ?/sec    1.03     12.4±0.01µs        ? ?/sec
   primitive/i32/small_list/list=4/match=50%                            1.00     23.9±0.18µs        ? ?/sec    1.01     24.2±0.25µs        ? ?/sec
   primitive/i64/large_list/list=128/match=0%                           1.00     12.5±0.09µs        ? ?/sec    1.04     12.9±0.06µs        ? ?/sec
   primitive/i64/large_list/list=128/match=50%                          1.00     18.9±0.22µs        ? ?/sec    1.05     19.9±0.18µs        ? ?/sec
   primitive/i64/large_list/list=32/match=0%                            1.08     13.6±0.04µs        ? ?/sec    1.00     12.6±0.14µs        ? ?/sec
   primitive/i64/large_list/list=32/match=50%                           1.00     18.5±0.08µs        ? ?/sec    1.00     18.5±0.10µs        ? ?/sec
   primitive/i64/small_list/list=16/match=0%                            1.00     13.0±0.01µs        ? ?/sec    1.01     13.2±0.02µs        ? ?/sec
   primitive/i64/small_list/list=16/match=50%                           1.00     21.7±0.28µs        ? ?/sec    1.07     23.2±0.36µs        ? ?/sec
   primitive/i64/small_list/list=4/match=0%                             1.03     13.2±0.07µs        ? ?/sec    1.00     12.8±0.02µs        ? ?/sec
   primitive/i64/small_list/list=4/match=50%                            1.05     22.6±0.52µs        ? ?/sec    1.00     21.4±0.09µs        ? ?/sec
   timestamp_ns/large_list/list=32/match=0%                             1.00     17.2±0.01µs        ? ?/sec    1.01     17.3±0.02µs        ? ?/sec
   timestamp_ns/large_list/list=32/match=50%                            1.05     35.3±0.81µs        ? ?/sec    1.00     33.6±0.59µs        ? ?/sec
   timestamp_ns/small_list/list=16/match=0%                             1.00     17.2±0.01µs        ? ?/sec    1.01     17.3±0.01µs        ? ?/sec
   timestamp_ns/small_list/list=16/match=50%                            1.07     36.5±0.55µs        ? ?/sec    1.00     34.2±0.92µs        ? ?/sec
   timestamp_ns/small_list/list=4/match=0%                              1.00     17.1±0.01µs        ? ?/sec    1.00     17.1±0.02µs        ? ?/sec
   timestamp_ns/small_list/list=4/match=50%                             1.00     32.8±0.31µs        ? ?/sec    1.07     35.0±0.49µs        ? ?/sec
   utf8/long_24b/list=256/match=0%                                      1.00     33.6±0.03µs        ? ?/sec    1.00     33.7±0.25µs        ? ?/sec
   utf8/long_24b/list=256/match=50%                                     1.00     71.7±0.51µs        ? ?/sec    1.01     72.4±0.63µs        ? ?/sec
   utf8/long_24b/list=4/match=0%                                        1.00     33.7±0.05µs        ? ?/sec    1.01     34.0±0.03µs        ? ?/sec
   utf8/long_24b/list=4/match=50%                                       1.00     73.2±0.88µs        ? ?/sec    1.00     73.2±0.40µs        ? ?/sec
   utf8/long_24b/list=64/match=0%                                       1.00     33.4±0.03µs        ? ?/sec    1.04     34.6±0.24µs        ? ?/sec
   utf8/long_24b/list=64/match=50%                                      1.01     72.0±0.36µs        ? ?/sec    1.00     71.3±0.34µs        ? ?/sec
   utf8/mixed_len/list=16/match=0%                                      1.01     36.9±0.21µs        ? ?/sec    1.00     36.6±0.59µs        ? ?/sec
   utf8/mixed_len/list=16/match=50%                                     1.02    107.2±0.56µs        ? ?/sec    1.00    105.3±0.78µs        ? ?/sec
   utf8/mixed_len/list=64/match=0%                                      1.00     38.3±0.63µs        ? ?/sec    1.01     38.5±0.17µs        ? ?/sec
   utf8/mixed_len/list=64/match=50%                                     1.02    118.1±0.61µs        ? ?/sec    1.00    115.8±0.75µs        ? ?/sec
   utf8/shared_prefix/pfx=12/list=32/match=50%                          1.00     72.1±0.46µs        ? ?/sec    1.00     71.8±0.50µs        ? ?/sec
   utf8/short_8b/list=16/match=50%/NOT_IN                               1.00     64.3±0.37µs        ? ?/sec    1.00     64.4±0.57µs        ? ?/sec
   utf8/short_8b/list=256/match=0%                                      1.00     26.3±0.02µs        ? ?/sec    1.00     26.4±0.02µs        ? ?/sec
   utf8/short_8b/list=256/match=50%                                     1.00     64.8±0.43µs        ? ?/sec    1.00     64.6±0.82µs        ? ?/sec
   utf8/short_8b/list=4/match=0%                                        1.01     26.6±0.02µs        ? ?/sec    1.00     26.4±0.03µs        ? ?/sec
   utf8/short_8b/list=4/match=50%                                       1.02     66.1±0.34µs        ? ?/sec    1.00     64.9±0.21µs        ? ?/sec
   utf8/short_8b/list=64/match=0%                                       1.00     26.4±0.04µs        ? ?/sec    1.02     26.8±0.36µs        ? ?/sec
   utf8/short_8b/list=64/match=50%                                      1.03     66.3±0.64µs        ? ?/sec    1.00     64.1±0.46µs        ? ?/sec
   utf8view/len_12b/list=16/match=0%                                    1.00     17.8±0.02µs        ? ?/sec    1.00     17.9±0.02µs        ? ?/sec
   utf8view/len_12b/list=16/match=50%                                   1.00     46.0±0.34µs        ? ?/sec    1.01     46.5±0.28µs        ? ?/sec
   utf8view/len_12b/list=64/match=0%                                    1.00     17.9±0.02µs        ? ?/sec    1.00     17.9±0.02µs        ? ?/sec
   utf8view/len_12b/list=64/match=50%                                   1.00     45.2±0.24µs        ? ?/sec    1.01     45.5±0.26µs        ? ?/sec
   utf8view/long_24b/list=16/match=0%                                   1.00     40.2±0.03µs        ? ?/sec    1.01     40.5±0.10µs        ? ?/sec
   utf8view/long_24b/list=16/match=50%                                  1.00     86.4±0.25µs        ? ?/sec    1.01     87.5±0.25µs        ? ?/sec
   utf8view/long_24b/list=256/match=0%                                  1.00     40.1±0.04µs        ? ?/sec    1.00     40.2±0.03µs        ? ?/sec
   utf8view/long_24b/list=256/match=50%                                 1.00     85.4±0.20µs        ? ?/sec    1.00     85.5±0.18µs        ? ?/sec
   utf8view/long_24b/list=4/match=0%                                    1.00     40.4±0.19µs        ? ?/sec    1.00     40.2±0.03µs        ? ?/sec
   utf8view/long_24b/list=4/match=50%                                   1.00     86.0±0.17µs        ? ?/sec    1.01     87.1±0.21µs        ? ?/sec
   utf8view/long_24b/list=64/match=0%                                   1.00     40.3±0.24µs        ? ?/sec    1.01     40.7±0.19µs        ? ?/sec
   utf8view/long_24b/list=64/match=50%                                  1.00     83.7±0.51µs        ? ?/sec    1.01     84.3±0.19µs        ? ?/sec
   utf8view/mixed_len/list=16/match=0%                                  1.00     29.9±0.07µs        ? ?/sec    1.00     29.8±0.06µs        ? ?/sec
   utf8view/mixed_len/list=16/match=50%                                 1.01     74.0±0.42µs        ? ?/sec    1.00     73.3±0.53µs        ? ?/sec
   utf8view/mixed_len/list=64/match=0%                                  1.01     34.0±0.11µs        ? ?/sec    1.00     33.7±0.13µs        ? ?/sec
   utf8view/mixed_len/list=64/match=50%                                 1.01     85.9±0.39µs        ? ?/sec    1.00     85.1±0.48µs        ? ?/sec
   utf8view/shared_prefix/pfx=12/list=32/match=0%                       1.00     42.2±0.09µs        ? ?/sec    1.01     42.6±0.35µs        ? ?/sec
   utf8view/shared_prefix/pfx=12/list=32/match=50%                      1.00     83.8±0.38µs        ? ?/sec    1.00     83.6±0.34µs        ? ?/sec
   utf8view/shared_prefix/pfx=16/list=64/match=0%                       1.00     40.3±0.03µs        ? ?/sec    1.00     40.4±0.03µs        ? ?/sec
   utf8view/shared_prefix/pfx=16/list=64/match=50%                      1.00     84.9±0.33µs        ? ?/sec    1.00     85.2±0.25µs        ? ?/sec
   utf8view/shared_prefix/pfx=8/list=16/match=0%                        1.00     30.0±0.10µs        ? ?/sec    1.00     29.9±0.05µs        ? ?/sec
   utf8view/shared_prefix/pfx=8/list=16/match=50%                       1.01     71.4±0.17µs        ? ?/sec    1.00     70.4±0.14µs        ? ?/sec
   utf8view/short_8b/list=16/match=0%                                   1.00     17.6±0.01µs        ? ?/sec    1.02     17.9±0.08µs        ? ?/sec
   utf8view/short_8b/list=16/match=50%                                  1.00     41.5±0.16µs        ? ?/sec    1.02     42.5±0.25µs        ? ?/sec
   utf8view/short_8b/list=256/match=0%                                  1.00     17.9±0.03µs        ? ?/sec    1.01     18.0±0.11µs        ? ?/sec
   utf8view/short_8b/list=256/match=50%                                 1.00     41.7±0.21µs        ? ?/sec    1.01     42.0±0.31µs        ? ?/sec
   utf8view/short_8b/list=4/match=0%                                    1.00     18.0±0.04µs        ? ?/sec    1.00     17.9±0.04µs        ? ?/sec
   utf8view/short_8b/list=4/match=50%                                   1.00     45.2±0.34µs        ? ?/sec    1.02     46.0±0.16µs        ? ?/sec
   utf8view/short_8b/list=64/match=0%                                   1.00     18.0±0.01µs        ? ?/sec    1.00     18.0±0.19µs        ? ?/sec
   utf8view/short_8b/list=64/match=50%                                  1.00     40.5±0.26µs        ? ?/sec    1.01     40.8±0.16µs        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **in_list_strategy — base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 1310.3s |
   | Peak memory | 41.9 MiB |
   | Avg memory | 28.9 MiB |
   | CPU user | 1410.6s |
   | CPU sys | 1.2s |
   | Peak spill | 0 B |
   
   **in_list_strategy — branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 1305.3s |
   | Peak memory | 44.1 MiB |
   | Avg memory | 31.7 MiB |
   | CPU user | 1419.3s |
   | CPU sys | 1.3s |
   | Peak spill | 0 B |
   
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #23035:
URL: https://github.com/apache/datafusion/pull/23035


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#issuecomment-4811879920

   🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23035#issuecomment-4811575397)
   
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
   
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   <details><summary>Details</summary>
   <p>
   
   ```
   group                                                                HEAD                                   perf_in_list_unify_bitmap_filters
   -----                                                                ----                                   ---------------------------------
   dictionary/i32/dict=10/list=16                                       1.00      7.6±0.02µs        ? ?/sec    1.00      7.6±0.00µs        ? ?/sec
   dictionary/i32/dict=100/list=16                                      1.00      7.7±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=100/list=16/NOT_IN                               1.00      7.7±0.00µs        ? ?/sec    1.00      7.7±0.00µs        ? ?/sec
   dictionary/i32/dict=100/list=4                                       1.00      7.7±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=100/list=64                                      1.00      7.8±0.01µs        ? ?/sec    1.00      7.7±0.01µs        ? ?/sec
   dictionary/i32/dict=1000/list=16                                     1.00      9.0±0.01µs        ? ?/sec    1.00      9.0±0.01µs        ? ?/sec
   dictionary/utf8_long/dict=100/list=16                                1.00      8.3±0.01µs        ? ?/sec    1.00      8.3±0.01µs        ? ?/sec
   dictionary/utf8_short/dict=50/list=32                                1.00      8.1±0.01µs        ? ?/sec    1.00      8.1±0.01µs        ? ?/sec
   dictionary/utf8_short/dict=50/list=8                                 1.00      8.0±0.01µs        ? ?/sec    1.00      8.0±0.01µs        ? ?/sec
   dictionary/utf8_short/dict=500/list=20                               1.00      9.6±0.01µs        ? ?/sec    1.00      9.6±0.01µs        ? ?/sec
   f32/large_list/list=64/match=0%                                      1.01     15.4±0.00µs        ? ?/sec    1.00     15.2±0.06µs        ? ?/sec
   f32/large_list/list=64/match=50%                                     1.02     27.2±0.27µs        ? ?/sec    1.00     26.7±0.26µs        ? ?/sec
   f32/small_list/list=32/match=0%                                      1.03     15.7±0.01µs        ? ?/sec    1.00     15.3±0.01µs        ? ?/sec
   f32/small_list/list=32/match=50%                                     1.11     23.2±0.30µs        ? ?/sec    1.00     20.9±0.18µs        ? ?/sec
   f32/small_list/list=4/match=0%                                       1.03     15.8±0.03µs        ? ?/sec    1.00     15.3±0.01µs        ? ?/sec
   f32/small_list/list=4/match=50%                                      1.00     27.8±0.37µs        ? ?/sec    1.05     29.3±0.33µs        ? ?/sec
   fixed_size_binary/fsb16/list=10000/match=0%                          1.00     25.1±0.02µs        ? ?/sec    1.01     25.2±0.03µs        ? ?/sec
   fixed_size_binary/fsb16/list=10000/match=50%                         1.04     56.2±0.21µs        ? ?/sec    1.00     54.1±0.32µs        ? ?/sec
   fixed_size_binary/fsb16/list=256/match=0%                            1.00     23.9±0.03µs        ? ?/sec    1.00     23.8±0.03µs        ? ?/sec
   fixed_size_binary/fsb16/list=256/match=50%                           1.05     52.0±0.53µs        ? ?/sec    1.00     49.5±0.32µs        ? ?/sec
   fixed_size_binary/fsb16/list=4/match=0%                              1.00     23.0±0.06µs        ? ?/sec    1.02     23.5±0.06µs        ? ?/sec
   fixed_size_binary/fsb16/list=4/match=50%                             1.03     56.3±0.14µs        ? ?/sec    1.00     54.6±0.21µs        ? ?/sec
   fixed_size_binary/fsb16/list=64/match=0%                             1.00     22.9±0.02µs        ? ?/sec    1.01     23.0±0.03µs        ? ?/sec
   fixed_size_binary/fsb16/list=64/match=50%                            1.03     56.5±0.28µs        ? ?/sec    1.00     54.8±0.32µs        ? ?/sec
   narrow_integer/i16/list=256/match=0%                                 1.00     11.9±0.06µs        ? ?/sec    1.09     13.0±0.09µs        ? ?/sec
   narrow_integer/i16/list=256/match=50%                                1.11     22.3±0.34µs        ? ?/sec    1.00     20.1±0.16µs        ? ?/sec
   narrow_integer/i16/list=4/match=0%                                   1.00     12.0±0.01µs        ? ?/sec    1.05     12.6±0.04µs        ? ?/sec
   narrow_integer/i16/list=4/match=50%                                  1.05     23.0±0.24µs        ? ?/sec    1.00     22.0±0.35µs        ? ?/sec
   narrow_integer/i16/list=64/match=0%                                  1.00     11.8±0.00µs        ? ?/sec    1.10     13.0±0.16µs        ? ?/sec
   narrow_integer/i16/list=64/match=50%                                 1.04     19.2±0.24µs        ? ?/sec    1.00     18.6±0.17µs        ? ?/sec
   narrow_integer/u8/list=16/match=0%                                   1.00      5.2±0.01µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   narrow_integer/u8/list=16/match=50%                                  1.00      5.2±0.02µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   narrow_integer/u8/list=4/match=0%                                    1.00      5.2±0.01µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   narrow_integer/u8/list=4/match=50%                                   1.00      5.2±0.00µs        ? ?/sec    1.00      5.2±0.00µs        ? ?/sec
   nulls/narrow_integer/u8/list=16/match=50%/nulls=20%                  1.00      5.3±0.00µs        ? ?/sec    1.00      5.3±0.01µs        ? ?/sec
   nulls/primitive/i32/large_list/list=64/match=50%/nulls=20%           1.11     25.1±0.45µs        ? ?/sec    1.00     22.5±0.20µs        ? ?/sec
   nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%           1.00     24.0±0.29µs        ? ?/sec    1.12     27.0±0.33µs        ? ?/sec
   nulls/primitive/i32/small_list/list=16/match=50%/nulls=20%/NOT_IN    1.22     24.1±0.18µs        ? ?/sec    1.00     19.8±0.21µs        ? ?/sec
   nulls/primitive/i32/small_list/list=16/match=50%/nulls=50%           1.00     16.4±0.15µs        ? ?/sec    1.27     20.9±0.04µs        ? ?/sec
   nulls/utf8/long_24b/list=16/match=50%/nulls=20%                      1.00     70.5±0.36µs        ? ?/sec    1.01     71.0±0.32µs        ? ?/sec
   nulls/utf8/short_8b/list=16/match=50%/nulls=20%                      1.00     60.9±0.40µs        ? ?/sec    1.01     61.7±0.23µs        ? ?/sec
   nulls/utf8view/long_24b/list=16/match=50%/nulls=20%                  1.00     86.9±0.24µs        ? ?/sec    1.00     86.5±0.19µs        ? ?/sec
   nulls/utf8view/short_8b/list=16/match=50%/nulls=20%                  1.00     48.1±0.37µs        ? ?/sec    1.01     48.7±0.22µs        ? ?/sec
   nulls/utf8view/short_8b/list=16/match=50%/nulls=20%/NOT_IN           1.00     48.1±0.16µs        ? ?/sec    1.02     48.9±0.33µs        ? ?/sec
   nulls/utf8view/short_8b/list=16/match=50%/nulls=50%                  1.00     35.3±0.14µs        ? ?/sec    1.03     36.5±0.13µs        ? ?/sec
   primitive/i32/large_list/list=256/match=0%                           1.00     12.2±0.04µs        ? ?/sec    1.02     12.5±0.02µs        ? ?/sec
   primitive/i32/large_list/list=256/match=50%                          1.00     20.3±0.17µs        ? ?/sec    1.30     26.4±0.42µs        ? ?/sec
   primitive/i32/large_list/list=64/match=0%                            1.00     12.1±0.02µs        ? ?/sec    1.05     12.8±0.04µs        ? ?/sec
   primitive/i32/large_list/list=64/match=50%                           1.00     19.4±0.13µs        ? ?/sec    1.26     24.5±0.30µs        ? ?/sec
   primitive/i32/small_list/list=16/match=50%/NOT_IN                    1.11     26.0±0.34µs        ? ?/sec    1.00     23.4±0.30µs        ? ?/sec
   primitive/i32/small_list/list=32/match=0%                            1.00     12.1±0.08µs        ? ?/sec    1.03     12.4±0.01µs        ? ?/sec
   primitive/i32/small_list/list=32/match=50%                           1.00     19.9±0.11µs        ? ?/sec    1.25     25.0±0.25µs        ? ?/sec
   primitive/i32/small_list/list=4/match=0%                             1.00     12.1±0.01µs        ? ?/sec    1.02     12.4±0.02µs        ? ?/sec
   primitive/i32/small_list/list=4/match=50%                            1.00     24.3±0.17µs        ? ?/sec    1.24     30.1±0.40µs        ? ?/sec
   primitive/i64/large_list/list=128/match=0%                           1.00     13.0±0.03µs        ? ?/sec    1.03     13.3±0.02µs        ? ?/sec
   primitive/i64/large_list/list=128/match=50%                          1.00     18.1±0.17µs        ? ?/sec    1.10     19.9±0.21µs        ? ?/sec
   primitive/i64/large_list/list=32/match=0%                            1.04     12.6±0.14µs        ? ?/sec    1.00     12.2±0.02µs        ? ?/sec
   primitive/i64/large_list/list=32/match=50%                           1.00     18.1±0.13µs        ? ?/sec    1.23     22.2±0.60µs        ? ?/sec
   primitive/i64/small_list/list=16/match=0%                            1.14     14.0±0.20µs        ? ?/sec    1.00     12.3±0.02µs        ? ?/sec
   primitive/i64/small_list/list=16/match=50%                           1.29     24.3±0.57µs        ? ?/sec    1.00     18.8±0.13µs        ? ?/sec
   primitive/i64/small_list/list=4/match=0%                             1.06     12.9±0.03µs        ? ?/sec    1.00     12.2±0.01µs        ? ?/sec
   primitive/i64/small_list/list=4/match=50%                            1.00     22.4±0.41µs        ? ?/sec    1.01     22.6±0.33µs        ? ?/sec
   timestamp_ns/large_list/list=32/match=0%                             1.00     17.2±0.04µs        ? ?/sec    1.00     17.2±0.01µs        ? ?/sec
   timestamp_ns/large_list/list=32/match=50%                            1.07     34.4±0.68µs        ? ?/sec    1.00     32.3±1.30µs        ? ?/sec
   timestamp_ns/small_list/list=16/match=0%                             1.00     17.2±0.07µs        ? ?/sec    1.00     17.2±0.04µs        ? ?/sec
   timestamp_ns/small_list/list=16/match=50%                            1.22     36.3±0.29µs        ? ?/sec    1.00     29.7±0.25µs        ? ?/sec
   timestamp_ns/small_list/list=4/match=0%                              1.00     17.0±0.02µs        ? ?/sec    1.01     17.2±0.02µs        ? ?/sec
   timestamp_ns/small_list/list=4/match=50%                             1.02     32.3±0.23µs        ? ?/sec    1.00     31.5±0.31µs        ? ?/sec
   utf8/long_24b/list=256/match=0%                                      1.00     33.5±0.03µs        ? ?/sec    1.01     33.8±0.03µs        ? ?/sec
   utf8/long_24b/list=256/match=50%                                     1.00     72.3±0.45µs        ? ?/sec    1.00     72.0±0.70µs        ? ?/sec
   utf8/long_24b/list=4/match=0%                                        1.00     33.7±0.02µs        ? ?/sec    1.01     34.0±0.02µs        ? ?/sec
   utf8/long_24b/list=4/match=50%                                       1.00     72.6±0.57µs        ? ?/sec    1.00     72.7±0.27µs        ? ?/sec
   utf8/long_24b/list=64/match=0%                                       1.00     33.4±0.03µs        ? ?/sec    1.00     33.5±0.02µs        ? ?/sec
   utf8/long_24b/list=64/match=50%                                      1.00     72.3±0.22µs        ? ?/sec    1.00     72.3±0.34µs        ? ?/sec
   utf8/mixed_len/list=16/match=0%                                      1.00     36.8±0.20µs        ? ?/sec    1.01     37.0±0.10µs        ? ?/sec
   utf8/mixed_len/list=16/match=50%                                     1.02    107.2±0.84µs        ? ?/sec    1.00    104.9±0.62µs        ? ?/sec
   utf8/mixed_len/list=64/match=0%                                      1.00     38.0±0.39µs        ? ?/sec    1.00     38.0±0.21µs        ? ?/sec
   utf8/mixed_len/list=64/match=50%                                     1.01    117.7±0.48µs        ? ?/sec    1.00    116.1±0.49µs        ? ?/sec
   utf8/shared_prefix/pfx=12/list=32/match=50%                          1.00     72.4±0.64µs        ? ?/sec    1.00     72.3±0.56µs        ? ?/sec
   utf8/short_8b/list=16/match=50%/NOT_IN                               1.00     65.2±0.76µs        ? ?/sec    1.01     65.7±0.38µs        ? ?/sec
   utf8/short_8b/list=256/match=0%                                      1.00     26.2±0.02µs        ? ?/sec    1.03     27.1±0.32µs        ? ?/sec
   utf8/short_8b/list=256/match=50%                                     1.02     65.3±0.49µs        ? ?/sec    1.00     64.3±0.40µs        ? ?/sec
   utf8/short_8b/list=4/match=0%                                        1.00     26.3±0.04µs        ? ?/sec    1.01     26.7±0.07µs        ? ?/sec
   utf8/short_8b/list=4/match=50%                                       1.02     66.6±0.92µs        ? ?/sec    1.00     65.3±0.26µs        ? ?/sec
   utf8/short_8b/list=64/match=0%                                       1.00     26.3±0.04µs        ? ?/sec    1.01     26.6±0.02µs        ? ?/sec
   utf8/short_8b/list=64/match=50%                                      1.03     65.7±0.43µs        ? ?/sec    1.00     63.7±0.34µs        ? ?/sec
   utf8view/len_12b/list=16/match=0%                                    1.00     18.0±0.04µs        ? ?/sec    1.03     18.5±0.03µs        ? ?/sec
   utf8view/len_12b/list=16/match=50%                                   1.00     46.2±0.22µs        ? ?/sec    1.00     46.1±0.26µs        ? ?/sec
   utf8view/len_12b/list=64/match=0%                                    1.00     18.0±0.02µs        ? ?/sec    1.02     18.3±0.04µs        ? ?/sec
   utf8view/len_12b/list=64/match=50%                                   1.03     45.7±0.13µs        ? ?/sec    1.00     44.4±0.35µs        ? ?/sec
   utf8view/long_24b/list=16/match=0%                                   1.00     40.3±0.07µs        ? ?/sec    1.00     40.2±0.04µs        ? ?/sec
   utf8view/long_24b/list=16/match=50%                                  1.00     86.5±0.19µs        ? ?/sec    1.00     86.6±0.19µs        ? ?/sec
   utf8view/long_24b/list=256/match=0%                                  1.00     40.2±0.03µs        ? ?/sec    1.01     40.4±0.14µs        ? ?/sec
   utf8view/long_24b/list=256/match=50%                                 1.00     85.5±0.11µs        ? ?/sec    1.00     85.6±0.15µs        ? ?/sec
   utf8view/long_24b/list=4/match=0%                                    1.02     41.0±0.09µs        ? ?/sec    1.00     40.2±0.04µs        ? ?/sec
   utf8view/long_24b/list=4/match=50%                                   1.00     86.2±0.22µs        ? ?/sec    1.00     86.6±0.21µs        ? ?/sec
   utf8view/long_24b/list=64/match=0%                                   1.01     40.5±0.06µs        ? ?/sec    1.00     40.2±0.05µs        ? ?/sec
   utf8view/long_24b/list=64/match=50%                                  1.00     83.6±0.17µs        ? ?/sec    1.01     84.1±0.18µs        ? ?/sec
   utf8view/mixed_len/list=16/match=0%                                  1.00     30.0±0.05µs        ? ?/sec    1.00     30.0±0.09µs        ? ?/sec
   utf8view/mixed_len/list=16/match=50%                                 1.02     74.2±0.37µs        ? ?/sec    1.00     72.7±0.68µs        ? ?/sec
   utf8view/mixed_len/list=64/match=0%                                  1.01     33.9±0.12µs        ? ?/sec    1.00     33.6±0.12µs        ? ?/sec
   utf8view/mixed_len/list=64/match=50%                                 1.00     85.4±0.48µs        ? ?/sec    1.00     85.5±0.43µs        ? ?/sec
   utf8view/shared_prefix/pfx=12/list=32/match=0%                       1.00     42.2±0.04µs        ? ?/sec    1.01     42.6±0.07µs        ? ?/sec
   utf8view/shared_prefix/pfx=12/list=32/match=50%                      1.00     82.8±0.25µs        ? ?/sec    1.01     83.6±0.42µs        ? ?/sec
   utf8view/shared_prefix/pfx=16/list=64/match=0%                       1.01     40.6±0.31µs        ? ?/sec    1.00     40.4±0.04µs        ? ?/sec
   utf8view/shared_prefix/pfx=16/list=64/match=50%                      1.00     84.4±0.27µs        ? ?/sec    1.00     84.6±0.14µs        ? ?/sec
   utf8view/shared_prefix/pfx=8/list=16/match=0%                        1.00     29.8±0.06µs        ? ?/sec    1.01     30.0±0.04µs        ? ?/sec
   utf8view/shared_prefix/pfx=8/list=16/match=50%                       1.01     72.0±0.34µs        ? ?/sec    1.00     71.4±0.29µs        ? ?/sec
   utf8view/short_8b/list=16/match=0%                                   1.00     17.7±0.04µs        ? ?/sec    1.00     17.7±0.03µs        ? ?/sec
   utf8view/short_8b/list=16/match=50%                                  1.00     41.9±0.16µs        ? ?/sec    1.00     41.8±0.16µs        ? ?/sec
   utf8view/short_8b/list=256/match=0%                                  1.00     17.9±0.06µs        ? ?/sec    1.05     18.8±0.38µs        ? ?/sec
   utf8view/short_8b/list=256/match=50%                                 1.00     41.9±0.32µs        ? ?/sec    1.00     42.0±0.14µs        ? ?/sec
   utf8view/short_8b/list=4/match=0%                                    1.01     18.2±0.26µs        ? ?/sec    1.00     18.1±0.02µs        ? ?/sec
   utf8view/short_8b/list=4/match=50%                                   1.00     45.0±0.24µs        ? ?/sec    1.00     45.0±0.54µs        ? ?/sec
   utf8view/short_8b/list=64/match=0%                                   1.00     18.0±0.04µs        ? ?/sec    1.04     18.8±0.22µs        ? ?/sec
   utf8view/short_8b/list=64/match=50%                                  1.00     40.5±0.21µs        ? ?/sec    1.00     40.6±0.12µs        ? ?/sec
   ```
   
   </p>
   </details>
   
   <details><summary>Resource Usage</summary>
   
   **in_list_strategy — base (merge-base)**
   | Metric | Value |
   |--------|-------|
   | Wall time | 1225.3s |
   | Peak memory | 44.6 MiB |
   | Avg memory | 34.1 MiB |
   | CPU user | 1411.0s |
   | CPU sys | 1.1s |
   | Peak spill | 0 B |
   
   **in_list_strategy — branch**
   | Metric | Value |
   |--------|-------|
   | Wall time | 1255.3s |
   | Peak memory | 40.9 MiB |
   | Avg memory | 29.9 MiB |
   | CPU user | 1414.7s |
   | CPU sys | 1.2s |
   | Peak spill | 0 B |
   
   </details>
   
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#issuecomment-4811591483

   🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23035#issuecomment-4811575397)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4811575397-715-cr7tx 6.12.85+ #1 SMP Mon May 11 08:17:35 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf/in_list_unify_bitmap_filters (a38a6ccaa2b2fee12ab3402392659eb83f43eebb) to bde8e5b (merge-base) [diff](https://github.com/apache/datafusion/compare/bde8e5b24e772210885ea5272e5cb06b52c939c3..a38a6ccaa2b2fee12ab3402392659eb83f43eebb) using: in_list_strategy
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#issuecomment-4810275846

   🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23035#issuecomment-4810253683)
   **Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4810253683-709-sx7tr 6.12.85+ #1 SMP Mon May 11 08:17:35 UTC 2026 aarch64 GNU/Linux`
   <details><summary>CPU Details (lscpu)</summary>
   
   ```
   Architecture:                            aarch64
   CPU op-mode(s):                          64-bit
   Byte Order:                              Little Endian
   CPU(s):                                  16
   On-line CPU(s) list:                     0-15
   Vendor ID:                               ARM
   Model name:                              Neoverse-V2
   Model:                                   1
   Thread(s) per core:                      1
   Core(s) per cluster:                     16
   Socket(s):                               -
   Cluster(s):                              1
   Stepping:                                r0p1
   BogoMIPS:                                2000.00
   Flags:                                   fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
   L1d cache:                               1 MiB (16 instances)
   L1i cache:                               1 MiB (16 instances)
   L2 cache:                                32 MiB (16 instances)
   L3 cache:                                80 MiB (1 instance)
   NUMA node(s):                            1
   NUMA node0 CPU(s):                       0-15
   Vulnerability Gather data sampling:      Not affected
   Vulnerability Indirect target selection: Not affected
   Vulnerability Itlb multihit:             Not affected
   Vulnerability L1tf:                      Not affected
   Vulnerability Mds:                       Not affected
   Vulnerability Meltdown:                  Not affected
   Vulnerability Mmio stale data:           Not affected
   Vulnerability Reg file data sampling:    Not affected
   Vulnerability Retbleed:                  Not affected
   Vulnerability Spec rstack overflow:      Not affected
   Vulnerability Spec store bypass:         Mitigation; Speculative Store Bypass disabled via prctl
   Vulnerability Spectre v1:                Mitigation; __user pointer sanitization
   Vulnerability Spectre v2:                Mitigation; CSV2, BHB
   Vulnerability Srbds:                     Not affected
   Vulnerability Tsa:                       Not affected
   Vulnerability Tsx async abort:           Not affected
   Vulnerability Vmscape:                   Not affected
   ```
   
   </details>
   
   Comparing perf/in_list_unify_bitmap_filters (3085965fc2cd4c53475bae4738dfc25713b2a2c2) to bde8e5b (merge-base) [diff](https://github.com/apache/datafusion/compare/bde8e5b24e772210885ea5272e5cb06b52c939c3..3085965fc2cd4c53475bae4738dfc25713b2a2c2) using: in_list_strategy
   Results will be posted here when complete
   
   ---
   [File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner


-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#discussion_r3483020046


##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
+    }
+}
 
+impl BitmapStorage for Box<[u64; 1024]> {
+    #[inline]
+    fn new_zeroed() -> Self {
+        Box::new([0u64; 1024])
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
+    }
     #[inline(always)]
-    fn check(&self, needle: u8) -> bool {
-        let index = needle as usize;
-        (self.bits[index / 64] >> (index % 64)) & 1 != 0
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-impl StaticFilter for UInt8BitmapFilter {
-    fn null_count(&self) -> usize {
-        self.null_count
+pub(super) trait BitmapFilterConfig: Send + Sync + 'static {

Review Comment:
   Still not perfect, but much better I'd say! The LOC diff of the PR dropped, which is usually a good sign...



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#discussion_r3481847817


##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
+    }
+}
 
+impl BitmapStorage for Box<[u64; 1024]> {
+    #[inline]
+    fn new_zeroed() -> Self {
+        Box::new([0u64; 1024])
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
+    }
     #[inline(always)]
-    fn check(&self, needle: u8) -> bool {
-        let index = needle as usize;
-        (self.bits[index / 64] >> (index % 64)) & 1 != 0
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-impl StaticFilter for UInt8BitmapFilter {
-    fn null_count(&self) -> usize {
-        self.null_count
+pub(super) trait BitmapFilterConfig: Send + Sync + 'static {

Review Comment:
   a few comments explaining what this trait is and why it is needed, I think would help future readers (it looks like a package of other types to make the generics on bitmap implementations simpler)



##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {

Review Comment:
   Recommend a few comments explainng this trait, to help future readers
   



##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {

Review Comment:
   > / `UInt8` has only 256 possible values, so the filter stores membership in a
   /// 256-bit bitmap instead of using a hash table.
   
   This was nice rationale information that I think would be nice to add to comments



##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
+    }
+}
 
+impl BitmapStorage for Box<[u64; 1024]> {

Review Comment:
   ditto here for comments about using a 8k bitmap rather than hahstable



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] IN LIST: unify bitmap filter implementations [datafusion]

Posted by "geoffreyclaude (via GitHub)" <gi...@apache.org>.
geoffreyclaude commented on code in PR #23035:
URL: https://github.com/apache/datafusion/pull/23035#discussion_r3482614141


##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
+    }
+}
 
+impl BitmapStorage for Box<[u64; 1024]> {
+    #[inline]
+    fn new_zeroed() -> Self {
+        Box::new([0u64; 1024])
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
+    }
     #[inline(always)]
-    fn check(&self, needle: u8) -> bool {
-        let index = needle as usize;
-        (self.bits[index / 64] >> (index % 64)) & 1 != 0
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-impl StaticFilter for UInt8BitmapFilter {
-    fn null_count(&self) -> usize {
-        self.null_count
+pub(super) trait BitmapFilterConfig: Send + Sync + 'static {

Review Comment:
   Added a few comments, which led me to realize the solution was way over-engineered. I've refactoring the traits a bit into a simpler form.



##########
datafusion/physical-expr/src/expressions/in_list/primitive_filter.rs:
##########
@@ -29,113 +29,108 @@ use std::hash::{Hash, Hasher};
 use super::result::build_in_list_result;
 use super::static_filter::{StaticFilter, handle_dictionary};
 
-/// Bitmap filter for O(1) set membership via single bit test.
-///
-/// `UInt8` has only 256 possible values, so the filter stores membership in a
-/// 256-bit bitmap instead of using a hash table.
-pub(super) struct UInt8BitmapFilter {
-    null_count: usize,
-    bits: [u64; 4],
+pub(super) trait BitmapStorage: Send + Sync {
+    fn new_zeroed() -> Self;
+    fn set_bit(&mut self, index: usize);
+    fn get_bit(&self, index: usize) -> bool;
 }
 
-impl UInt8BitmapFilter {
-    pub(super) fn try_new(in_array: &ArrayRef) -> Result<Self> {
-        let prim_array = in_array.as_primitive_opt::<UInt8Type>().ok_or_else(|| {
-            exec_datafusion_err!("UInt8BitmapFilter: expected UInt8 array")
-        })?;
-        let mut bits = [0u64; 4];
-        let mut set_bit = |v: u8| {
-            let index = usize::from(v);
-            bits[index / 64] |= 1u64 << (index % 64);
-        };
-
-        let values = prim_array.values();
-        match prim_array.nulls() {
-            None => {
-                for &v in values {
-                    set_bit(v);
-                }
-            }
-            Some(nulls) => {
-                for i in
-                    BitIndexIterator::new(nulls.validity(), nulls.offset(), nulls.len())
-                {
-                    set_bit(values[i]);
-                }
-            }
-        }
-        Ok(Self {
-            null_count: prim_array.null_count(),
-            bits,
-        })
+impl BitmapStorage for [u64; 4] {
+    #[inline]
+    fn new_zeroed() -> Self {
+        [0u64; 4]
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
     }
+    #[inline(always)]
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
+    }
+}
 
+impl BitmapStorage for Box<[u64; 1024]> {
+    #[inline]
+    fn new_zeroed() -> Self {
+        Box::new([0u64; 1024])
+    }
+    #[inline]
+    fn set_bit(&mut self, index: usize) {
+        self[index / 64] |= 1u64 << (index % 64);
+    }
     #[inline(always)]
-    fn check(&self, needle: u8) -> bool {
-        let index = needle as usize;
-        (self.bits[index / 64] >> (index % 64)) & 1 != 0
+    fn get_bit(&self, index: usize) -> bool {
+        (self[index / 64] >> (index % 64)) & 1 != 0
     }
 }
 
-impl StaticFilter for UInt8BitmapFilter {
-    fn null_count(&self) -> usize {
-        self.null_count
+pub(super) trait BitmapFilterConfig: Send + Sync + 'static {

Review Comment:
   Added a few comments, which led me to realize the solution was way over-engineered. I'm refactoring the traits a bit into a simpler form.



-- 
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: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org