alamb commented on code in PR #8902: URL: https://github.com/apache/arrow-rs/pull/8902#discussion_r2560363367
########## parquet/src/arrow/arrow_reader/selection/mask.rs: ########## @@ -0,0 +1,566 @@ +// 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 crate::arrow::arrow_reader::{RowSelection, RowSelector}; +use arrow_array::{Array, BooleanArray}; +use arrow_buffer::bit_iterator::BitIndexIterator; +use arrow_buffer::{BooleanBuffer, BooleanBufferBuilder, MutableBuffer}; +use std::ops::Range; + +/// Selection based on a [`BooleanArray`] +/// +/// This represents the result of a filter evaluation as a bitmap. It is +/// more efficient for sparse filter results with many small skips or selections. +/// +/// It is similar to the "Bitmap Index" described in +/// [Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses] +/// +/// [Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses]: https://dl.acm.org/doi/10.1145/3626246.3653395 +/// +/// Originally from Xiangpeng Hao in <https://github.com/apache/arrow-rs/pull/6624> +#[derive(Debug, Clone, Eq, PartialEq)] +pub(crate) struct BooleanRowSelection { + selector: BooleanBuffer, +} + +impl BooleanRowSelection { + /// Create a new [`BooleanRowSelection] from a list of [`BooleanArray`]. + pub fn from_filters(filters: &[BooleanArray]) -> Self { + let arrays: Vec<&dyn Array> = filters.iter().map(|x| x as &dyn Array).collect(); + let result = arrow_select::concat::concat(&arrays).unwrap().into_data(); + let (boolean_array, _null) = BooleanArray::from(result).into_parts(); + BooleanRowSelection { + selector: boolean_array, + } + } + + /// Create a new [`BooleanRowSelection`] with all rows unselected + pub fn new_unselected(row_count: usize) -> Self { + let buffer = BooleanBuffer::new_unset(row_count); + + BooleanRowSelection { selector: buffer } + } + + /// Create a new [`BooleanRowSelection`] with all rows selected + pub fn new_selected(row_count: usize) -> Self { + let buffer = BooleanBuffer::new_set(row_count); + + BooleanRowSelection { selector: buffer } + } + + /// Returns a new [`BooleanRowSelection`] that selects the inverse of this [`BooleanRowSelection`]. + pub fn as_inverted(&self) -> Self { + let buffer = !&self.selector; + BooleanRowSelection { selector: buffer } + } + + /// Returns the number of rows selected by this [`BooleanRowSelection`]. + pub fn row_count(&self) -> usize { + self.selector.count_set_bits() + } + + /// Create a new [`BooleanRowSelection`] from a list of consecutive ranges. + pub fn from_consecutive_ranges( + ranges: impl Iterator<Item = Range<usize>>, + total_rows: usize, + ) -> Self { + let mut buffer = BooleanBufferBuilder::new(total_rows); + let mut last_end = 0; + + for range in ranges { + let len = range.end - range.start; + if len == 0 { + continue; + } + + if range.start > last_end { + buffer.append_n(range.start - last_end, false); + } + buffer.append_n(len, true); + last_end = range.end; + } + + if last_end != total_rows { + buffer.append_n(total_rows - last_end, false); + } + + BooleanRowSelection { + selector: buffer.finish(), + } + } + + /// Compute the union of two [`BooleanRowSelection`] + /// For example: + /// self: NNYYYYNNYYNYN + /// other: NYNNNNNNN + /// + /// returned: NYYYYYNNYYNYN + #[must_use] + pub fn union(&self, other: &Self) -> Self { + // use arrow::compute::kernels::boolean::or; + + let union_selectors = &self.selector | &other.selector; + + BooleanRowSelection { + selector: union_selectors, + } + } + + /// Compute the intersection of two [`BooleanRowSelection`] + /// For example: + /// self: NNYYYYNNYYNYN + /// other: NYNNNNNNY + /// + /// returned: NNNNNNNNYYNYN + #[must_use] + pub fn intersection(&self, other: &Self) -> Self { + let intersection_selectors = &self.selector & &other.selector; + + BooleanRowSelection { + selector: intersection_selectors, + } + } + + /// Combines this [`BooleanRowSelection`] with another using logical AND on the selected bits. + /// + /// Unlike intersection, the `other` [`BooleanRowSelection`] must have exactly as many set bits as `self`. + /// This method will keep only the bits in `self` that are also set in `other` + /// at the positions corresponding to `self`'s set bits. + pub fn and_then(&self, other: &Self) -> Self { + // Ensure that 'other' has exactly as many set bits as 'self' + debug_assert_eq!( + self.row_count(), + other.selector.len(), + "The 'other' selection must have exactly as many set bits as 'self'." + ); + + if self.selector.len() == other.selector.len() { + // fast path if the two selections are the same length + // common if this is the first predicate + debug_assert_eq!(self.row_count(), self.selector.len()); + return self.intersection(other); + } + + let mut buffer = MutableBuffer::from_len_zeroed(self.selector.inner().len()); + buffer.copy_from_slice(self.selector.inner().as_slice()); + let mut builder = BooleanBufferBuilder::new_from_buffer(buffer, self.selector.len()); + + // Create iterators for 'self' and 'other' bits + let mut other_bits = other.selector.iter(); + + for bit_idx in self.true_iter() { + let predicate = other_bits + .next() + .expect("Mismatch in set bits between self and other"); + if !predicate { + builder.set_bit(bit_idx, false); + } + } + + BooleanRowSelection { + selector: builder.finish(), + } + } + + /// Returns an iterator over the indices of the set bits in this [`BooleanRowSelection`] + pub fn true_iter(&self) -> BitIndexIterator<'_> { + self.selector.set_indices() + } + + /// Returns `true` if this [`BooleanRowSelection`] selects any rows + pub fn selects_any(&self) -> bool { + self.true_iter().next().is_some() + } + + /// Returns a new [`BooleanRowSelection`] that selects the rows in this [`BooleanRowSelection`] from `offset` to `offset + len` + pub fn slice(&self, offset: usize, len: usize) -> BooleanArray { + BooleanArray::new(self.selector.slice(offset, len), None) + } +} + +impl From<Vec<RowSelector>> for BooleanRowSelection { + fn from(selection: Vec<RowSelector>) -> Self { + let selection = RowSelection::from(selection); + RowSelection::into(selection) + } +} + +impl From<RowSelection> for BooleanRowSelection { + fn from(selection: RowSelection) -> Self { + let total_rows = selection.row_count(); + let mut builder = BooleanBufferBuilder::new(total_rows); + + for selector in selection.iter() { + if selector.skip { + builder.append_n(selector.row_count, false); + } else { + builder.append_n(selector.row_count, true); + } + } + + BooleanRowSelection { + selector: builder.finish(), + } + } +} + +impl From<&BooleanRowSelection> for RowSelection { + fn from(selection: &BooleanRowSelection) -> Self { + let array = BooleanArray::new(selection.selector.clone(), None); + RowSelection::from_filters(&[array]) + } +} + +/// Combines this [`BooleanBuffer`] with another using logical AND on the selected bits. +/// +/// Unlike intersection, the `other` [`BooleanBuffer`] must have exactly as many **set bits** as `self`, +/// i.e., self.count_set_bits() == other.len(). +/// +/// This method will keep only the bits in `self` that are also set in `other` +/// at the positions corresponding to `self`'s set bits. +/// For example: +/// left: NNYYYNNYYNYN +/// right: YNY NY N +/// result: NNYNYNNNYNNN +/// +/// Optimized version of `boolean_buffer_and_then` using BMI2 PDEP instructions. +/// This function performs the same operation but uses bit manipulation instructions +/// for better performance on supported x86_64 CPUs. +pub fn boolean_buffer_and_then(left: &BooleanBuffer, right: &BooleanBuffer) -> BooleanBuffer { Review Comment: @XiangpengHao did this it in liquid cache: - https://github.com/XiangpengHao/liquid-cache/blob/60323cdb5f17f88af633ad9acbc7d74f684f9912/src/parquet/src/utils.rs#L17 I will copy that new version over here in this PR -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
