Skip to main content

arrow_select/coalesce/
boolean.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use super::InProgressArray;
6use crate::filter::{FilterPredicate, Packer};
7use arrow_array::cast::AsArray;
8use arrow_array::{Array, ArrayRef, BooleanArray};
9use arrow_buffer::bit_chunk_iterator::BitChunks;
10use arrow_buffer::{BooleanBuffer, BooleanBufferBuilder, NullBufferBuilder};
11use arrow_schema::ArrowError;
12use std::sync::Arc;
13
14fn copy_filter_words_without_nulls(
15    output_values: &mut BooleanBufferBuilder,
16    source_value_chunks: &BitChunks<'_>,
17    filter_chunks: &BitChunks<'_>,
18) {
19    let mut value_packer = Packer::default();
20
21    // Check the mask first so sparse filters skip reading most source words.
22    for (index, filter_mask) in filter_chunks.iter().enumerate() {
23        if filter_mask == 0 {
24            continue;
25        }
26
27        if let Some(complete_word) =
28            value_packer.push(source_value_chunks.chunk(index), filter_mask)
29        {
30            output_values.append_word(complete_word, 64);
31        }
32    }
33
34    let filter_mask = filter_chunks.remainder_bits();
35    if filter_mask != 0
36        && let Some(complete_word) =
37            value_packer.push(source_value_chunks.remainder_bits(), filter_mask)
38    {
39        output_values.append_word(complete_word, 64);
40    }
41
42    if let Some((pending_bits, pending_len)) = value_packer.finish() {
43        output_values.append_word(pending_bits, pending_len);
44    }
45}
46
47fn copy_filter_words_with_nulls(
48    output_values: &mut BooleanBufferBuilder,
49    output_validity: &mut NullBufferBuilder,
50    source_value_chunks: &BitChunks<'_>,
51    source_validity_chunks: &BitChunks<'_>,
52    filter_chunks: &BitChunks<'_>,
53) {
54    let mut value_packer = Packer::default();
55    let mut validity_packer = Packer::default();
56
57    // Check the mask first so sparse filters skip reading most source words.
58    for (index, filter_mask) in filter_chunks.iter().enumerate() {
59        if filter_mask == 0 {
60            continue;
61        }
62
63        if let Some(complete_word) =
64            value_packer.push(source_value_chunks.chunk(index), filter_mask)
65        {
66            output_values.append_word(complete_word, 64);
67        }
68        if let Some(complete_word) =
69            validity_packer.push(source_validity_chunks.chunk(index), filter_mask)
70        {
71            output_validity.append_word(complete_word, 64);
72        }
73    }
74
75    let filter_mask = filter_chunks.remainder_bits();
76    if filter_mask != 0 {
77        if let Some(complete_word) =
78            value_packer.push(source_value_chunks.remainder_bits(), filter_mask)
79        {
80            output_values.append_word(complete_word, 64);
81        }
82        if let Some(complete_word) =
83            validity_packer.push(source_validity_chunks.remainder_bits(), filter_mask)
84        {
85            output_validity.append_word(complete_word, 64);
86        }
87    }
88
89    if let Some((pending_bits, pending_len)) = value_packer.finish() {
90        output_values.append_word(pending_bits, pending_len);
91    }
92    if let Some((pending_bits, pending_len)) = validity_packer.finish() {
93        output_validity.append_word(pending_bits, pending_len);
94    }
95}
96
97#[derive(Debug)]
98pub(crate) struct InProgressBooleanArray {
99    source: Option<ArrayRef>,
100    batch_size: usize,
101    values: Option<BooleanBufferBuilder>,
102    nulls: NullBufferBuilder,
103}
104
105impl InProgressBooleanArray {
106    pub(crate) fn new(batch_size: usize) -> Self {
107        Self {
108            source: None,
109            batch_size,
110            values: None,
111            nulls: NullBufferBuilder::new(batch_size),
112        }
113    }
114
115    fn values(&mut self) -> &mut BooleanBufferBuilder {
116        self.values
117            .get_or_insert_with(|| BooleanBufferBuilder::new(self.batch_size))
118    }
119
120    fn append_array(&mut self, array: &BooleanArray) {
121        self.values().append_buffer(array.values());
122        if let Some(nulls) = array.nulls() {
123            self.nulls.append_buffer(nulls);
124        } else {
125            self.nulls.append_n_non_nulls(array.len());
126        }
127    }
128}
129
130impl InProgressArray for InProgressBooleanArray {
131    fn set_source(&mut self, source: Option<ArrayRef>) {
132        self.source = source;
133    }
134
135    fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(), ArrowError> {
136        let source = self.source.as_ref().ok_or_else(|| {
137            ArrowError::InvalidArgumentError(
138                "Internal Error: InProgressBooleanArray: source not set".to_string(),
139            )
140        })?;
141        let array = source.as_boolean().slice(offset, len);
142        self.append_array(&array);
143        Ok(())
144    }
145
146    fn copy_rows_by_filter_from(
147        &mut self,
148        source: ArrayRef,
149        filter: &FilterPredicate,
150    ) -> Result<(), ArrowError> {
151        if filter.filter_len() > source.len() {
152            return Err(ArrowError::InvalidArgumentError(format!(
153                "Filter predicate of length {} is larger than target array of length {}",
154                filter.filter_len(),
155                source.len()
156            )));
157        }
158
159        if filter.uses_sparse_indices() {
160            let filtered = filter.filter(source.as_ref())?;
161            self.append_array(filtered.as_boolean());
162            return Ok(());
163        }
164
165        let source = source.as_boolean();
166        // Read values and mask in aligned words even when the source is sliced.
167        let filter_chunks = filter.filter_mask().bit_chunks();
168        let source_values = source.values();
169        let source_value_chunks = BitChunks::new(
170            source_values.values(),
171            source_values.offset(),
172            filter.filter_len(),
173        );
174        // Ignore present-but-all-valid buffers to avoid allocating output validity
175        // for data with no actual nulls.
176        let source_validity_chunks =
177            source
178                .nulls()
179                .filter(|nulls| nulls.null_count() != 0)
180                .map(|nulls| {
181                    let nulls = nulls.inner();
182                    BitChunks::new(nulls.values(), nulls.offset(), filter.filter_len())
183                });
184
185        let output_values = self
186            .values
187            .get_or_insert_with(|| BooleanBufferBuilder::new(self.batch_size));
188
189        // Branch once here so non-null inputs avoid validity work in the chunk loop.
190        let selected_count = filter.count();
191        if let Some(source_validity_chunks) = &source_validity_chunks {
192            copy_filter_words_with_nulls(
193                output_values,
194                &mut self.nulls,
195                &source_value_chunks,
196                source_validity_chunks,
197                &filter_chunks,
198            );
199        } else {
200            copy_filter_words_without_nulls(output_values, &source_value_chunks, &filter_chunks);
201            self.nulls.append_n_non_nulls(selected_count);
202        }
203        Ok(())
204    }
205
206    fn finish(&mut self) -> Result<ArrayRef, ArrowError> {
207        let values = self
208            .values
209            .take()
210            .map(|mut values| values.finish())
211            .unwrap_or_else(|| BooleanBuffer::new_unset(0));
212        let nulls = self.nulls.finish();
213        self.nulls = NullBufferBuilder::new(self.batch_size);
214        Ok(Arc::new(BooleanArray::new(values, nulls)))
215    }
216
217    fn size(&self) -> usize {
218        self.source
219            .as_ref()
220            .map_or(0, |source| source.get_array_memory_size())
221            + self
222                .values
223                .as_ref()
224                .map_or(0, |values| values.capacity() / 8)
225            + self.nulls.allocated_size()
226    }
227}
228
229#[cfg(test)]
230mod tests {
231    use super::*;
232    use crate::filter::FilterBuilder;
233    use arrow_buffer::NullBuffer;
234
235    #[test]
236    fn copies_slices_and_sparse_filters() {
237        let source = Arc::new(BooleanArray::from(vec![
238            Some(true),
239            None,
240            Some(false),
241            Some(true),
242            Some(false),
243        ])) as ArrayRef;
244        let mut in_progress = InProgressBooleanArray::new(8);
245        in_progress.set_source(Some(Arc::clone(&source)));
246        in_progress.copy_rows(1, 2).unwrap();
247        in_progress.set_source(None);
248
249        let filter = BooleanArray::from(vec![true, false, false, true, false]);
250        let predicate = FilterBuilder::new(&filter).build();
251        in_progress
252            .copy_rows_by_filter_from(source, &predicate)
253            .unwrap();
254
255        let output = in_progress.finish().unwrap();
256        let expected = BooleanArray::from(vec![None, Some(false), Some(true), Some(true)]);
257        assert_eq!(output.as_boolean(), &expected);
258    }
259
260    #[test]
261    fn finish_resets_buffers() {
262        let mut in_progress = InProgressBooleanArray::new(8);
263        assert_eq!(in_progress.finish().unwrap().len(), 0);
264
265        let source = Arc::new(BooleanArray::from(vec![
266            Some(true),
267            None,
268            Some(false),
269            None,
270        ]));
271        in_progress.set_source(Some(Arc::clone(&source) as ArrayRef));
272        in_progress.copy_rows(0, 2).unwrap();
273        let first = in_progress.finish().unwrap();
274        assert_eq!(first.as_boolean(), &source.slice(0, 2));
275
276        in_progress.copy_rows(2, 2).unwrap();
277        let second = in_progress.finish().unwrap();
278        assert_eq!(second.as_boolean(), &source.slice(2, 2));
279        assert_eq!(in_progress.finish().unwrap().len(), 0);
280    }
281
282    const FILTER_LEN: usize = 269;
283    const SOURCE_OFFSET: usize = 3;
284
285    #[test]
286    fn filtered_words_without_nulls_match_filter_kernel() {
287        let len = SOURCE_OFFSET + FILTER_LEN;
288        let values = (0..len).map(source_value).collect();
289        let all_valid = BooleanArray::new(values, Some(NullBuffer::new_valid(len)))
290            .slice(SOURCE_OFFSET, FILTER_LEN);
291        let without_validity = non_null_source();
292        assert!(without_validity.nulls().is_none());
293        assert!(all_valid.nulls().is_some());
294
295        for (case, source) in [
296            ("without validity", without_validity),
297            ("all-valid validity", all_valid),
298        ] {
299            assert_eq!(source.null_count(), 0);
300            assert_filtered_words_match_filter_kernel(case, source);
301        }
302    }
303
304    #[test]
305    fn filtered_words_with_nulls_match_filter_kernel() {
306        let source = BooleanArray::from_iter(
307            (0..SOURCE_OFFSET + FILTER_LEN)
308                .map(|index| (index % 11 != 0).then_some(index % 3 == 0 || index % 7 == 0)),
309        )
310        .slice(SOURCE_OFFSET, FILTER_LEN);
311        assert!(source.null_count() > 0);
312
313        assert_filtered_words_match_filter_kernel("with nulls", source);
314    }
315
316    #[test]
317    fn filtered_words_with_unaligned_validity_match_filter_kernel() {
318        let values: BooleanBuffer = (0..SOURCE_OFFSET + FILTER_LEN).map(source_value).collect();
319        let validity: BooleanBuffer = (0..FILTER_LEN + 11).map(|index| index % 11 != 0).collect();
320        let source = BooleanArray::new(
321            values.slice(SOURCE_OFFSET, FILTER_LEN),
322            Some(NullBuffer::new(validity.slice(11, FILTER_LEN))),
323        );
324        assert_ne!(source.values().offset(), source.nulls().unwrap().offset());
325
326        assert_filtered_words_match_filter_kernel("unaligned validity", source);
327    }
328
329    fn assert_filtered_words_match_filter_kernel(source_case: &str, source: BooleanArray) {
330        for (filter_case, filter) in filter_cases() {
331            assert_filter_copy_matches_kernel(source_case, filter_case, &source, &filter);
332        }
333    }
334
335    fn filter_cases() -> Vec<(&'static str, BooleanArray)> {
336        let selections = [
337            ("none", vec![]),
338            ("all", (0..FILTER_LEN).collect()),
339            (
340                "word boundaries",
341                vec![0, 1, 7, 63, 64, 65, 127, 128, 191, 192, 255, 256, 268],
342            ),
343            (
344                "carry across source words",
345                // The first two chunks leave 24 carried bits; the third completes a word.
346                (0..40).chain(64..112).chain(128..168).collect(),
347            ),
348            ("alternating", (0..FILTER_LEN).step_by(2).collect()),
349        ];
350        let mut filters: Vec<(&str, BooleanArray)> = selections
351            .into_iter()
352            .map(|(case, selected_indices)| {
353                let filter = (0..FILTER_LEN)
354                    .map(|index| selected_indices.contains(&index))
355                    .collect();
356                (case, filter)
357            })
358            .collect();
359
360        const FILTER_OFFSET: usize = 5;
361        let sliced_filter: BooleanArray = std::iter::repeat_n(false, FILTER_OFFSET)
362            .chain((0..FILTER_LEN).map(|index| index.is_multiple_of(20)))
363            .collect();
364        let sliced_filter = sliced_filter.slice(FILTER_OFFSET, FILTER_LEN);
365        assert_eq!(sliced_filter.values().offset(), FILTER_OFFSET);
366        filters.push(("sliced filter", sliced_filter));
367
368        let shorter_filter = (0_usize..197)
369            .map(|index| index.is_multiple_of(17))
370            .collect();
371        filters.push(("shorter than source", shorter_filter));
372
373        let aligned_filter = (0_usize..256)
374            .map(|index| index.is_multiple_of(19))
375            .collect();
376        filters.push(("empty remainder", aligned_filter));
377
378        let mut filter_values = vec![false; FILTER_LEN];
379        for index in [1, 65, 129, 268] {
380            filter_values[index] = true;
381        }
382        let mut filter_validity = vec![true; FILTER_LEN];
383        filter_validity[65] = false;
384        let filter_with_null = BooleanArray::new(
385            BooleanBuffer::from(filter_values),
386            Some(NullBuffer::new(BooleanBuffer::from(filter_validity))),
387        );
388        assert!(filter_with_null.value(65));
389        assert!(filter_with_null.is_null(65));
390        filters.push(("null filter entry", filter_with_null));
391        filters
392    }
393
394    fn assert_filter_copy_matches_kernel(
395        source_case: &str,
396        filter_case: &str,
397        source: &BooleanArray,
398        filter: &BooleanArray,
399    ) {
400        const PREFIX_LEN: usize = 5;
401        let expect_lazy_validity = source.null_count() == 0;
402
403        for optimize in [false, true] {
404            let builder = FilterBuilder::new(filter);
405            let predicate = if optimize {
406                builder.optimize().build()
407            } else {
408                builder.build()
409            };
410            let filtered = predicate.filter(source).unwrap();
411            let prefix = source.slice(0, PREFIX_LEN);
412            let expected = crate::concat::concat(&[&prefix, filtered.as_ref()]).unwrap();
413
414            let source = Arc::new(source.clone()) as ArrayRef;
415            let mut in_progress = InProgressBooleanArray::new(FILTER_LEN);
416            in_progress.set_source(Some(Arc::clone(&source)));
417            in_progress.copy_rows(0, PREFIX_LEN).unwrap();
418            in_progress.set_source(None);
419            in_progress
420                .copy_rows_by_filter_from(source, &predicate)
421                .unwrap();
422
423            let output = in_progress.finish().unwrap();
424            assert_eq!(
425                output.as_boolean(),
426                expected.as_boolean(),
427                "{source_case}, {filter_case}, optimize={optimize}"
428            );
429            if expect_lazy_validity {
430                assert!(
431                    output.nulls().is_none(),
432                    "{source_case}, {filter_case}, optimize={optimize} should preserve lazy validity"
433                );
434            }
435        }
436    }
437
438    fn non_null_source() -> BooleanArray {
439        let source: BooleanArray = (0..SOURCE_OFFSET + FILTER_LEN).map(source_value).collect();
440        source.slice(SOURCE_OFFSET, FILTER_LEN)
441    }
442
443    fn source_value(index: usize) -> bool {
444        index.is_multiple_of(3) || index.is_multiple_of(7)
445    }
446
447    #[test]
448    fn filter_longer_than_source_returns_error() {
449        let source = Arc::new(BooleanArray::from(vec![true, false])) as ArrayRef;
450        let filter_mask = BooleanArray::from(vec![true, false, true]);
451        let predicate = FilterBuilder::new(&filter_mask).build();
452        let mut in_progress = InProgressBooleanArray::new(8);
453
454        let error = in_progress
455            .copy_rows_by_filter_from(source, &predicate)
456            .unwrap_err();
457        assert_eq!(
458            error.to_string(),
459            "Invalid argument error: Filter predicate of length 3 is larger than target array of length 2"
460        );
461    }
462}