This is an automated email from the ASF dual-hosted git repository.
dheres pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new d42610711d Add has_true() and has_false() to BooleanArray (#9511)
d42610711d is described below
commit d42610711d12a03b810bf0297d38a36029093304
Author: Adrian Garcia Badaracco <[email protected]>
AuthorDate: Wed Mar 18 00:31:25 2026 -0500
Add has_true() and has_false() to BooleanArray (#9511)
## Motivation
When working with `BooleanArray`, a common pattern is checking whether
*any* true or false value exists — e.g.
`arr.true_count() > 0` or `arr.false_count() == 0`. This currently
requires `true_count()` / `false_count()`, which scan the **entire**
bitmap to count every set bit (via `popcount`), even though we only need
to know if at least one exists.
This PR adds `has_true()` and `has_false()` methods that short-circuit
as soon as they find a matching value, providing both:
1. **Better performance** — faster on large arrays in the best case
2. **More ergonomic API** — `arr.has_true()` expresses intent more
clearly than `arr.true_count() > 0`
## Callsites in DataFusion
There are several places in DataFusion that would benefit from these
methods:
- **`datafusion/functions-nested/src/array_has.rs`** —
`eq_array.true_count() > 0` → `eq_array.has_true()`
- **`datafusion/physical-plan/src/topk/mod.rs`** — `filter.true_count()
== 0` check → `!filter.has_true()`
- **`datafusion/datasource-parquet/src/metadata.rs`** —
`exactness.true_count() == 0` and `combined_mask.true_count() > 0`
- **`datafusion/physical-plan/src/joins/nested_loop_join.rs`** —
`bitmap.true_count() == 0` checks
- **`datafusion/physical-expr-common/src/physical_expr.rs`** —
`selection_count == 0` from `selection.true_count()`
- **`datafusion/physical-expr/src/expressions/binary.rs`** —
short-circuit checks for AND/OR
## Benchmark Results
```
Scenario true_count has_true has_false
Speedup (best)
─────────────────────────────────────────────────────────────────────────────────────────────
all_true, 64 4.32 ns 4.08 ns 4.76 ns
~1.1x
all_false, 64 4.30 ns 4.25 ns 4.52 ns
~1.0x
all_true, 1024 5.15 ns 4.52 ns 4.99 ns
~1.1x
all_false, 1024 5.17 ns 4.55 ns 5.00 ns
~1.1x
mixed_early, 1024 5.22 ns — 5.04 ns
~1.0x
nulls_all_true, 1024 12.84 ns 4.10 ns 12.92 ns
~3.1x
all_true, 65536 100.06 ns 5.96 ns 49.70 ns
~16.8x (has_true)
all_false, 65536 99.33 ns 49.30 ns 6.19 ns
~16.0x (has_false)
mixed_early, 65536 100.10 ns — 6.20 ns
~16.1x (has_false)
nulls_all_true, 65536 522.94 ns 4.05 ns 521.82 ns
~129x (has_true)
```
The key wins are on larger arrays (65,536 elements), where
`has_true`/`has_false` are **up to 16-129x faster** than
`true_count()` in best-case scenarios (early short-circuit). Even in
worst case (must scan entire array), performance is
comparable to `true_count`.
## Implementation
The implementation processes bits in 64-bit chunks using
`UnalignedBitChunk`, which handles arbitrary bit offsets and aligns
data for SIMD-friendly processing.
- **`has_true` (no nulls):** OR-folds 64-bit chunks, short-circuits when
any bit is set
- **`has_false` (no nulls):** AND-folds 64-bit chunks, short-circuits
when any bit is unset (with padding bits masked to 1)
- **With nulls:** Iterates paired `(null, value)` chunks, checking `null
& value != 0` (has_true) or `null & !value != 0`
(has_false)
### Alternatives considered
1. **Fully vectorized (no early stopping):** Would process the entire
bitmap like `true_count()` but with simpler bitwise ops
instead of popcount. Marginally faster than `true_count()` but misses
the main optimization opportunity.
2. **Per-element iteration with early stopping:** `self.iter().any(|v| v
== Some(true))`. Simple but processes one bit at a
time, missing SIMD vectorization of the inner loop. Our approach
processes 64 bits at a time while still supporting early
exit.
The chosen approach balances SIMD-friendly bulk processing (64 bits per
iteration) with early termination, giving the best of
both worlds.
## Test Plan
- Unit tests covering: all-true, all-false, mixed, empty, nullable
(all-valid-true, all-valid-false, all-null), non-aligned
lengths (65 elements, 64+1 with trailing false)
- Criterion benchmarks comparing `has_true`/`has_false` vs `true_count`
across sizes (64, 1024, 65536) and data distributions
🤖 Generated with [Claude Code](https://claude.com/claude-code
---------
Co-authored-by: Claude Opus 4.6 <[email protected]>
---
arrow-array/Cargo.toml | 4 +
arrow-array/benches/boolean_array.rs | 77 ++++++++++++
arrow-array/src/array/boolean_array.rs | 209 ++++++++++++++++++++++++++++++++-
3 files changed, 288 insertions(+), 2 deletions(-)
diff --git a/arrow-array/Cargo.toml b/arrow-array/Cargo.toml
index 6be5a6daab..da8ef98a10 100644
--- a/arrow-array/Cargo.toml
+++ b/arrow-array/Cargo.toml
@@ -92,3 +92,7 @@ harness = false
[[bench]]
name = "record_batch"
harness = false
+
+[[bench]]
+name = "boolean_array"
+harness = false
diff --git a/arrow-array/benches/boolean_array.rs
b/arrow-array/benches/boolean_array.rs
new file mode 100644
index 0000000000..03b601075b
--- /dev/null
+++ b/arrow-array/benches/boolean_array.rs
@@ -0,0 +1,77 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow_array::BooleanArray;
+use criterion::*;
+use std::hint;
+
+fn criterion_benchmark(c: &mut Criterion) {
+ for len in [64, 1024, 65536] {
+ // All true (no nulls)
+ let all_true = BooleanArray::from(vec![true; len]);
+ c.bench_function(&format!("true_count(all_true, {len})"), |b| {
+ b.iter(|| hint::black_box(&all_true).true_count());
+ });
+ c.bench_function(&format!("has_true(all_true, {len})"), |b| {
+ b.iter(|| hint::black_box(&all_true).has_true());
+ });
+ c.bench_function(&format!("has_false(all_true, {len})"), |b| {
+ b.iter(|| hint::black_box(&all_true).has_false());
+ });
+
+ // All false (no nulls)
+ let all_false = BooleanArray::from(vec![false; len]);
+ c.bench_function(&format!("true_count(all_false, {len})"), |b| {
+ b.iter(|| hint::black_box(&all_false).true_count());
+ });
+ c.bench_function(&format!("has_true(all_false, {len})"), |b| {
+ b.iter(|| hint::black_box(&all_false).has_true());
+ });
+ c.bench_function(&format!("has_false(all_false, {len})"), |b| {
+ b.iter(|| hint::black_box(&all_false).has_false());
+ });
+
+ // Mixed: first element differs (best-case short-circuit)
+ let mut mixed_early: Vec<bool> = vec![true; len];
+ mixed_early[0] = false;
+ let mixed_early = BooleanArray::from(mixed_early);
+ c.bench_function(&format!("true_count(mixed_early, {len})"), |b| {
+ b.iter(|| hint::black_box(&mixed_early).true_count());
+ });
+ c.bench_function(&format!("has_false(mixed_early, {len})"), |b| {
+ b.iter(|| hint::black_box(&mixed_early).has_false());
+ });
+
+ // With nulls: all valid values true
+ let with_nulls: Vec<Option<bool>> = (0..len)
+ .map(|i| if i % 10 == 0 { None } else { Some(true) })
+ .collect();
+ let with_nulls = BooleanArray::from(with_nulls);
+ c.bench_function(&format!("true_count(nulls_all_true, {len})"), |b| {
+ b.iter(|| hint::black_box(&with_nulls).true_count());
+ });
+ c.bench_function(&format!("has_true(nulls_all_true, {len})"), |b| {
+ b.iter(|| hint::black_box(&with_nulls).has_true());
+ });
+ c.bench_function(&format!("has_false(nulls_all_true, {len})"), |b| {
+ b.iter(|| hint::black_box(&with_nulls).has_false());
+ });
+ }
+}
+
+criterion_group!(benches, criterion_benchmark);
+criterion_main!(benches);
diff --git a/arrow-array/src/array/boolean_array.rs
b/arrow-array/src/array/boolean_array.rs
index 582627b243..1a2dd986ad 100644
--- a/arrow-array/src/array/boolean_array.rs
+++ b/arrow-array/src/array/boolean_array.rs
@@ -19,6 +19,7 @@ use crate::array::print_long_array;
use crate::builder::BooleanBuilder;
use crate::iterator::BooleanIter;
use crate::{Array, ArrayAccessor, ArrayRef, Scalar};
+use arrow_buffer::bit_chunk_iterator::UnalignedBitChunk;
use arrow_buffer::{BooleanBuffer, Buffer, MutableBuffer, NullBuffer, bit_util};
use arrow_data::{ArrayData, ArrayDataBuilder};
use arrow_schema::DataType;
@@ -156,7 +157,18 @@ impl BooleanArray {
&self.values
}
- /// Returns the number of non null, true values within this array
+ /// Block size for chunked fold operations in [`Self::has_true`] and
[`Self::has_false`].
+ /// Folding this many u64 chunks at a time allows the compiler to
autovectorize
+ /// the inner loop while still enabling short-circuit exits.
+ const CHUNK_FOLD_BLOCK_SIZE: usize = 64;
+
+ /// Returns an [`UnalignedBitChunk`] over this array's values.
+ fn unaligned_bit_chunks(&self) -> UnalignedBitChunk<'_> {
+ UnalignedBitChunk::new(self.values().values(), self.values().offset(),
self.len())
+ }
+
+ /// Returns the number of non null, true values within this array.
+ /// If you only need to check if there is at least one true value,
consider using `has_true()` which can short-circuit and be more efficient.
pub fn true_count(&self) -> usize {
match self.nulls() {
Some(nulls) => {
@@ -171,11 +183,80 @@ impl BooleanArray {
}
}
- /// Returns the number of non null, false values within this array
+ /// Returns the number of non null, false values within this array.
+ /// If you only need to check if there is at least one false value,
consider using `has_false()` which can short-circuit and be more efficient.
pub fn false_count(&self) -> usize {
self.len() - self.null_count() - self.true_count()
}
+ /// Returns whether there is at least one non-null `true` value in this
array.
+ ///
+ /// This is more efficient than `true_count() > 0` because it can
short-circuit
+ /// as soon as a `true` value is found, without counting all set bits.
+ ///
+ /// Null values are not counted as `true`. Returns `false` for empty
arrays.
+ pub fn has_true(&self) -> bool {
+ match self.nulls() {
+ Some(nulls) => {
+ let null_chunks = nulls.inner().bit_chunks().iter_padded();
+ let value_chunks = self.values().bit_chunks().iter_padded();
+ null_chunks.zip(value_chunks).any(|(n, v)| (n & v) != 0)
+ }
+ None => {
+ let bit_chunks = self.unaligned_bit_chunks();
+ bit_chunks.prefix().unwrap_or(0) != 0
+ || bit_chunks
+ .chunks()
+ .chunks(Self::CHUNK_FOLD_BLOCK_SIZE)
+ .any(|block| block.iter().fold(0u64, |acc, &c| acc |
c) != 0)
+ || bit_chunks.suffix().unwrap_or(0) != 0
+ }
+ }
+ }
+
+ /// Returns whether there is at least one non-null `false` value in this
array.
+ ///
+ /// This is more efficient than `false_count() > 0` because it can
short-circuit
+ /// as soon as a `false` value is found, without counting all set bits.
+ ///
+ /// Null values are not counted as `false`. Returns `false` for empty
arrays.
+ pub fn has_false(&self) -> bool {
+ match self.nulls() {
+ Some(nulls) => {
+ let null_chunks = nulls.inner().bit_chunks().iter_padded();
+ let value_chunks = self.values().bit_chunks().iter_padded();
+ null_chunks.zip(value_chunks).any(|(n, v)| (n & !v) != 0)
+ }
+ None => {
+ let bit_chunks = self.unaligned_bit_chunks();
+ // UnalignedBitChunk zeros padding bits; fill them with 1s so
+ // they don't appear as false values.
+ let lead_mask = !((1u64 << bit_chunks.lead_padding()) - 1);
+ let trail_mask = if bit_chunks.trailing_padding() == 0 {
+ u64::MAX
+ } else {
+ (1u64 << (64 - bit_chunks.trailing_padding())) - 1
+ };
+ let (prefix_fill, suffix_fill) = match (bit_chunks.prefix(),
bit_chunks.suffix()) {
+ (Some(_), Some(_)) => (!lead_mask, !trail_mask),
+ (Some(_), None) => (!lead_mask | !trail_mask, 0),
+ (None, Some(_)) => (0, !trail_mask),
+ (None, None) => (0, 0),
+ };
+ bit_chunks
+ .prefix()
+ .is_some_and(|v| (v | prefix_fill) != u64::MAX)
+ || bit_chunks
+ .chunks()
+ .chunks(Self::CHUNK_FOLD_BLOCK_SIZE)
+ .any(|block| block.iter().fold(u64::MAX, |acc, &c| acc
& c) != u64::MAX)
+ || bit_chunks
+ .suffix()
+ .is_some_and(|v| (v | suffix_fill) != u64::MAX)
+ }
+ }
+ }
+
/// Returns the boolean value at index `i`.
///
/// Note: This method does not check for nulls and the value is arbitrary
@@ -854,4 +935,128 @@ mod tests {
assert!(sliced.is_valid(1));
assert!(!sliced.value(1));
}
+
+ #[test]
+ fn test_has_true_has_false_all_true() {
+ let arr = BooleanArray::from(vec![true, true, true]);
+ assert!(arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_all_false() {
+ let arr = BooleanArray::from(vec![false, false, false]);
+ assert!(!arr.has_true());
+ assert!(arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_mixed() {
+ let arr = BooleanArray::from(vec![true, false, true]);
+ assert!(arr.has_true());
+ assert!(arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_empty() {
+ let arr = BooleanArray::from(Vec::<bool>::new());
+ assert!(!arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_nulls_all_valid_true() {
+ let arr = BooleanArray::from(vec![Some(true), None, Some(true)]);
+ assert!(arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_nulls_all_valid_false() {
+ let arr = BooleanArray::from(vec![Some(false), None, Some(false)]);
+ assert!(!arr.has_true());
+ assert!(arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_all_null() {
+ let arr = BooleanArray::new_null(5);
+ assert!(!arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_false_aligned_suffix_all_true() {
+ let arr = BooleanArray::from(vec![true; 129]);
+ assert!(arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_false_non_aligned_all_true() {
+ // 65 elements: exercises the remainder path in has_false
+ let arr = BooleanArray::from(vec![true; 65]);
+ assert!(arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_false_non_aligned_last_false() {
+ // 64 trues + 1 false: remainder path should find the false
+ let mut values = vec![true; 64];
+ values.push(false);
+ let arr = BooleanArray::from(values);
+ assert!(arr.has_true());
+ assert!(arr.has_false());
+ }
+
+ #[test]
+ fn test_has_false_exact_64_all_true() {
+ // Exactly 64 elements, no remainder
+ let arr = BooleanArray::from(vec![true; 64]);
+ assert!(arr.has_true());
+ assert!(!arr.has_false());
+ }
+
+ #[test]
+ fn test_has_true_has_false_unaligned_slices() {
+ let cases = [
+ (1, 129, true, false),
+ (3, 130, true, false),
+ (5, 65, true, false),
+ (7, 64, true, false),
+ ];
+
+ let base = BooleanArray::from(vec![true; 300]);
+
+ for (offset, len, expected_has_true, expected_has_false) in cases {
+ let arr = base.slice(offset, len);
+ assert_eq!(
+ arr.has_true(),
+ expected_has_true,
+ "offset={offset} len={len}"
+ );
+ assert_eq!(
+ arr.has_false(),
+ expected_has_false,
+ "offset={offset} len={len}"
+ );
+ }
+ }
+
+ #[test]
+ fn test_has_true_has_false_exact_multiples_of_64() {
+ let cases = [
+ (64, true, false),
+ (128, true, false),
+ (192, true, false),
+ (256, true, false),
+ ];
+
+ for (len, expected_has_true, expected_has_false) in cases {
+ let arr = BooleanArray::from(vec![true; len]);
+ assert_eq!(arr.has_true(), expected_has_true, "len={len}");
+ assert_eq!(arr.has_false(), expected_has_false, "len={len}");
+ }
+ }
}
