Skip to main content

parquet/arrow/push_decoder/scan_plan/
mod.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
5//! [`ScanPlan`]: the byte ranges that a push decoder may still read.
6
7use std::cmp::Reverse;
8use std::collections::BinaryHeap;
9use std::iter::FusedIterator;
10use std::ops::Range;
11use std::sync::Arc;
12
13use super::reader_builder::StageSchedule;
14use crate::arrow::arrow_reader::{ReadPlanBuilder, RowSelection};
15use crate::arrow::in_memory_row_group::{
16    ColumnFetch, column_selection, columns_to_fetch, dictionary_range, page_range,
17};
18use crate::errors::ParquetError;
19use crate::file::metadata::ParquetMetaData;
20use crate::file::metadata::page_index::PageIndexProvider;
21use crate::file::page_index::offset_index::PageLocation;
22
23mod budget;
24mod frontier;
25
26pub(crate) use budget::{BudgetedReadPlan, RowBudget};
27pub(crate) use frontier::{NextRowGroup, RowGroupFrontier};
28
29/// One item of a [`ScanPlan`].
30///
31/// Two items are equal if their public fields are equal.
32#[derive(Debug, Clone)]
33#[non_exhaustive]
34pub struct PlannedRange {
35    /// Byte range in the file.
36    pub range: Range<u64>,
37    /// Row group index in the file.
38    pub row_group: usize,
39    /// Leaf column index in the file.
40    pub column: usize,
41    /// What the range contains.
42    pub kind: PageKind,
43    /// First planned row that this range serves, counted from the start of
44    /// the plan. The tests use it to check the order of the plan.
45    #[cfg_attr(not(test), expect(dead_code))]
46    pub(crate) first_row: u64,
47    /// One past the last planned row that this range serves.
48    #[cfg_attr(not(test), expect(dead_code))]
49    pub(crate) last_row: u64,
50}
51
52/// Compares the public fields only. `first_row` and `last_row` count from
53/// the start of a plan, so they differ between two plans of the same decoder.
54impl PartialEq for PlannedRange {
55    fn eq(&self, other: &Self) -> bool {
56        let Self {
57            range,
58            row_group,
59            column,
60            kind,
61            first_row: _,
62            last_row: _,
63        } = self;
64        *range == other.range
65            && *row_group == other.row_group
66            && *column == other.column
67            && *kind == other.kind
68    }
69}
70
71impl Eq for PlannedRange {}
72
73impl PlannedRange {
74    /// Number of bytes in this range.
75    pub fn len(&self) -> u64 {
76        self.range.end - self.range.start
77    }
78
79    /// Returns `true` if this range contains no bytes.
80    pub fn is_empty(&self) -> bool {
81        self.range.is_empty()
82    }
83}
84
85/// What a [`PlannedRange`] contains.
86#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
87#[non_exhaustive]
88pub enum PageKind {
89    /// The dictionary page of a column chunk.
90    Dictionary,
91    /// One data page.
92    Data,
93    /// A complete column chunk. The plan uses this when the column has no
94    /// offset index, so page locations are unknown.
95    ColumnChunk,
96}
97
98/// A decoding stage of a row group.
99///
100/// The decoder reads a column once per row group. A column that a predicate
101/// reads is not read again for the output.
102pub(crate) use super::reader_builder::Stage as ScanStage;
103
104/// The byte ranges that a push decoder may still read, in the order that
105/// decoding needs them.
106///
107/// Created by [`ParquetPushDecoder::scan_plan`]. Use it to fetch data before
108/// the decoder asks for it.
109///
110/// A `ScanPlan` is an estimate of the ranges that the decoder may need. The
111/// ranges in [`DecodeResult::NeedsData`] from
112/// [`ParquetPushDecoder::try_decode`] are the ranges that it actually needs.
113///
114/// * The plan covers every byte that the decoder can request after the
115///   plan is made. It can cover more, for example ranges that a
116///   [`RowFilter`] makes unnecessary. One request can span more than one
117///   planned range: without a row selection, the decoder requests a complete
118///   column chunk, and the plan lists the pages of the column chunk.
119/// * The ranges are generated on demand, as you iterate. The plan does not
120///   calculate a range until you ask for it.
121/// * The plan comes from the current state of the decoder. To plan the
122///   whole scan, call [`ParquetPushDecoder::scan_plan`] once after
123///   [`ParquetPushDecoderBuilder::build`] and keep the iterator. If you
124///   rebuild the decoder with [`ParquetPushDecoder::into_builder`], the old
125///   plan is not valid for the new decoder. Call `scan_plan` again on the new
126///   decoder.
127/// * Row groups are in read order. In a row group, the columns of the
128///   [`RowFilter`] predicates come first, then the other output columns. The
129///   ranges are ordered by the first row that they serve, and the ranges of
130///   one column chunk stay in file order.
131/// * There is one range for each page if the column has an offset index,
132///   and one range for the entire column chunk if not.
133/// * The plan does not change decoding, does no I/O and does not depend
134///   on pushed data.
135/// * Without a row selection, the state of the plan does not grow with the
136///   number of pages. With a row selection, the plan keeps the indexes of
137///   the selected pages of each column chunk in the current decoding stage
138///   of the current row group.
139/// * If the decoder will return an error for a row group, the plan ends
140///   before that row group. An example is a row selection with more rows
141///   than the row group.
142///
143/// Keep the fetched ranges in your own cache, and answer each `NeedsData`
144/// with exactly the requested ranges. See [`ParquetPushDecoder::push_ranges`].
145///
146/// # Example
147///
148/// ```
149/// # use std::collections::BTreeMap;
150/// # use std::ops::Range;
151/// # use bytes::Bytes;
152/// # use arrow_array::record_batch;
153/// # use parquet::DecodeResult;
154/// # use parquet::arrow::ArrowWriter;
155/// # use parquet::arrow::arrow_reader::{ArrowReaderMetadata, ArrowReaderOptions};
156/// # use parquet::arrow::push_decoder::ParquetPushDecoderBuilder;
157/// # use parquet::file::metadata::PageIndexPolicy;
158/// # use parquet::file::properties::WriterProperties;
159/// # let file = {
160/// #   let mut buffer = vec![];
161/// #   let batch = record_batch!(("a", Int32, [1, 2, 3, 4])).unwrap();
162/// #   let props = WriterProperties::builder().set_max_row_group_row_count(Some(2)).build();
163/// #   let mut writer = ArrowWriter::try_new(&mut buffer, batch.schema(), Some(props)).unwrap();
164/// #   writer.write(&batch).unwrap();
165/// #   writer.close().unwrap();
166/// #   Bytes::from(buffer)
167/// # };
168/// # let fetch = |range: &Range<u64>| file.slice(range.start as usize..range.end as usize);
169/// # // Join cached ranges that cover `range`, or fetch it.
170/// # let read = |cache: &BTreeMap<u64, Bytes>, range: &Range<u64>| {
171/// #     let mut data = Vec::new();
172/// #     let mut position = range.start;
173/// #     while position < range.end {
174/// #         let Some((start, bytes)) = cache.range(..=position).next_back() else {
175/// #             return fetch(range);
176/// #         };
177/// #         let end = (start + bytes.len() as u64).min(range.end);
178/// #         if end <= position {
179/// #             return fetch(range);
180/// #         }
181/// #         data.extend_from_slice(&bytes[(position - start) as usize..(end - start) as usize]);
182/// #         position = end;
183/// #     }
184/// #     Bytes::from(data)
185/// # };
186/// # let options = ArrowReaderOptions::new().with_page_index_policy(PageIndexPolicy::Optional);
187/// # let metadata = ArrowReaderMetadata::load(&file, options).unwrap();
188/// let mut decoder = ParquetPushDecoderBuilder::new_with_metadata(metadata)
189///     .build()
190///     .unwrap();
191///
192/// // Read ahead up to 1 MB into a cache
193/// let mut cache = BTreeMap::new();
194/// let mut cached = 0;
195/// for planned in decoder.scan_plan() {
196///     if cached + planned.len() > 1024 * 1024 {
197///         break;
198///     }
199///     cached += planned.len();
200///     cache.insert(planned.range.start, fetch(&planned.range));
201/// }
202///
203/// // Answer each request from the cache
204/// loop {
205///     match decoder.try_decode().unwrap() {
206///         DecodeResult::NeedsData(ranges) => {
207///             // `read` takes the data from the cache. If a range is not in
208///             // the cache, it fetches it here.
209///             let data = ranges.iter().map(|range| read(&cache, range)).collect();
210///             decoder.push_ranges(ranges, data).unwrap();
211///         }
212///         DecodeResult::Data(batch) => println!("{} rows", batch.num_rows()),
213///         DecodeResult::Finished => break,
214///     }
215/// }
216/// ```
217///
218/// [`RowFilter`]: crate::arrow::arrow_reader::RowFilter
219/// [`DecodeResult::NeedsData`]: crate::DecodeResult::NeedsData
220/// [`ParquetPushDecoder::scan_plan`]: super::ParquetPushDecoder::scan_plan
221/// [`ParquetPushDecoder::into_builder`]: super::ParquetPushDecoder::into_builder
222/// [`ParquetPushDecoder::try_decode`]: super::ParquetPushDecoder::try_decode
223/// [`ParquetPushDecoder::push_ranges`]: super::ParquetPushDecoder::push_ranges
224/// [`ParquetPushDecoderBuilder::build`]: super::ParquetPushDecoderBuilder::build
225#[derive(Debug, Clone)]
226pub struct ScanPlan {
227    /// `None` for an empty plan, for example of a finished decoder.
228    planner: Option<Box<Planner>>,
229}
230
231impl ScanPlan {
232    /// A plan with no ranges.
233    pub(crate) fn empty() -> Self {
234        Self { planner: None }
235    }
236}
237
238/// The state of a [`ScanPlan`] that is not empty.
239#[derive(Debug, Clone)]
240struct Planner {
241    /// The decoder's row-group queue, selections and offset/limit budget, as
242    /// they were when the plan was made.
243    frontier: RowGroupFrontier,
244    /// The row group that the decoder was fetching when the plan was made.
245    /// It is planned first.
246    active_row_group: Option<NextRowGroup>,
247    /// The decoder's projection, predicates and batch size.
248    columns: Arc<StageColumns>,
249    /// Planned rows before the next row group.
250    next_row: u64,
251    /// The row group being planned, if any.
252    current: Option<RowGroupRanges>,
253    /// Whether planning has ended.
254    done: bool,
255}
256
257/// The decoder's batch size and decoding stages.
258#[derive(Debug)]
259struct StageColumns {
260    /// The output batch size, which aligns cached predicate reads.
261    batch_size: usize,
262    /// What each decoding stage fetches, shared with the decoder.
263    stages: Arc<StageSchedule>,
264}
265
266/// Builds a [`ScanPlan`] from a decoder's row-group frontier and the columns
267/// each decoding stage reads.
268#[derive(Debug)]
269pub(crate) struct ScanPlanBuilder {
270    frontier: RowGroupFrontier,
271    active_row_group: Option<NextRowGroup>,
272    columns: StageColumns,
273}
274
275impl ScanPlanBuilder {
276    /// Plan the row groups in `frontier`, decoding in batches of
277    /// `batch_size` rows with the decoding stages `stages`.
278    pub(crate) fn new(
279        frontier: RowGroupFrontier,
280        batch_size: usize,
281        stages: Arc<StageSchedule>,
282    ) -> Self {
283        Self {
284            frontier,
285            active_row_group: None,
286            columns: StageColumns { batch_size, stages },
287        }
288    }
289
290    /// Plan `active_row_group` first: the row group that the decoder is
291    /// fetching, which the frontier has already handed over.
292    pub(crate) fn with_active_row_group(mut self, active_row_group: Option<NextRowGroup>) -> Self {
293        self.active_row_group = active_row_group;
294        self
295    }
296
297    pub(crate) fn build(self) -> ScanPlan {
298        let Self {
299            frontier,
300            active_row_group,
301            columns,
302        } = self;
303        let planner = Planner {
304            frontier,
305            active_row_group,
306            columns: Arc::new(columns),
307            next_row: 0,
308            current: None,
309            done: false,
310        };
311        ScanPlan {
312            planner: Some(Box::new(planner)),
313        }
314    }
315}
316
317impl Planner {
318    /// Start planning the next row group the decoder will read.
319    ///
320    /// Returns `Ok(false)` when no row group remains. A row group that the
321    /// offset/limit budget removes is planned with no ranges.
322    fn plan_next_row_group(&mut self) -> Result<bool, ParquetError> {
323        // Use the decoder's own row-group walk, so row groups that the
324        // selection or the budget removes are skipped here too.
325        let next_row_group = match self.active_row_group.take() {
326            Some(active) => Some(active),
327            None => self.frontier.next_readable_row_group()?,
328        };
329        let Some(NextRowGroup {
330            row_group_idx,
331            row_count,
332            selection,
333            budget,
334        }) = next_row_group
335        else {
336            return Ok(false);
337        };
338
339        let filtered = self.frontier.has_predicates;
340        let selection = if filtered {
341            // Predicates see every selected row. Offset and limit apply to
342            // their output, so they cannot be applied before decoding.
343            selection
344        } else {
345            // Apply offset and limit as the decoder does before it requests
346            // the output columns.
347            let plan_builder =
348                ReadPlanBuilder::new(self.columns.batch_size).with_selection(selection);
349            let BudgetedReadPlan {
350                plan_builder,
351                rows_after_budget,
352                remaining_budget,
353                ..
354            } = budget.apply_to_plan(plan_builder, row_count);
355            self.frontier
356                .update_budget_after_row_group(remaining_budget);
357            if rows_after_budget == 0 {
358                self.current = None;
359                return Ok(true);
360            }
361            plan_builder.selection().cloned()
362        };
363
364        let rows = SelectedRows::new(selection.as_ref(), row_count);
365        let first_row = self.next_row;
366        self.next_row += rows.selected_before(row_count);
367
368        let metadata = &self.frontier.parquet_metadata;
369        let page_index = metadata
370            .page_index()
371            .filter(|page_index| page_index.has_offset_indexes())
372            .cloned();
373        let row_group = metadata.row_group(row_group_idx);
374
375        // Predicate columns that are cached for the output are fetched with the
376        // selection expanded to batch boundaries. See `fetch_ranges`.
377        let stages = &self.columns.stages;
378        let expanded_selection = match (&selection, stages.cache_projection()) {
379            (Some(selection), Some(_)) => {
380                Some(selection.expand_to_batch_boundaries(self.columns.batch_size, row_count))
381            }
382            _ => None,
383        };
384
385        let num_columns = row_group.columns().len();
386        let mut planned_columns = vec![false; num_columns];
387        let mut stage_plans = vec![];
388        for (stage, fetch) in stages.stages() {
389            // The decoder reuses a column that an earlier stage read.
390            // `columns_to_fetch` filters, so it gives no size hint. Reserve
391            // for every column to avoid growing the vector one column at a time.
392            let mut columns = Vec::with_capacity(num_columns);
393            columns.extend(columns_to_fetch(fetch.projection, num_columns, |idx| {
394                planned_columns[idx]
395            }));
396            // The plan keeps `columns` until the end of the row group. Release
397            // the capacity that a narrow projection does not use.
398            columns.shrink_to_fit();
399            for &column_idx in &columns {
400                planned_columns[column_idx] = true;
401            }
402            stage_plans.push(StagePlan { stage, columns });
403        }
404
405        self.current = Some(RowGroupRanges {
406            row_group: RowGroupContext {
407                row_group_idx,
408                row_count,
409                first_row,
410                rows,
411                selection,
412                expanded_selection,
413                stages: Arc::clone(&self.columns.stages),
414                metadata: Arc::clone(metadata),
415                page_index,
416            },
417            stages: stage_plans.into_iter(),
418            stage: None,
419        });
420        Ok(true)
421    }
422}
423
424impl Iterator for ScanPlan {
425    type Item = PlannedRange;
426
427    fn next(&mut self) -> Option<PlannedRange> {
428        self.planner.as_mut()?.next()
429    }
430}
431
432impl Planner {
433    fn next(&mut self) -> Option<PlannedRange> {
434        loop {
435            if let Some(range) = self.current.as_mut().and_then(RowGroupRanges::next) {
436                return Some(range);
437            }
438            if self.done {
439                return None;
440            }
441            match self.plan_next_row_group() {
442                Ok(true) => {}
443                // The decoder reports the same error when it reaches this row
444                // group. The plan is advisory, so it ends here.
445                Ok(false) | Err(_) => {
446                    self.current = None;
447                    self.done = true;
448                }
449            }
450        }
451    }
452}
453
454/// Once [`ScanPlan::next`] returns `None`, it always returns `None`.
455impl FusedIterator for ScanPlan {}
456
457/// The columns that one decoding stage of a row group reads first.
458#[derive(Debug, Clone)]
459struct StagePlan {
460    stage: ScanStage,
461    /// Leaf column indexes, in file order.
462    columns: Vec<usize>,
463}
464
465/// The planned ranges of one row group, in decode order.
466///
467/// Each stage is a merge of one cursor per column chunk. A cursor
468/// returns the ranges of its column chunk in file order, and their first
469/// rows do not decrease. A heap picks the cursor whose next range has the
470/// smallest [`RangeOrder`], so the ranges of a stage are ordered by first
471/// row without collecting and sorting all of them.
472#[derive(Debug, Clone)]
473struct RowGroupRanges {
474    row_group: RowGroupContext,
475    /// Stages not yet started.
476    stages: std::vec::IntoIter<StagePlan>,
477    /// The stage being merged.
478    stage: Option<StageRanges>,
479}
480
481/// What the ranges of one row group are computed from.
482#[derive(Debug, Clone)]
483struct RowGroupContext {
484    row_group_idx: usize,
485    row_count: usize,
486    /// Planned rows before this row group.
487    first_row: u64,
488    rows: SelectedRows,
489    /// The selection the decoder uses to choose pages.
490    selection: Option<RowSelection>,
491    /// The selection expanded to batch boundaries, for cached predicate
492    /// columns.
493    expanded_selection: Option<RowSelection>,
494    /// What each decoding stage fetches.
495    stages: Arc<StageSchedule>,
496    /// The file metadata, for the byte ranges of the column chunks.
497    metadata: Arc<ParquetMetaData>,
498    /// The file's page index, if it has offset indexes.
499    page_index: Option<Arc<dyn PageIndexProvider>>,
500}
501
502/// The merge state of one stage.
503///
504/// A cursor of a column chunk is one heap entry: the sort key of its next
505/// range, the column and the position of that range. The other parts of the
506/// range are computed again when the entry is popped. Thus a stage stores
507/// no per-column state other than its heap entry, unless the selection
508/// removes pages.
509#[derive(Debug, Clone)]
510struct StageRanges {
511    /// Leaf column indexes, in file order. A [`HeapEntry`] refers to a
512    /// column by its position in this list.
513    columns: Vec<usize>,
514    /// For each column in `columns`, the indexes of the data pages that the
515    /// decoder reads, if the selection removes pages. `None` if no column of
516    /// the stage has such a list.
517    selected: Option<Vec<Option<Vec<usize>>>>,
518    /// The next range of each cursor that has one, smallest first.
519    heap: BinaryHeap<Reverse<HeapEntry>>,
520}
521
522/// How the heap orders the next ranges of different column chunks: by first
523/// row, then more rows first (a dictionary page), then by file offset. The
524/// ranges of one column chunk keep file order, also a page with no planned
525/// rows that the predicate cache reads.
526///
527/// The key is `(first row, Reverse(last row), range start)`.
528type RangeOrder = (u64, Reverse<u64>, u64);
529
530/// A heap entry: the sort key of the next range of a cursor, the position
531/// of the column in [`StageRanges::columns`], and the [`HeadPosition`] of
532/// that range. The column position breaks ties, so ranges with equal keys
533/// stay in file order of their columns.
534type HeapEntry = (RangeOrder, u32, HeadPosition);
535
536/// Which range of a column chunk is next: [`CHUNK`], [`DICTIONARY`], or the
537/// position of a data page in the pages that the decoder reads.
538type HeadPosition = u32;
539
540/// The next range is the whole column chunk. The column has no offset index.
541const CHUNK: HeadPosition = u32::MAX;
542
543/// The next range is the dictionary page.
544const DICTIONARY: HeadPosition = u32::MAX - 1;
545
546/// Converts a column or page position to a heap entry field.
547fn position(position: usize) -> u32 {
548    u32::try_from(position).expect("fewer than u32::MAX - 1 columns and pages")
549}
550
551/// The data pages of a column chunk that the decoder reads, in page order.
552#[derive(Debug, Clone, Copy)]
553enum PageSet<'a> {
554    /// Every page of the offset index, which has this many pages.
555    All(usize),
556    /// The pages at these indexes in the offset index.
557    Selected(&'a [usize]),
558}
559
560impl PageSet<'_> {
561    fn len(&self) -> usize {
562        match self {
563            Self::All(len) => *len,
564            Self::Selected(pages) => pages.len(),
565        }
566    }
567
568    /// Index in the offset index of the page at `position`.
569    fn page(&self, position: usize) -> usize {
570        match self {
571            Self::All(_) => position,
572            Self::Selected(pages) => pages[position],
573        }
574    }
575}
576
577impl StageRanges {
578    /// The data pages that the decoder reads of the column at `slot`, whose
579    /// page locations are `locations`.
580    fn pages(&self, slot: usize, locations: &[PageLocation]) -> PageSet<'_> {
581        match self
582            .selected
583            .as_ref()
584            .and_then(|selected| selected[slot].as_ref())
585        {
586            Some(pages) => PageSet::Selected(pages),
587            None => PageSet::All(locations.len()),
588        }
589    }
590}
591
592impl RowGroupRanges {
593    fn next(&mut self) -> Option<PlannedRange> {
594        loop {
595            if let Some(stage) = self.stage.as_mut()
596                && let Some(Reverse(((first_row, Reverse(last_row), start), slot, head))) =
597                    stage.heap.pop()
598            {
599                let row_group = &self.row_group;
600                let column_idx = stage.columns[slot as usize];
601                let (end, kind) = if head == CHUNK {
602                    (row_group.chunk(column_idx).end, PageKind::ColumnChunk)
603                } else {
604                    let locations = row_group
605                        .locations(column_idx)
606                        .expect("pages have locations");
607                    let pages = stage.pages(slot as usize, locations);
608                    let (end, kind, next) = if head == DICTIONARY {
609                        (locations[0].offset as u64, PageKind::Dictionary, 0)
610                    } else {
611                        let page = page_range(&locations[pages.page(head as usize)]);
612                        (page.end, PageKind::Data, head as usize + 1)
613                    };
614                    if let Some(order) = row_group.data_page(locations, pages, next) {
615                        stage.heap.push(Reverse((order, slot, position(next))));
616                    }
617                    (end, kind)
618                };
619                return Some(PlannedRange {
620                    range: start..end,
621                    row_group: row_group.row_group_idx,
622                    column: column_idx,
623                    kind,
624                    first_row,
625                    last_row,
626                });
627            }
628            let plan = self.stages.next()?;
629            let mut selected = None;
630            let mut heap = Vec::with_capacity(plan.columns.len());
631            for (slot, &column_idx) in plan.columns.iter().enumerate() {
632                let (head, pages) = self.row_group.first_range(column_idx, plan.stage);
633                if let Some(pages) = pages {
634                    selected.get_or_insert_with(|| vec![None; plan.columns.len()])[slot] =
635                        Some(pages);
636                }
637                if let Some((order, head)) = head {
638                    heap.push(Reverse((order, position(slot), head)));
639                }
640            }
641            self.stage = Some(StageRanges {
642                columns: plan.columns,
643                selected,
644                heap: BinaryHeap::from(heap),
645            });
646        }
647    }
648}
649
650impl RowGroupContext {
651    fn locations(&self, column_idx: usize) -> Option<&[PageLocation]> {
652        self.page_index
653            .as_ref()?
654            .offset_index(self.row_group_idx, column_idx)
655            .map(|offset_index| offset_index.page_locations().as_slice())
656    }
657
658    /// Byte range of the whole column chunk.
659    fn chunk(&self, column_idx: usize) -> Range<u64> {
660        let (start, len) = self
661            .metadata
662            .row_group(self.row_group_idx)
663            .column(column_idx)
664            .byte_range();
665        start..start + len
666    }
667
668    /// Planned rows of the whole row group.
669    fn row_group_rows(&self) -> Range<u64> {
670        self.first_row..self.first_row + self.rows.selected_before(self.row_count)
671    }
672
673    /// Planned rows of the data page at `idx` in `locations`.
674    fn page_rows(&self, locations: &[PageLocation], idx: usize) -> Range<u64> {
675        let raw_end = locations
676            .get(idx + 1)
677            .map(|next| next.first_row_index as usize)
678            .unwrap_or(self.row_count);
679        let first_row = self.first_row
680            + self
681                .rows
682                .selected_before(locations[idx].first_row_index as usize);
683        first_row..self.first_row + self.rows.selected_before(raw_end)
684    }
685
686    /// The sort key of the data page at `position` in `pages`, if any.
687    fn data_page(
688        &self,
689        locations: &[PageLocation],
690        pages: PageSet<'_>,
691        position: usize,
692    ) -> Option<RangeOrder> {
693        if position >= pages.len() {
694            return None;
695        }
696        let idx = pages.page(position);
697        let rows = self.page_rows(locations, idx);
698        Some((rows.start, Reverse(rows.end), locations[idx].offset as u64))
699    }
700
701    /// The first range of one column chunk: its sort key and position, or
702    /// `None` if the column chunk has no range. Also returns the data pages
703    /// that the decoder reads, if the selection removes pages.
704    ///
705    /// The ranges are the same bytes that `InMemoryRowGroup::fetch_ranges`
706    /// requests, split at page boundaries when page locations are known.
707    fn first_range(
708        &self,
709        column_idx: usize,
710        stage: ScanStage,
711    ) -> (Option<(RangeOrder, HeadPosition)>, Option<Vec<usize>>) {
712        let fetch_selection = column_selection(
713            self.selection.as_ref(),
714            self.expanded_selection.as_ref(),
715            self.stages.fetch(stage).cache_projection,
716            column_idx,
717        );
718        let all_locations = self.locations(column_idx);
719        let fetch = ColumnFetch::new(self.chunk(column_idx), all_locations, fetch_selection);
720        // The decoder fetches a whole column chunk as one range. If page
721        // locations are known, the plan splits it into the same bytes, page
722        // by page.
723        let locations = all_locations.filter(|l| !l.is_empty());
724        let (locations, dictionary, selected) = match (fetch, locations) {
725            (ColumnFetch::Chunk { range }, Some(locations)) => {
726                (locations, dictionary_range(range.start, locations), None)
727            }
728            (ColumnFetch::Chunk { range }, None) => {
729                let rows = self.row_group_rows();
730                let order = (rows.start, Reverse(rows.end), range.start);
731                return (Some((order, CHUNK)), None);
732            }
733            (
734                ColumnFetch::Pages {
735                    dictionary,
736                    locations,
737                    pages,
738                },
739                _,
740            ) => (locations, dictionary, Some(pages)),
741        };
742        let pages = match &selected {
743            Some(pages) => PageSet::Selected(pages),
744            None => PageSet::All(locations.len()),
745        };
746
747        let head = if let Some(dictionary) = dictionary {
748            // The dictionary serves exactly the rows of the data pages read.
749            let rows = match pages.len() {
750                0 => self.row_group_rows(),
751                len => {
752                    let first = self.page_rows(locations, pages.page(0));
753                    let last = self.page_rows(locations, pages.page(len - 1));
754                    first.start..last.end
755                }
756            };
757            Some((
758                (rows.start, Reverse(rows.end), dictionary.start),
759                DICTIONARY,
760            ))
761        } else {
762            self.data_page(locations, pages, 0).map(|order| (order, 0))
763        };
764        (head, selected)
765    }
766}
767
768/// Counts the selected rows before a position in a row group.
769#[derive(Debug, Clone)]
770struct SelectedRows {
771    /// `(first raw row, selected rows before it, selected)` per selector.
772    /// `None` when every row is selected.
773    runs: Option<Vec<(usize, u64, bool)>>,
774}
775
776impl SelectedRows {
777    fn new(selection: Option<&RowSelection>, row_count: usize) -> Self {
778        let runs = selection.map(|selection| {
779            let mut runs = Vec::new();
780            let mut raw = 0;
781            let mut selected = 0;
782            for selector in selection.iter() {
783                if selector.row_count == 0 {
784                    continue;
785                }
786                runs.push((raw, selected, !selector.skip));
787                raw += selector.row_count;
788                if !selector.skip {
789                    selected += selector.row_count as u64;
790                }
791            }
792            // A selection shorter than the row group skips the trailing rows.
793            if raw < row_count {
794                runs.push((raw, selected, false));
795            }
796            runs
797        });
798        Self { runs }
799    }
800
801    /// The number of selected rows in `0..raw`.
802    fn selected_before(&self, raw: usize) -> u64 {
803        let Some(runs) = &self.runs else {
804            return raw as u64;
805        };
806        let idx = runs.partition_point(|(start, _, _)| *start < raw);
807        let Some(&(start, selected_before, selected)) = idx.checked_sub(1).map(|idx| &runs[idx])
808        else {
809            return 0;
810        };
811        if selected {
812            selected_before + (raw - start) as u64
813        } else {
814            selected_before
815        }
816    }
817}
818
819#[cfg(test)]
820mod tests;