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;