1use 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 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 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 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 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 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 (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}