parquet/arrow/arrow_reader/selection/
mod.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18//! Logic for selecting which rows to read: [`RowSelection`] and [`RowSelector`]
19//!
20//! This module holds [`RowSelection`] and its public API, which dispatches to
21//! one of the two backings depending on how the selection is stored:
22//!
23//! * `selector`: the run length backing, [`RowSelector`] and its primitives
24//! * `boolean`: the bitmap backing, `MaskSelection` and its primitives
25//!
26//! The remaining modules hold the operations that are common to both:
27//!
28//! * `algebra`: `and_then`, `intersection` and `union`
29//! * `ranges`: mapping a [`RowSelection`] onto page and batch ranges
30//! * `cursor`: iterating a [`RowSelection`] while reading
31
32use crate::file::page_index::offset_index::PageLocation;
33use arrow_array::{Array, BooleanArray};
34use arrow_buffer::{BooleanBuffer, BooleanBufferBuilder};
35use arrow_select::filter::SlicesIterator;
36use std::cmp::Ordering;
37use std::collections::VecDeque;
38use std::ops::Range;
39
40mod algebra;
41mod boolean;
42mod cursor;
43mod ranges;
44mod selector;
45
46use algebra::{
47    and_then_mask, and_then_row_selections, and_then_selectors_with_mask, intersect_masks,
48    intersect_row_selections, union_masks, union_row_selections,
49};
50pub use boolean::MaskRunIter;
51use boolean::{
52    MaskSelection, limit_mask, mask_has_at_least_runs, offset_mask, split_off_mask, trim_mask,
53};
54pub(crate) use cursor::{LoadedRowRanges, MaskCursor, RowSelectionStrategy};
55pub use cursor::{RowSelectionCursor, RowSelectionPolicy};
56use ranges::{expand_to_batch_boundaries_from_selectors, scan_ranges_from_selectors};
57pub use selector::RowSelector;
58use selector::{limit_selectors, offset_selectors, split_off_selectors};
59
60/// [`RowSelection`] represents selecting a subset of rows
61/// when scanning a parquet file.
62///
63/// This is applied prior to reading column data, and can therefore
64/// be used to skip IO to fetch data into memory
65///
66/// A typical use-case would be using the [`PageIndex`] to filter out rows
67/// that don't satisfy a predicate
68///
69/// Depending on the pattern of rows to be selected, [`RowSelection`] has
70/// either a bitmap or an RLE ([`RowSelector`]) based implementation.
71///
72/// # Example
73/// ```
74/// use parquet::arrow::arrow_reader::{RowSelection, RowSelector};
75///
76/// let selectors = vec![
77///     RowSelector::skip(5),
78///     RowSelector::select(5),
79///     RowSelector::select(5),
80///     RowSelector::skip(5),
81/// ];
82///
83/// // Creating a selection will combine adjacent selectors
84/// let selection: RowSelection = selectors.into();
85///
86/// let expected = vec![
87///     RowSelector::skip(5),
88///     RowSelector::select(10),
89///     RowSelector::skip(5),
90/// ];
91///
92/// let actual: Vec<RowSelector> = selection.into();
93/// assert_eq!(actual, expected);
94///
95/// // you can also create a selection from consecutive ranges
96/// let ranges = vec![5..10, 10..15];
97/// let selection =
98///   RowSelection::from_consecutive_ranges(ranges.into_iter(), 20);
99/// let actual: Vec<RowSelector> = selection.into();
100/// assert_eq!(actual, expected);
101///
102/// // or directly from a packed bitmap, when the upstream producer already
103/// // has one. The bitmap is kept as-is rather than run-length-encoded.
104/// use arrow_buffer::BooleanBuffer;
105/// let mask = BooleanBuffer::from(vec![true, false, true, true]);
106/// let selection = RowSelection::from_boolean_buffer(mask);
107/// assert_eq!(selection.row_count(), 3);
108/// ```
109///
110/// An RLE ([`RowSelector`]) backed [`RowSelection`] maintains the following
111/// invariants (they do not apply to the bitmap backed implementation):
112///
113/// * It contains no [`RowSelector`] of 0 rows
114/// * Consecutive [`RowSelector`]s alternate skipping or selecting rows
115///
116/// [`PageIndex`]: crate::file::page_index::column_index::ColumnIndexMetaData
117#[derive(Default, Clone)]
118pub struct RowSelection {
119    inner: RowSelectionInner,
120}
121
122/// Internal storage for [`RowSelection`].
123#[derive(Debug, Clone)]
124pub(crate) enum RowSelectionInner {
125    Selectors(Vec<RowSelector>),
126    Mask(Box<MaskSelection>),
127}
128
129impl Default for RowSelectionInner {
130    fn default() -> Self {
131        Self::Selectors(Vec::new())
132    }
133}
134
135impl std::fmt::Debug for RowSelection {
136    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
137        match &self.inner {
138            RowSelectionInner::Selectors(s) => f
139                .debug_struct("RowSelection")
140                .field("selectors", s)
141                .finish(),
142            RowSelectionInner::Mask(m) => f
143                .debug_struct("RowSelection")
144                .field("mask_len", &m.mask().len())
145                .finish_non_exhaustive(),
146        }
147    }
148}
149
150impl PartialEq for RowSelection {
151    fn eq(&self, other: &Self) -> bool {
152        match (&self.inner, &other.inner) {
153            (RowSelectionInner::Selectors(a), RowSelectionInner::Selectors(b)) => a == b,
154            (RowSelectionInner::Mask(a), RowSelectionInner::Mask(b)) => a.mask() == b.mask(),
155            (RowSelectionInner::Mask(mask), RowSelectionInner::Selectors(selectors))
156            | (RowSelectionInner::Selectors(selectors), RowSelectionInner::Mask(mask)) => {
157                if selectors
158                    .iter()
159                    .try_fold(0usize, |acc, selector| acc.checked_add(selector.row_count))
160                    != Some(mask.mask().len())
161                {
162                    return false;
163                }
164
165                let mut slices = mask.mask().set_slices().peekable();
166                let mut cursor = 0usize;
167
168                for selector in selectors {
169                    let end = cursor + selector.row_count;
170
171                    if selector.skip {
172                        if slices.peek().is_some_and(|(start, _)| *start < end) {
173                            return false;
174                        }
175                    } else {
176                        match slices.next() {
177                            Some((start, slice_end)) if start == cursor && slice_end == end => {}
178                            _ => return false,
179                        }
180                    }
181
182                    cursor = end;
183                }
184
185                slices.next().is_none()
186            }
187        }
188    }
189}
190
191impl Eq for RowSelection {}
192
193impl RowSelection {
194    /// Not `pub`: unlike `From<Vec<RowSelector>>`, this performs no
195    /// validation/normalization of the selectors (e.g. combining adjacent
196    /// selectors), so callers must uphold the invariants themselves.
197    fn from_selectors(selectors: Vec<RowSelector>) -> Self {
198        Self {
199            inner: RowSelectionInner::Selectors(selectors),
200        }
201    }
202
203    /// Create a [`RowSelection`] from a packed [`BooleanBuffer`].
204    ///
205    /// Each set bit selects a row, each unset bit skips one. Unlike
206    /// [`Self::from_filters`], the bitmap is kept as-is rather than
207    /// eagerly run-length-encoded. [`Self::iter`] materializes and caches the
208    /// RLE form on first use; use [`MaskRunIter`] to stream the RLE form
209    /// directly from the bitmap.
210    pub fn from_boolean_buffer(mask: BooleanBuffer) -> Self {
211        Self {
212            inner: RowSelectionInner::Mask(Box::new(MaskSelection::new(mask))),
213        }
214    }
215
216    fn from_mask_selection(mask: MaskSelection) -> Self {
217        Self {
218            inner: RowSelectionInner::Mask(Box::new(mask)),
219        }
220    }
221
222    /// Returns the underlying mask if this selection is mask-backed.
223    ///
224    /// Public so that engines composing selections (e.g. DataFusion's
225    /// [`ParquetAccessPlan::into_overall_row_selection`]) can concatenate
226    /// mask-backed selections without materialising the RLE form.
227    ///
228    /// [`ParquetAccessPlan::into_overall_row_selection`]: https://docs.rs/datafusion-datasource-parquet/latest/datafusion_datasource_parquet/access_plan/struct.ParquetAccessPlan.html#method.into_overall_row_selection
229    pub fn as_mask(&self) -> Option<&BooleanBuffer> {
230        match &self.inner {
231            RowSelectionInner::Mask(m) => Some(m.mask()),
232            RowSelectionInner::Selectors(_) => None,
233        }
234    }
235
236    /// Consume the selection and return its internal storage.
237    pub(crate) fn into_inner(self) -> RowSelectionInner {
238        self.inner
239    }
240
241    /// Choose the automatic materialisation strategy without converting between
242    /// selector and mask backing.
243    #[inline]
244    pub(crate) fn auto_selection_strategy(&self, threshold: usize) -> RowSelectionStrategy {
245        match &self.inner {
246            RowSelectionInner::Selectors(selectors) => {
247                let (total_rows, run_count) =
248                    selectors
249                        .iter()
250                        .fold((0usize, 0usize), |(rows, count), selector| {
251                            if selector.row_count > 0 {
252                                (rows + selector.row_count, count + 1)
253                            } else {
254                                (rows, count)
255                            }
256                        });
257
258                if run_count == 0
259                    || auto_min_mask_runs(total_rows, threshold)
260                        .is_some_and(|min_runs| run_count >= min_runs)
261                {
262                    RowSelectionStrategy::Mask
263                } else {
264                    RowSelectionStrategy::Selectors
265                }
266            }
267            RowSelectionInner::Mask(mask) => {
268                let mask = mask.mask();
269                let total_rows = mask.len();
270
271                if total_rows == 0 {
272                    return RowSelectionStrategy::Mask;
273                }
274
275                match auto_min_mask_runs(total_rows, threshold) {
276                    Some(min_runs) if mask_has_at_least_runs(mask, min_runs) => {
277                        RowSelectionStrategy::Mask
278                    }
279                    _ => RowSelectionStrategy::Selectors,
280                }
281            }
282        }
283    }
284
285    #[cfg(test)]
286    fn selectors(&self) -> Vec<RowSelector> {
287        self.iter().copied().collect()
288    }
289
290    fn into_selectors_vec(self) -> Vec<RowSelector> {
291        match self.inner {
292            RowSelectionInner::Selectors(s) => s,
293            RowSelectionInner::Mask(m) => (*m).into_selectors(),
294        }
295    }
296
297    /// Creates a [`RowSelection`] from a slice of [`BooleanArray`]
298    ///
299    /// # Panics
300    ///
301    /// Panics if any of the [`BooleanArray`] contain nulls
302    pub fn from_filters(filters: &[BooleanArray]) -> Self {
303        let mut next_offset = 0;
304        let total_rows = filters.iter().map(|x| x.len()).sum();
305
306        let iter = filters.iter().flat_map(|filter| {
307            let offset = next_offset;
308            next_offset += filter.len();
309            assert_eq!(filter.null_count(), 0);
310            SlicesIterator::new(filter).map(move |(start, end)| start + offset..end + offset)
311        });
312
313        Self::from_consecutive_ranges(iter, total_rows)
314    }
315
316    /// Builds a selection equivalent to [`Self::from_filters`] whose backing
317    /// matches [`RowSelectionPolicy::Auto`]. Selector materialization stops as
318    /// soon as the final mask strategy is known.
319    ///
320    /// # Panics
321    ///
322    /// Panics if any of the [`BooleanArray`] contain nulls.
323    pub(crate) fn from_filters_auto(filters: &[BooleanArray], threshold: usize) -> Self {
324        let total_rows = filters.iter().map(|filter| filter.len()).sum::<usize>();
325
326        // Empty selector-backed selections resolve to Mask under Auto. Preserve
327        // that decision in the backing selected by this constructor.
328        if total_rows == 0 {
329            return Self::from_boolean_buffer(BooleanBuffer::new_unset(0));
330        }
331
332        let Some(min_mask_runs) = auto_min_mask_runs(total_rows, threshold) else {
333            return Self::from_filters(filters);
334        };
335
336        match selectors_below_run_limit(filters, total_rows, min_mask_runs) {
337            Some(selectors) => Self::from_selectors(selectors),
338            None => Self::from_filters_mask(filters),
339        }
340    }
341
342    /// Creates a mask-backed [`RowSelection`] from predicate filters.
343    ///
344    /// # Panics
345    ///
346    /// Panics if any of the [`BooleanArray`] contain nulls.
347    pub(crate) fn from_filters_mask(filters: &[BooleanArray]) -> Self {
348        let mask = match filters {
349            [filter] => {
350                assert_eq!(filter.null_count(), 0);
351                filter.values().clone()
352            }
353            _ => filters_to_boolean_buffer(filters),
354        };
355        Self::from_boolean_buffer(mask)
356    }
357
358    /// Creates a [`RowSelection`] from an iterator of consecutive ranges to keep
359    pub fn from_consecutive_ranges<I: Iterator<Item = Range<usize>>>(
360        ranges: I,
361        total_rows: usize,
362    ) -> Self {
363        let mut selectors: Vec<RowSelector> = Vec::with_capacity(ranges.size_hint().0);
364        let mut last_end = 0;
365        for range in ranges {
366            let len = range.end - range.start;
367            if len == 0 {
368                continue;
369            }
370
371            match range.start.cmp(&last_end) {
372                Ordering::Equal => match selectors.last_mut() {
373                    Some(last) => last.row_count = last.row_count.checked_add(len).unwrap(),
374                    None => selectors.push(RowSelector::select(len)),
375                },
376                Ordering::Greater => {
377                    selectors.push(RowSelector::skip(range.start - last_end));
378                    selectors.push(RowSelector::select(len))
379                }
380                Ordering::Less => panic!("out of order"),
381            }
382            last_end = range.end;
383        }
384
385        if last_end != total_rows {
386            selectors.push(RowSelector::skip(total_rows - last_end))
387        }
388
389        Self::from_selectors(selectors)
390    }
391
392    /// Given an offset index, return the byte ranges for all data pages selected by `self`
393    ///
394    /// This is useful for determining what byte ranges to fetch from underlying storage
395    ///
396    /// Note: this method does not make any effort to combine consecutive ranges, nor coalesce
397    /// ranges that are close together. This is instead delegated to the IO subsystem to optimise,
398    /// e.g. `ObjectStore::get_ranges` in the [`object_store`] crate
399    ///
400    /// [`object_store`]: https://crates.io/crates/object_store
401    pub fn scan_ranges(&self, page_locations: &[PageLocation]) -> Vec<Range<u64>> {
402        match &self.inner {
403            RowSelectionInner::Selectors(selectors) => {
404                scan_ranges_from_selectors(selectors.iter().copied(), page_locations)
405            }
406            RowSelectionInner::Mask(mask) => {
407                scan_ranges_from_selectors(MaskRunIter::new(mask.mask()), page_locations)
408            }
409        }
410    }
411
412    /// Returns the complete row ranges of the pages selected by [`Self::scan_ranges`].
413    pub(crate) fn row_ranges_for_selected_pages(
414        &self,
415        page_locations: &[PageLocation],
416        total_rows: usize,
417    ) -> Vec<Range<usize>> {
418        let mut selected_pages = self.scan_ranges(page_locations).into_iter().peekable();
419        let mut row_ranges = Vec::new();
420
421        for (idx, page) in page_locations.iter().enumerate() {
422            let Some(selected_page) = selected_pages.peek() else {
423                break;
424            };
425            if selected_page.start != page.offset as u64 {
426                continue;
427            }
428            selected_pages.next();
429
430            let end = page_locations
431                .get(idx + 1)
432                .map(|next| next.first_row_index as usize)
433                .unwrap_or(total_rows);
434            row_ranges.push(page.first_row_index as usize..end);
435        }
436
437        row_ranges
438    }
439
440    /// Splits off the first `row_count` from this [`RowSelection`]
441    pub fn split_off(&mut self, row_count: usize) -> Self {
442        match std::mem::take(&mut self.inner) {
443            RowSelectionInner::Mask(mask) => {
444                let total = mask.cached_count();
445                let (head, tail) = split_off_mask((*mask).into_mask(), row_count);
446                // Popcount only the head and derive the tail by subtraction, so
447                // repeated splits stay O(bitmap) overall.
448                let (head, tail) = match total {
449                    Some(total) => {
450                        let head_count = if tail.is_empty() {
451                            total
452                        } else {
453                            head.count_set_bits()
454                        };
455                        (
456                            MaskSelection::with_count(head, head_count),
457                            MaskSelection::with_count(tail, total - head_count),
458                        )
459                    }
460                    None => (MaskSelection::new(head), MaskSelection::new(tail)),
461                };
462                self.inner = RowSelectionInner::Mask(Box::new(tail));
463                Self::from_mask_selection(head)
464            }
465            RowSelectionInner::Selectors(selectors) => {
466                let (head, tail) = split_off_selectors(selectors, row_count);
467                self.inner = RowSelectionInner::Selectors(tail);
468                Self::from_selectors(head)
469            }
470        }
471    }
472
473    /// returns a [`RowSelection`] representing rows that are selected in both
474    /// input [`RowSelection`]s.
475    ///
476    /// This is equivalent to the logical `AND` / conjunction of the two
477    /// selections.
478    ///
479    /// # Example
480    /// If `N` means the row is not selected, and `Y` means it is
481    /// selected:
482    ///
483    /// ```text
484    /// self:     NNNNNNNNNNNNYYYYYYYYYYYYYYYYYYYYYYNNNYYYYY
485    /// other:                YYYYYNNNNYYYYYYYYYYYYY   YYNNN
486    ///
487    /// returned: NNNNNNNNNNNNYYYYYNNNNYYYYYYYYYYYYYNNNYYNNN
488    /// ```
489    ///
490    /// # Panics
491    ///
492    /// Panics if `other` does not have a length equal to the number of rows selected
493    /// by this RowSelection
494    ///
495    pub fn and_then(&self, other: &Self) -> Self {
496        match (&self.inner, &other.inner) {
497            (RowSelectionInner::Mask(mask), _) => {
498                Self::from_boolean_buffer(and_then_mask(mask.mask(), other))
499            }
500            (RowSelectionInner::Selectors(first), RowSelectionInner::Selectors(second)) => {
501                and_then_row_selections(first, second)
502            }
503            (RowSelectionInner::Selectors(first), RowSelectionInner::Mask(second)) => {
504                and_then_selectors_with_mask(first, second.mask())
505            }
506        }
507    }
508
509    /// Compute the intersection of two [`RowSelection`]
510    /// For example:
511    /// self:      NNYYYYNNYYNYN
512    /// other:     NYNNNNNNY
513    ///
514    /// returned:  NNNNNNNNYYNYN
515    pub fn intersection(&self, other: &Self) -> Self {
516        match (&self.inner, &other.inner) {
517            (RowSelectionInner::Mask(l), RowSelectionInner::Mask(r)) => {
518                Self::from_boolean_buffer(intersect_masks(l.mask(), r.mask()))
519            }
520            (RowSelectionInner::Selectors(l), RowSelectionInner::Selectors(r)) => {
521                intersect_row_selections(l, r)
522            }
523            (RowSelectionInner::Selectors(l), RowSelectionInner::Mask(r)) => {
524                intersect_row_selections(l, &r.borrowed_selectors())
525            }
526            (RowSelectionInner::Mask(l), RowSelectionInner::Selectors(r)) => {
527                intersect_row_selections(&l.borrowed_selectors(), r)
528            }
529        }
530    }
531
532    /// Compute the union of two [`RowSelection`]
533    /// For example:
534    /// self:      NNYYYYNNYYNYN
535    /// other:     NYNNNNNNN
536    ///
537    /// returned:  NYYYYYNNYYNYN
538    pub fn union(&self, other: &Self) -> Self {
539        match (&self.inner, &other.inner) {
540            (RowSelectionInner::Mask(l), RowSelectionInner::Mask(r)) => {
541                Self::from_boolean_buffer(union_masks(l.mask(), r.mask()))
542            }
543            (RowSelectionInner::Selectors(l), RowSelectionInner::Selectors(r)) => {
544                union_row_selections(l, r)
545            }
546            (RowSelectionInner::Selectors(l), RowSelectionInner::Mask(r)) => {
547                union_row_selections(l, &r.borrowed_selectors())
548            }
549            (RowSelectionInner::Mask(l), RowSelectionInner::Selectors(r)) => {
550                union_row_selections(&l.borrowed_selectors(), r)
551            }
552        }
553    }
554
555    /// Returns `true` if this [`RowSelection`] selects any rows
556    pub fn selects_any(&self) -> bool {
557        match &self.inner {
558            RowSelectionInner::Selectors(s) => s.iter().any(|x| !x.skip),
559            RowSelectionInner::Mask(m) => match m.cached_count() {
560                Some(count) => count > 0,
561                None => m.mask().set_indices().next().is_some(),
562            },
563        }
564    }
565
566    /// Trims this [`RowSelection`] removing any trailing skips
567    pub(crate) fn trim(self) -> Self {
568        match self.inner {
569            RowSelectionInner::Mask(m) => {
570                let trimmed = trim_mask(m.mask());
571                let cached_count = m.cached_count();
572                match trimmed {
573                    // Trimming only drops trailing unset bits; the count is unchanged.
574                    Some(mask) => match cached_count {
575                        Some(count) => {
576                            Self::from_mask_selection(MaskSelection::with_count(mask, count))
577                        }
578                        None => Self::from_boolean_buffer(mask),
579                    },
580                    // Nothing to trim, hand the existing box back untouched.
581                    None => Self {
582                        inner: RowSelectionInner::Mask(m),
583                    },
584                }
585            }
586            RowSelectionInner::Selectors(mut selectors) => {
587                while selectors.last().map(|x| x.skip).unwrap_or(false) {
588                    selectors.pop();
589                }
590                Self::from_selectors(selectors)
591            }
592        }
593    }
594
595    /// Applies an offset to this [`RowSelection`], skipping the first `offset` selected rows
596    pub(crate) fn offset(self, offset: usize) -> Self {
597        if offset == 0 {
598            return self;
599        }
600
601        match self.inner {
602            RowSelectionInner::Mask(mask) => {
603                let count = mask.count();
604                let buffer = offset_mask((*mask).into_mask(), offset, count);
605                Self::from_mask_selection(MaskSelection::with_count(
606                    buffer,
607                    count.saturating_sub(offset),
608                ))
609            }
610            RowSelectionInner::Selectors(selectors) => {
611                Self::from_selectors(offset_selectors(selectors, offset))
612            }
613        }
614    }
615
616    /// Limit this [`RowSelection`] to only select `limit` rows
617    pub(crate) fn limit(self, limit: usize) -> Self {
618        match self.inner {
619            RowSelectionInner::Mask(mask) => {
620                let cached = mask.cached_count();
621                let buffer = limit_mask((*mask).into_mask(), limit);
622                match cached {
623                    Some(count) => Self::from_mask_selection(MaskSelection::with_count(
624                        buffer,
625                        count.min(limit),
626                    )),
627                    None => Self::from_boolean_buffer(buffer),
628                }
629            }
630            RowSelectionInner::Selectors(selectors) => {
631                Self::from_selectors(limit_selectors(selectors, limit))
632            }
633        }
634    }
635
636    /// Returns an iterator over the [`RowSelector`]s for this
637    /// [`RowSelection`].
638    ///
639    /// Mask-backed selections materialize a `Vec<RowSelector>` cache on first
640    /// call (one allocation, `O(set_slices)` work) so the iterator can hand out
641    /// `&RowSelector`; the cache is not copied on clone. For single-pass walks
642    /// over mask-backed selections, prefer streaming directly via
643    /// [`Self::as_mask`] + [`MaskRunIter::new`] — that path is allocation-free
644    /// and avoids populating the cache.
645    pub fn iter(&self) -> impl Iterator<Item = &RowSelector> {
646        match &self.inner {
647            RowSelectionInner::Selectors(s) => s.iter(),
648            RowSelectionInner::Mask(m) => m.selectors().iter(),
649        }
650    }
651
652    /// Returns the number of selected rows
653    pub fn row_count(&self) -> usize {
654        match &self.inner {
655            RowSelectionInner::Selectors(s) => {
656                s.iter().filter(|x| !x.skip).map(|x| x.row_count).sum()
657            }
658            RowSelectionInner::Mask(m) => m.count(),
659        }
660    }
661
662    /// Returns the total number of rows spanned by this selection, both
663    /// selected and skipped
664    pub fn total_row_count(&self) -> usize {
665        match &self.inner {
666            RowSelectionInner::Selectors(s) => s.iter().map(|x| x.row_count).sum(),
667            RowSelectionInner::Mask(m) => m.mask().len(),
668        }
669    }
670
671    /// Returns the number of de-selected rows
672    pub fn skipped_row_count(&self) -> usize {
673        match &self.inner {
674            RowSelectionInner::Selectors(s) => {
675                s.iter().filter(|x| x.skip).map(|x| x.row_count).sum()
676            }
677            RowSelectionInner::Mask(m) => m.mask().len() - m.count(),
678        }
679    }
680
681    /// Expands the selection to align with batch boundaries.
682    /// This is needed when using cached array readers to ensure that
683    /// the cached data covers full batches.
684    pub(crate) fn expand_to_batch_boundaries(&self, batch_size: usize, total_rows: usize) -> Self {
685        if batch_size == 0 {
686            return self.clone();
687        }
688
689        match &self.inner {
690            RowSelectionInner::Selectors(selectors) => expand_to_batch_boundaries_from_selectors(
691                selectors.iter().copied(),
692                batch_size,
693                total_rows,
694            ),
695            RowSelectionInner::Mask(mask) => expand_to_batch_boundaries_from_selectors(
696                MaskRunIter::new(mask.mask()),
697                batch_size,
698                total_rows,
699            ),
700        }
701    }
702}
703
704/// Returns the minimum normalized run count for which the Auto selection policy
705/// would prefer a mask to RLE.
706///
707/// Auto prefers masks when the average run length is strictly below `threshold`.
708/// For positive thresholds and totals below `usize::MAX`, the first qualifying
709/// run count is `floor(total_rows / threshold) + 1`.
710///
711/// Returns `None` when selectors are always preferred for a non-empty selection.
712/// Callers handle empty selections separately.
713#[inline]
714fn auto_min_mask_runs(total_rows: usize, threshold: usize) -> Option<usize> {
715    // The strict comparison against a saturated product cannot succeed when
716    // the left-hand side is already usize::MAX.
717    if total_rows == usize::MAX {
718        return None;
719    }
720
721    let min_runs = total_rows.checked_div(threshold)?.checked_add(1)?;
722    (min_runs <= total_rows).then_some(min_runs)
723}
724
725/// Builds normalized selectors while their run count remains below
726/// `min_mask_runs`. Returning `None` drops the partial selector allocation
727/// before the caller constructs a mask.
728fn selectors_below_run_limit(
729    filters: &[BooleanArray],
730    total_rows: usize,
731    min_mask_runs: usize,
732) -> Option<Vec<RowSelector>> {
733    let mut selectors = Vec::new();
734    let mut next_offset = 0usize;
735    let mut last_end = 0usize;
736
737    for filter in filters {
738        assert_eq!(filter.null_count(), 0);
739        let offset = next_offset;
740        next_offset = next_offset.checked_add(filter.len()).unwrap();
741
742        for (start, end) in SlicesIterator::new(filter) {
743            let start = start.checked_add(offset).unwrap();
744            let end = end.checked_add(offset).unwrap();
745
746            if start > last_end {
747                append_normalized_selector(&mut selectors, RowSelector::skip(start - last_end));
748                if selectors.len() >= min_mask_runs {
749                    return None;
750                }
751            }
752
753            append_normalized_selector(&mut selectors, RowSelector::select(end - start));
754            if selectors.len() >= min_mask_runs {
755                return None;
756            }
757            last_end = end;
758        }
759    }
760
761    if last_end != total_rows {
762        append_normalized_selector(&mut selectors, RowSelector::skip(total_rows - last_end));
763        if selectors.len() >= min_mask_runs {
764            return None;
765        }
766    }
767
768    Some(selectors)
769}
770
771/// Appends a selector while maintaining the normalized selector invariants.
772fn append_normalized_selector(selectors: &mut Vec<RowSelector>, selector: RowSelector) {
773    if selector.row_count == 0 {
774        return;
775    }
776
777    match selectors.last_mut() {
778        Some(last) if last.skip == selector.skip => {
779            last.row_count = last.row_count.checked_add(selector.row_count).unwrap()
780        }
781        _ => selectors.push(selector),
782    }
783}
784
785fn filters_to_boolean_buffer(filters: &[BooleanArray]) -> BooleanBuffer {
786    let total_rows = filters.iter().map(|filter| filter.len()).sum();
787    let mut builder = BooleanBufferBuilder::new(total_rows);
788    for filter in filters {
789        assert_eq!(filter.null_count(), 0);
790        builder.append_buffer(filter.values());
791    }
792    builder.finish()
793}
794
795impl From<Vec<RowSelector>> for RowSelection {
796    fn from(selectors: Vec<RowSelector>) -> Self {
797        selectors.into_iter().collect()
798    }
799}
800
801impl From<BooleanBuffer> for RowSelection {
802    fn from(mask: BooleanBuffer) -> Self {
803        Self::from_boolean_buffer(mask)
804    }
805}
806
807impl FromIterator<RowSelector> for RowSelection {
808    fn from_iter<T: IntoIterator<Item = RowSelector>>(iter: T) -> Self {
809        let iter = iter.into_iter();
810
811        // Capacity before filter
812        let mut selectors = Vec::with_capacity(iter.size_hint().0);
813
814        let mut filtered = iter.filter(|x| x.row_count != 0);
815        if let Some(x) = filtered.next() {
816            selectors.push(x);
817        }
818
819        for s in filtered {
820            if s.row_count == 0 {
821                continue;
822            }
823
824            // Combine consecutive selectors
825            let last = selectors.last_mut().unwrap();
826            if last.skip == s.skip {
827                last.row_count = last.row_count.checked_add(s.row_count).unwrap();
828            } else {
829                selectors.push(s)
830            }
831        }
832
833        Self::from_selectors(selectors)
834    }
835}
836
837impl From<RowSelection> for Vec<RowSelector> {
838    fn from(r: RowSelection) -> Self {
839        r.into_selectors_vec()
840    }
841}
842
843impl From<RowSelection> for VecDeque<RowSelector> {
844    fn from(r: RowSelection) -> Self {
845        r.into_selectors_vec().into()
846    }
847}
848
849impl FromIterator<RowSelection> for RowSelection {
850    /// Concatenate multiple [`RowSelection`]s in iterator order.
851    ///
852    /// When every input is mask-backed the result stays mask-backed
853    /// (`BooleanBuffer`s are appended); otherwise falls back to flattening
854    /// through the per-`RowSelector` form.
855    fn from_iter<T: IntoIterator<Item = RowSelection>>(iter: T) -> Self {
856        let items: Vec<RowSelection> = iter.into_iter().collect();
857
858        let all_mask = items
859            .iter()
860            .all(|s| matches!(&s.inner, RowSelectionInner::Mask(_)));
861
862        if all_mask {
863            let total_len: usize = items
864                .iter()
865                .map(|s| match &s.inner {
866                    RowSelectionInner::Mask(m) => m.mask().len(),
867                    RowSelectionInner::Selectors(_) => unreachable!(),
868                })
869                .sum();
870            let mut builder = BooleanBufferBuilder::new(total_len);
871            for item in items {
872                match item.into_inner() {
873                    RowSelectionInner::Mask(m) => builder.append_buffer(m.mask()),
874                    RowSelectionInner::Selectors(_) => unreachable!(),
875                }
876            }
877            return Self::from_boolean_buffer(builder.finish());
878        }
879
880        items
881            .into_iter()
882            .flat_map(|s| s.into_selectors_vec())
883            .collect()
884    }
885}
886
887#[cfg(test)]
888mod tests {
889    use super::*;
890    use rand::rngs::StdRng;
891    use rand::{RngExt, SeedableRng};
892
893    const MAX_RANDOM_ROWS: usize = 65_536;
894    const THRESHOLDS: &[usize] = &[0, 1, 8, 16, 31, 32, 33, 64];
895    const SELECTIVITIES: &[usize] = &[0, 1, 5, 15, 50, 90, 99, 100];
896    const FILTER_SHAPES: &[FilterShape] = &[
897        FilterShape::Isolated,
898        FilterShape::Runs,
899        FilterShape::Random,
900        FilterShape::Clustered,
901    ];
902
903    #[derive(Clone, Copy, Debug)]
904    enum FilterShape {
905        Isolated,
906        Runs,
907        Random,
908        Clustered,
909    }
910
911    #[test]
912    fn auto_min_mask_runs_matches_policy_boundaries() {
913        assert_eq!(auto_min_mask_runs(0, 32), None);
914        assert_eq!(auto_min_mask_runs(64, 0), None);
915        assert_eq!(auto_min_mask_runs(64, 1), None);
916        assert_eq!(auto_min_mask_runs(64, 32), Some(3));
917        assert_eq!(auto_min_mask_runs(64, 64), Some(2));
918        assert_eq!(auto_min_mask_runs(64, 65), Some(1));
919        assert_eq!(auto_min_mask_runs(usize::MAX, usize::MAX), None);
920    }
921
922    #[test]
923    fn auto_construction_preserves_global_runs_and_threshold_boundary() {
924        let filters = vec![
925            BooleanArray::from(vec![false, true, true]),
926            BooleanArray::from(Vec::<bool>::new()),
927            BooleanArray::from(vec![true, true, false]),
928            BooleanArray::from(vec![false, false, true]),
929        ];
930
931        for threshold in THRESHOLDS {
932            assert_auto_equivalent(&filters, *threshold, "cross-filter run merge");
933        }
934
935        let run31_filters = split_evenly(&run_mask(65_536, 31, 31), 8_192);
936        let run32_filters = split_evenly(&run_mask(65_536, 32, 32), 8_192);
937
938        assert_eq!(
939            RowSelection::from_filters(&run31_filters).auto_selection_strategy(32),
940            RowSelectionStrategy::Mask
941        );
942        assert_eq!(
943            RowSelection::from_filters(&run32_filters).auto_selection_strategy(32),
944            RowSelectionStrategy::Selectors
945        );
946        assert_auto_equivalent(&run31_filters, 32, "run31 below threshold");
947        assert_auto_equivalent(&run32_filters, 32, "run32 equal to threshold");
948
949        assert_auto_equivalent(&[], 0, "no filters");
950        assert_auto_equivalent(&[BooleanArray::from(Vec::<bool>::new())], 0, "empty filter");
951    }
952
953    #[test]
954    #[cfg_attr(miri, ignore)] // Takes too long
955    fn auto_construction_edge_row_counts() {
956        for rows in [0, 1, 7, 8, 31, 32, 33, MAX_RANDOM_ROWS] {
957            let masks = [
958                ("all skipped", BooleanBuffer::new_unset(rows)),
959                ("all selected", BooleanBuffer::new_set(rows)),
960                (
961                    "alternating",
962                    BooleanBuffer::from_iter((0..rows).map(|row| row % 2 == 0)),
963                ),
964                ("short runs", run_mask(rows, 3, 5)),
965            ];
966
967            for (shape, mask) in masks {
968                let mask = with_bit_offset(mask, 5);
969                let filters = split_evenly(&mask, rows.div_ceil(3).max(1));
970
971                for &threshold in THRESHOLDS {
972                    let context = format!("rows={rows} shape={shape} threshold={threshold}");
973                    assert_auto_equivalent(&filters, threshold, &context);
974                }
975            }
976        }
977    }
978
979    #[test]
980    #[cfg_attr(miri, ignore)] // Takes too long
981    fn auto_construction_randomized_equivalence() {
982        let mut rng = StdRng::seed_from_u64(0x1077_6000_5eed);
983        let mut case_idx = 0usize;
984
985        for &threshold in THRESHOLDS {
986            for &selectivity in SELECTIVITIES {
987                for &shape in FILTER_SHAPES {
988                    for with_offset in [false, true] {
989                        let rows = rng.random_range(0..=MAX_RANDOM_ROWS);
990                        let mask = random_shape(&mut rng, rows, selectivity, shape);
991                        let bit_offset = if with_offset {
992                            rng.random_range(1..=63)
993                        } else {
994                            0
995                        };
996                        let mask = with_bit_offset(mask, bit_offset);
997                        let filter_count = rng.random_range(1..=32);
998                        let filters = random_split(&mut rng, &mask, filter_count);
999                        let context = format!(
1000                            "case={case_idx} rows={rows} selectivity={selectivity} shape={shape:?} \
1001                             filters={filter_count} threshold={threshold} bit_offset={bit_offset}"
1002                        );
1003
1004                        assert_auto_equivalent(&filters, threshold, &context);
1005                        case_idx += 1;
1006                    }
1007                }
1008            }
1009        }
1010    }
1011
1012    fn assert_auto_equivalent(filters: &[BooleanArray], threshold: usize, context: &str) {
1013        let reference = RowSelection::from_filters(filters);
1014        let reference_strategy = reference.auto_selection_strategy(threshold);
1015        let auto_built = RowSelection::from_filters_auto(filters, threshold);
1016        let auto_built_strategy = auto_built.auto_selection_strategy(threshold);
1017        let auto_built_backing = match &auto_built.inner {
1018            RowSelectionInner::Mask(_) => RowSelectionStrategy::Mask,
1019            RowSelectionInner::Selectors(_) => RowSelectionStrategy::Selectors,
1020        };
1021
1022        assert_eq!(reference_strategy, auto_built_backing, "backing: {context}");
1023        assert_eq!(
1024            reference_strategy, auto_built_strategy,
1025            "strategy: {context}"
1026        );
1027        assert_eq!(reference, auto_built, "logical selection: {context}");
1028    }
1029
1030    fn run_mask(rows: usize, selected_run: usize, skipped_run: usize) -> BooleanBuffer {
1031        let period = selected_run + skipped_run;
1032        BooleanBuffer::from_iter((0..rows).map(|row| row % period < selected_run))
1033    }
1034
1035    fn split_evenly(mask: &BooleanBuffer, batch_size: usize) -> Vec<BooleanArray> {
1036        (0..mask.len())
1037            .step_by(batch_size)
1038            .map(|offset| {
1039                let len = batch_size.min(mask.len() - offset);
1040                BooleanArray::new(mask.slice(offset, len), None)
1041            })
1042            .collect()
1043    }
1044
1045    fn random_shape(
1046        rng: &mut StdRng,
1047        rows: usize,
1048        selectivity: usize,
1049        shape: FilterShape,
1050    ) -> BooleanBuffer {
1051        if selectivity == 0 {
1052            return BooleanBuffer::new_unset(rows);
1053        }
1054        if selectivity == 100 {
1055            return BooleanBuffer::new_set(rows);
1056        }
1057
1058        match shape {
1059            FilterShape::Isolated => isolated_mask(rows, selectivity),
1060            FilterShape::Runs => {
1061                let scale = rng.random_range(1..=8);
1062                run_mask(rows, selectivity * scale, (100 - selectivity) * scale)
1063            }
1064            FilterShape::Random => BooleanBuffer::from_iter(
1065                (0..rows).map(|_| rng.random_bool(selectivity as f64 / 100.0)),
1066            ),
1067            FilterShape::Clustered => one_cluster_mask(rng, rows, selectivity),
1068        }
1069    }
1070
1071    fn isolated_mask(rows: usize, selectivity: usize) -> BooleanBuffer {
1072        if selectivity <= 50 {
1073            let period = 100usize.div_ceil(selectivity).max(2);
1074            BooleanBuffer::from_iter((0..rows).map(|row| row % period == 0))
1075        } else {
1076            let period = 100usize.div_ceil(100 - selectivity).max(2);
1077            BooleanBuffer::from_iter((0..rows).map(|row| row % period != 0))
1078        }
1079    }
1080
1081    fn one_cluster_mask(rng: &mut StdRng, rows: usize, selectivity: usize) -> BooleanBuffer {
1082        let selected = rows.saturating_mul(selectivity) / 100;
1083        let start = rng.random_range(0..=rows - selected);
1084        let mut builder = BooleanBufferBuilder::new(rows);
1085        builder.append_n(start, false);
1086        builder.append_n(selected, true);
1087        builder.append_n(rows - start - selected, false);
1088        builder.finish()
1089    }
1090
1091    fn with_bit_offset(mask: BooleanBuffer, offset: usize) -> BooleanBuffer {
1092        if offset == 0 {
1093            return mask;
1094        }
1095
1096        let len = mask.len();
1097        let mut builder = BooleanBufferBuilder::new(offset + len);
1098        builder.append_n(offset, false);
1099        builder.append_buffer(&mask);
1100        builder.finish().slice(offset, len)
1101    }
1102
1103    fn random_split(
1104        rng: &mut StdRng,
1105        mask: &BooleanBuffer,
1106        filter_count: usize,
1107    ) -> Vec<BooleanArray> {
1108        let mut filters = Vec::with_capacity(filter_count);
1109        let mut offset = 0usize;
1110
1111        for index in 0..filter_count {
1112            let remaining = mask.len() - offset;
1113            let len = if index + 1 == filter_count {
1114                remaining
1115            } else {
1116                rng.random_range(0..=remaining)
1117            };
1118            filters.push(BooleanArray::new(mask.slice(offset, len), None));
1119            offset += len;
1120        }
1121
1122        filters
1123    }
1124
1125    #[test]
1126    fn test_total_row_count() {
1127        let selection = RowSelection::from(vec![RowSelector::skip(5), RowSelector::select(3)]);
1128        assert_eq!(selection.total_row_count(), 8);
1129        assert_eq!(selection.row_count(), 3);
1130        assert_eq!(selection.skipped_row_count(), 5);
1131
1132        let selection =
1133            RowSelection::from_boolean_buffer(BooleanBuffer::from(vec![true, false, true]));
1134        assert_eq!(selection.total_row_count(), 3);
1135        assert_eq!(selection.row_count(), 2);
1136        assert_eq!(selection.skipped_row_count(), 1);
1137
1138        let empty = RowSelection::from(vec![]);
1139        assert_eq!(empty.total_row_count(), 0);
1140    }
1141
1142    #[test]
1143    fn test_offset_zero_and_zero_batch_expand_are_identity() {
1144        let selection =
1145            RowSelection::from_boolean_buffer(BooleanBuffer::from(vec![true, false, true]));
1146        assert_eq!(selection.clone().offset(0), selection);
1147        assert_eq!(selection.expand_to_batch_boundaries(0, 3), selection);
1148    }
1149
1150    #[test]
1151    fn test_from_filters() {
1152        let filters = vec![
1153            BooleanArray::from(vec![false, false, false, true, true, true, true]),
1154            BooleanArray::from(vec![true, true, false, false, true, true, true]),
1155            BooleanArray::from(vec![false, false, false, false]),
1156            BooleanArray::from(Vec::<bool>::new()),
1157        ];
1158
1159        let selection = RowSelection::from_filters(&filters[..1]);
1160        assert!(selection.selects_any());
1161        assert_eq!(
1162            selection.selectors(),
1163            vec![RowSelector::skip(3), RowSelector::select(4)]
1164        );
1165
1166        let selection = RowSelection::from_filters(&filters[..2]);
1167        assert!(selection.selects_any());
1168        assert_eq!(
1169            selection.selectors(),
1170            vec![
1171                RowSelector::skip(3),
1172                RowSelector::select(6),
1173                RowSelector::skip(2),
1174                RowSelector::select(3)
1175            ]
1176        );
1177
1178        let selection = RowSelection::from_filters(&filters);
1179        assert!(selection.selects_any());
1180        assert_eq!(
1181            selection.selectors(),
1182            vec![
1183                RowSelector::skip(3),
1184                RowSelector::select(6),
1185                RowSelector::skip(2),
1186                RowSelector::select(3),
1187                RowSelector::skip(4)
1188            ]
1189        );
1190
1191        let selection = RowSelection::from_filters(&filters[2..3]);
1192        assert!(!selection.selects_any());
1193        assert_eq!(selection.selectors(), vec![RowSelector::skip(4)]);
1194    }
1195
1196    #[test]
1197    fn test_iter() {
1198        // use the iter() API to show it does what is expected and
1199        // avoid accidental deletion
1200        let selectors = vec![
1201            RowSelector::select(3),
1202            RowSelector::skip(33),
1203            RowSelector::select(4),
1204        ];
1205
1206        let round_tripped: Vec<RowSelector> = RowSelection::from(selectors.clone())
1207            .iter()
1208            .copied()
1209            .collect();
1210        assert_eq!(selectors, round_tripped);
1211    }
1212
1213    #[test]
1214    fn test_row_count() {
1215        let selection = RowSelection::from(vec![
1216            RowSelector::skip(34),
1217            RowSelector::select(12),
1218            RowSelector::skip(3),
1219            RowSelector::select(35),
1220        ]);
1221
1222        assert_eq!(selection.row_count(), 12 + 35);
1223        assert_eq!(selection.skipped_row_count(), 34 + 3);
1224
1225        let selection = RowSelection::from(vec![RowSelector::select(12), RowSelector::select(35)]);
1226
1227        assert_eq!(selection.row_count(), 12 + 35);
1228        assert_eq!(selection.skipped_row_count(), 0);
1229
1230        let selection = RowSelection::from(vec![RowSelector::skip(34), RowSelector::skip(3)]);
1231
1232        assert_eq!(selection.row_count(), 0);
1233        assert_eq!(selection.skipped_row_count(), 34 + 3);
1234
1235        let selection = RowSelection::from(vec![]);
1236
1237        assert_eq!(selection.row_count(), 0);
1238        assert_eq!(selection.skipped_row_count(), 0);
1239    }
1240
1241    #[test]
1242    fn test_mixed_backing_equality_mismatches() {
1243        let mask =
1244            RowSelection::from_boolean_buffer(BooleanBuffer::from(vec![true, false, true, true]));
1245
1246        // Total row counts differ
1247        let longer = RowSelection::from(vec![
1248            RowSelector::select(1),
1249            RowSelector::skip(1),
1250            RowSelector::select(2),
1251            RowSelector::skip(1),
1252        ]);
1253        assert_ne!(mask, longer);
1254        assert_ne!(longer, mask);
1255
1256        // A selected bit falls inside a skip run
1257        let skip_overlap = RowSelection::from(vec![RowSelector::skip(2), RowSelector::select(2)]);
1258        assert_ne!(mask, skip_overlap);
1259
1260        // Select run boundaries do not line up
1261        let misaligned = RowSelection::from(vec![
1262            RowSelector::select(2),
1263            RowSelector::skip(1),
1264            RowSelector::select(1),
1265        ]);
1266        assert_ne!(mask, misaligned);
1267
1268        let equal = RowSelection::from(vec![
1269            RowSelector::select(1),
1270            RowSelector::skip(1),
1271            RowSelector::select(2),
1272        ]);
1273        assert_eq!(mask, equal);
1274        assert_eq!(equal, mask);
1275    }
1276
1277    #[test]
1278    fn test_from_iter_all_mask_preserves_mask_backing() {
1279        let a_bits = vec![true, false, true, true];
1280        let b_bits = vec![false, true, false];
1281        let c_bits = vec![true, true, false, false, true];
1282
1283        let parts = vec![
1284            RowSelection::from_boolean_buffer(BooleanBuffer::from(a_bits.clone())),
1285            RowSelection::from_boolean_buffer(BooleanBuffer::from(b_bits.clone())),
1286            RowSelection::from_boolean_buffer(BooleanBuffer::from(c_bits.clone())),
1287        ];
1288        let collected: RowSelection = parts.into_iter().collect();
1289
1290        let combined = a_bits
1291            .iter()
1292            .chain(b_bits.iter())
1293            .chain(c_bits.iter())
1294            .copied()
1295            .collect::<Vec<_>>();
1296        let expected = RowSelection::from_filters(&[BooleanArray::from(combined)]);
1297
1298        assert!(collected.as_mask().is_some());
1299        assert_eq!(collected, expected);
1300    }
1301
1302    #[test]
1303    fn test_from_iter_mixed_backing_falls_back_to_selectors() {
1304        let a_bits = vec![true, false, true];
1305        let b_selectors = vec![RowSelector::skip(2), RowSelector::select(3)];
1306        let c_bits = vec![false, true];
1307
1308        let parts = vec![
1309            RowSelection::from_boolean_buffer(BooleanBuffer::from(a_bits.clone())),
1310            RowSelection::from(b_selectors),
1311            RowSelection::from_boolean_buffer(BooleanBuffer::from(c_bits.clone())),
1312        ];
1313        let collected: RowSelection = parts.into_iter().collect();
1314
1315        assert!(collected.as_mask().is_none());
1316
1317        let combined_bits = vec![
1318            true, false, true, false, false, true, true, true, false, true,
1319        ];
1320        let expected = RowSelection::from_filters(&[BooleanArray::from(combined_bits)]);
1321        assert_eq!(collected, expected);
1322    }
1323
1324    #[test]
1325    fn test_from_iter_empty_yields_empty_selection() {
1326        let collected: RowSelection = std::iter::empty::<RowSelection>().collect();
1327        assert_eq!(collected, RowSelection::default());
1328        assert!(collected.as_mask().is_some());
1329        assert_eq!(collected.as_mask().unwrap().len(), 0);
1330    }
1331}
parquet/arrow/arrow_reader/selection/mod.rs

parquet/arrow/arrow_reader/selection/
mod.rs
