Skip to main content

parquet/arrow/push_decoder/scan_plan/
frontier.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//! Which row groups a scan reads next, with their selections and budget.
6
7use crate::arrow::arrow_reader::{RowGroupPlan, RowGroupSelection, RowSelection};
8use crate::errors::ParquetError;
9use crate::file::metadata::ParquetMetaData;
10use std::collections::{HashMap, VecDeque};
11use std::sync::Arc;
12
13use super::budget::RowBudget;
14
15/// Plan for the next queued row group after row-selection slicing.
16#[derive(Debug)]
17enum QueuedRowGroupDecision {
18    /// Hand this row group to the builder.
19    Read(NextRowGroup),
20    /// Skip this row group, and keep scanning with the updated budget.
21    Skip { remaining_budget: RowBudget },
22}
23
24/// Work item handed from [`RowGroupFrontier`] to [`RowGroupReaderBuilder`](crate::arrow::push_decoder::reader_builder::RowGroupReaderBuilder).
25#[derive(Debug, Clone)]
26pub(crate) struct NextRowGroup {
27    pub(crate) row_group_idx: usize,
28    pub(crate) row_count: usize,
29    /// This row group's selection, or `None` when all rows are selected.
30    pub(crate) selection: Option<RowSelection>,
31    /// Budget snapshot to apply while decoding this row group.
32    pub(crate) budget: RowBudget,
33}
34
35/// Row groups and selections that have not yet been handed to the row-group
36/// reader builder.
37#[derive(Debug, Clone)]
38struct QueuedRowGroups {
39    queue: Queue,
40    /// The number of times each row group is in `queue`, so that
41    /// [`Self::contains`] does not scan the queue.
42    counts: HashMap<usize, usize>,
43}
44
45impl QueuedRowGroups {
46    /// Validate and queue a row-group plan for `parquet_metadata`.
47    fn try_new(
48        parquet_metadata: &ParquetMetaData,
49        row_group_plan: RowGroupPlan,
50    ) -> Result<Self, ParquetError> {
51        let queue = Queue::try_new(parquet_metadata, row_group_plan)?;
52        let mut counts = HashMap::new();
53        for row_group_idx in queue.row_group_indices() {
54            *counts.entry(row_group_idx).or_default() += 1;
55        }
56        Ok(Self { queue, counts })
57    }
58
59    /// Convert the remaining queue back into a builder configuration.
60    fn into_plan(self) -> RowGroupPlan {
61        self.queue.into_plan()
62    }
63
64    fn front(&self) -> Option<usize> {
65        self.queue.front()
66    }
67
68    /// The row groups in the queue, in no specific order and without
69    /// duplicates.
70    fn row_groups(&self) -> impl Iterator<Item = usize> + '_ {
71        self.counts.keys().copied()
72    }
73
74    /// Returns `true` if `row_group_idx` is in the queue.
75    fn contains(&self, row_group_idx: usize) -> bool {
76        self.counts.contains_key(&row_group_idx)
77    }
78
79    fn len(&self) -> usize {
80        self.queue.len()
81    }
82
83    fn clear(&mut self) {
84        self.queue.clear();
85        self.counts.clear();
86    }
87
88    /// See [`Queue::global_selection_is_exhausted`].
89    fn global_selection_is_exhausted(&self) -> bool {
90        self.queue.global_selection_is_exhausted()
91    }
92
93    /// Remove the front row group and return its local selection.
94    fn pop_front_selection(&mut self, row_count: usize) -> Option<RowSelection> {
95        if let Some(row_group_idx) = self.queue.front() {
96            match self.counts.get_mut(&row_group_idx) {
97                Some(1) => {
98                    self.counts.remove(&row_group_idx);
99                }
100                Some(count) => *count -= 1,
101                None => debug_assert!(false, "row group {row_group_idx} is queued but not counted"),
102            }
103        }
104        self.queue.pop_front_selection(row_count)
105    }
106}
107
108/// The queue of [`QueuedRowGroups`].
109#[derive(Debug, Clone)]
110enum Queue {
111    /// One selection cursor spans all queued row groups.
112    Global {
113        row_groups: VecDeque<usize>,
114        selection: Option<RowSelection>,
115    },
116    /// Selections are already relative to their respective row groups.
117    PerRowGroup(VecDeque<RowGroupSelection>),
118}
119
120impl Queue {
121    /// Validate and queue a row-group plan for `parquet_metadata`.
122    fn try_new(
123        parquet_metadata: &ParquetMetaData,
124        row_group_plan: RowGroupPlan,
125    ) -> Result<Self, ParquetError> {
126        match row_group_plan {
127            RowGroupPlan::Global {
128                row_groups,
129                selection,
130            } => Ok(Self::Global {
131                row_groups: row_groups
132                    .unwrap_or_else(|| (0..parquet_metadata.num_row_groups()).collect())
133                    .into(),
134                selection,
135            }),
136            RowGroupPlan::PerRowGroup(row_groups) => {
137                for row_group in &row_groups {
138                    let row_count =
139                        parquet_metadata.row_group_num_rows(row_group.row_group_index)?;
140                    if let Some(selection) = &row_group.selection {
141                        let selection_rows = selection.total_row_count();
142                        if selection_rows > row_count {
143                            return Err(ParquetError::General(format!(
144                                "Row selection for row group {} contains {selection_rows} rows, but the row group has {row_count}",
145                                row_group.row_group_index
146                            )));
147                        }
148                    }
149                }
150                Ok(Self::PerRowGroup(row_groups.into()))
151            }
152            RowGroupPlan::Conflicting => Err(RowGroupPlan::conflict_error()),
153        }
154    }
155
156    /// Convert the remaining queue back into a builder configuration.
157    fn into_plan(self) -> RowGroupPlan {
158        match self {
159            Self::Global {
160                row_groups,
161                selection,
162            } => RowGroupPlan::Global {
163                row_groups: Some(Vec::from(row_groups)),
164                selection,
165            },
166            Self::PerRowGroup(row_groups) => RowGroupPlan::PerRowGroup(Vec::from(row_groups)),
167        }
168    }
169
170    fn front(&self) -> Option<usize> {
171        match self {
172            Self::Global { row_groups, .. } => row_groups.front().copied(),
173            Self::PerRowGroup(row_groups) => row_groups
174                .front()
175                .map(|row_group| row_group.row_group_index),
176        }
177    }
178
179    /// The queued row group indexes, in order.
180    fn row_group_indices(&self) -> Vec<usize> {
181        match self {
182            Self::Global { row_groups, .. } => row_groups.iter().copied().collect(),
183            Self::PerRowGroup(row_groups) => row_groups
184                .iter()
185                .map(|row_group| row_group.row_group_index)
186                .collect(),
187        }
188    }
189
190    fn len(&self) -> usize {
191        match self {
192            Self::Global { row_groups, .. } => row_groups.len(),
193            Self::PerRowGroup(row_groups) => row_groups.len(),
194        }
195    }
196
197    fn clear(&mut self) {
198        match self {
199            Self::Global {
200                row_groups,
201                selection,
202            } => {
203                row_groups.clear();
204                *selection = None;
205            }
206            Self::PerRowGroup(row_groups) => row_groups.clear(),
207        }
208    }
209
210    /// Returns `true` when a shared global selection has no selected rows left.
211    /// Per-row-group selections are independent and are drained one at a time.
212    fn global_selection_is_exhausted(&self) -> bool {
213        matches!(
214            self,
215            Self::Global {
216                selection: Some(selection),
217                ..
218            } if selection.row_count() == 0
219        )
220    }
221
222    /// Remove the front row group and return its local selection.
223    fn pop_front_selection(&mut self, row_count: usize) -> Option<RowSelection> {
224        match self {
225            Self::Global {
226                row_groups,
227                selection,
228            } => {
229                let popped = row_groups.pop_front();
230                debug_assert!(popped.is_some(), "front row group checked before pop");
231                selection
232                    .as_mut()
233                    .map(|selection| selection.split_off(row_count))
234            }
235            Self::PerRowGroup(row_groups) => {
236                row_groups
237                    .pop_front()
238                    .expect("front row group checked before pop")
239                    .selection
240            }
241        }
242    }
243}
244
245#[derive(Debug, Clone)]
246pub(crate) struct RowGroupFrontier {
247    /// Metadata used to resolve row counts for queued row groups.
248    pub(super) parquet_metadata: Arc<ParquetMetaData>,
249    /// Row groups not yet handed to the builder.
250    queued: QueuedRowGroups,
251    /// Offset/limit budget before the next readable row group is planned.
252    pub(super) budget: RowBudget,
253    /// If predicates are present, row groups with selected rows must be read so
254    /// the predicate can decide whether they are actually needed.
255    pub(super) has_predicates: bool,
256}
257
258impl RowGroupFrontier {
259    pub(crate) fn new(
260        parquet_metadata: Arc<ParquetMetaData>,
261        row_group_plan: RowGroupPlan,
262        budget: RowBudget,
263        has_predicates: bool,
264    ) -> Result<Self, ParquetError> {
265        let queued = QueuedRowGroups::try_new(&parquet_metadata, row_group_plan)?;
266
267        Ok(Self {
268            parquet_metadata,
269            queued,
270            budget,
271            has_predicates,
272        })
273    }
274
275    /// The queued row groups, in no specific order and without duplicates.
276    pub(crate) fn queued_row_groups(&self) -> impl Iterator<Item = usize> + '_ {
277        self.queued.row_groups()
278    }
279
280    /// Returns `true` if `row_group_idx` is still queued to be read.
281    pub(crate) fn is_queued(&self, row_group_idx: usize) -> bool {
282        self.queued.contains(row_group_idx)
283    }
284
285    pub(crate) fn update_budget_after_row_group(&mut self, budget: RowBudget) {
286        self.budget = budget;
287    }
288
289    /// Peek at the next row-group index [`Self::next_readable_row_group`]
290    /// would hand out, without mutating any state. Returns `None` if every
291    /// remaining row group would be skipped under the current
292    /// selection/budget, or if the queue is empty.
293    ///
294    /// Runs the real [`Self::next_readable_row_group`] advance logic on a
295    /// throwaway clone of the frontier, so peek can never drift from the
296    /// read path. The clone copies the queued row-group plan and selections;
297    /// see
298    /// [`RemainingRowGroups::peek_next_row_group`](crate::arrow::push_decoder::remaining::RemainingRowGroups::peek_next_row_group).
299    pub(crate) fn peek_next_row_group(&self) -> Result<Option<usize>, ParquetError> {
300        Ok(self
301            .clone()
302            .next_readable_row_group()?
303            .map(|next_row_group| next_row_group.row_group_idx))
304    }
305
306    /// Number of row groups not yet handed to the builder.
307    pub(crate) fn row_groups_remaining(&self) -> usize {
308        self.queued.len()
309    }
310
311    /// Decompose into the metadata, the row groups not yet handed to the
312    /// builder, and the remaining offset/limit budget.
313    pub(crate) fn into_parts(self) -> (Arc<ParquetMetaData>, RowGroupPlan, RowBudget) {
314        let Self {
315            parquet_metadata,
316            queued,
317            budget,
318            has_predicates: _,
319        } = self;
320        (parquet_metadata, queued.into_plan(), budget)
321    }
322
323    fn clear_remaining(&mut self) {
324        self.queued.clear();
325    }
326
327    /// Plan whether a selected row group should be read or skipped.
328    ///
329    /// Selection-only skips are handled before this method is called. This
330    /// method applies the remaining offset/limit budget and predicate
331    /// conservatism.
332    fn plan_selected_row_group(
333        &self,
334        next_row_group: NextRowGroup,
335        selected_rows: usize,
336    ) -> QueuedRowGroupDecision {
337        if self.has_predicates {
338            return QueuedRowGroupDecision::Read(next_row_group);
339        }
340
341        let rows_after_budget = self.budget.rows_after(selected_rows);
342        if rows_after_budget != 0 {
343            return QueuedRowGroupDecision::Read(next_row_group);
344        }
345
346        QueuedRowGroupDecision::Skip {
347            remaining_budget: self.budget.advance(selected_rows, rows_after_budget),
348        }
349    }
350
351    /// Advance queued row groups until one should be handed to the builder.
352    pub(crate) fn next_readable_row_group(&mut self) -> Result<Option<NextRowGroup>, ParquetError> {
353        loop {
354            let Some(row_group_idx) = self.queued.front() else {
355                return Ok(None);
356            };
357            // A global selection can be exhausted before its row-group queue.
358            // Per-row-group selections have no shared cursor to exhaust; empty
359            // local selections are discarded by the `selected_rows == 0` path below.
360            if self.budget.is_exhausted() || self.queued.global_selection_is_exhausted() {
361                self.clear_remaining();
362                return Ok(None);
363            }
364
365            let row_count = self.parquet_metadata.row_group_num_rows(row_group_idx)?;
366            let selection = self.queued.pop_front_selection(row_count);
367            let (selection, selected_rows) = match selection {
368                Some(selection) => {
369                    let selected_rows = selection.row_count();
370                    if selected_rows == 0 {
371                        continue;
372                    }
373                    // An all-rows selection is equivalent to no selection
374                    (
375                        (selected_rows != row_count).then_some(selection),
376                        selected_rows,
377                    )
378                }
379                None => (None, row_count),
380            };
381
382            let next_row_group = NextRowGroup {
383                row_group_idx,
384                row_count,
385                selection,
386                budget: self.budget,
387            };
388
389            match self.plan_selected_row_group(next_row_group, selected_rows) {
390                QueuedRowGroupDecision::Read(next_row_group) => {
391                    return Ok(Some(next_row_group));
392                }
393                QueuedRowGroupDecision::Skip { remaining_budget } => {
394                    self.budget = remaining_budget;
395                }
396            }
397        }
398    }
399}
400
401#[cfg(test)]
402mod tests {
403    use super::*;
404    use crate::arrow::arrow_reader::RowSelector;
405    use crate::arrow::push_decoder::test::test_file_parquet_metadata;
406
407    fn global_plan(
408        row_groups: Option<Vec<usize>>,
409        selection: Option<RowSelection>,
410    ) -> RowGroupPlan {
411        RowGroupPlan::Global {
412            row_groups,
413            selection,
414        }
415    }
416
417    #[test]
418    fn queued_row_groups_encapsulates_plan_transitions() {
419        let metadata = test_file_parquet_metadata();
420
421        let mut all_row_groups =
422            QueuedRowGroups::try_new(&metadata, global_plan(None, None)).unwrap();
423        assert_eq!(all_row_groups.len(), 2);
424        assert_eq!(all_row_groups.front(), Some(0));
425        assert!(!all_row_groups.global_selection_is_exhausted());
426        assert!(all_row_groups.pop_front_selection(200).is_none());
427        assert_eq!(all_row_groups.front(), Some(1));
428        all_row_groups.clear();
429        assert_eq!(all_row_groups.len(), 0);
430        assert!(matches!(
431            all_row_groups.into_plan(),
432            RowGroupPlan::Global {
433                row_groups: Some(row_groups),
434                selection: None,
435            } if row_groups.is_empty()
436        ));
437
438        let global_selection = RowSelection::from(vec![
439            RowSelector::skip(10),
440            RowSelector::select(5),
441            RowSelector::skip(185),
442            RowSelector::select(200),
443        ]);
444        let mut global = QueuedRowGroups::try_new(
445            &metadata,
446            global_plan(Some(vec![0, 1]), Some(global_selection)),
447        )
448        .unwrap();
449        let first = global.pop_front_selection(200).unwrap();
450        assert_eq!(first.row_count(), 5);
451        assert!(!global.global_selection_is_exhausted());
452        assert!(matches!(
453            global.into_plan(),
454            RowGroupPlan::Global {
455                row_groups: Some(row_groups),
456                selection: Some(selection),
457            } if row_groups == vec![1] && selection.row_count() == 200
458        ));
459
460        let local_selection =
461            RowSelection::from(vec![RowSelector::skip(5), RowSelector::select(3)]);
462        let mut local = QueuedRowGroups::try_new(
463            &metadata,
464            RowGroupPlan::PerRowGroup(vec![
465                RowGroupSelection::new(1, Some(local_selection)),
466                RowGroupSelection::new(0, None),
467            ]),
468        )
469        .unwrap();
470        assert_eq!(local.front(), Some(1));
471        assert_eq!(local.pop_front_selection(200).unwrap().row_count(), 3);
472        assert!(!local.global_selection_is_exhausted());
473        assert!(matches!(
474            local.into_plan(),
475            RowGroupPlan::PerRowGroup(row_groups)
476                if row_groups == vec![RowGroupSelection::new(0, None)]
477        ));
478
479        let exhausted = QueuedRowGroups::try_new(
480            &metadata,
481            global_plan(
482                Some(vec![0]),
483                Some(RowSelection::from(vec![RowSelector::skip(200)])),
484            ),
485        )
486        .unwrap();
487        assert!(exhausted.global_selection_is_exhausted());
488    }
489
490    #[test]
491    fn frontier_handles_global_and_local_exhaustion() {
492        let metadata = test_file_parquet_metadata();
493        let budget = RowBudget::new(None, None);
494
495        let mut global = RowGroupFrontier::new(
496            Arc::clone(&metadata),
497            global_plan(
498                Some(vec![0, 1]),
499                Some(RowSelection::from(vec![RowSelector::skip(400)])),
500            ),
501            budget,
502            false,
503        )
504        .unwrap();
505        assert!(global.next_readable_row_group().unwrap().is_none());
506        assert_eq!(global.queued.len(), 0);
507
508        let mut local = RowGroupFrontier::new(
509            Arc::clone(&metadata),
510            RowGroupPlan::PerRowGroup(vec![
511                RowGroupSelection::new(0, Some(RowSelection::from(vec![RowSelector::skip(200)]))),
512                RowGroupSelection::new(1, None),
513            ]),
514            budget,
515            false,
516        )
517        .unwrap();
518        let next = local.next_readable_row_group().unwrap().unwrap();
519        assert_eq!(next.row_group_idx, 1);
520        assert_eq!(next.row_count, 200);
521        assert!(next.selection.is_none());
522
523        let mut exhausted_budget = RowGroupFrontier::new(
524            metadata,
525            RowGroupPlan::PerRowGroup(vec![RowGroupSelection::new(0, None)]),
526            RowBudget::new(None, Some(0)),
527            false,
528        )
529        .unwrap();
530        assert!(
531            exhausted_budget
532                .next_readable_row_group()
533                .unwrap()
534                .is_none()
535        );
536        assert_eq!(exhausted_budget.queued.len(), 0);
537    }
538
539    #[test]
540    fn queued_row_groups_count_repeated_row_groups() {
541        let metadata = test_file_parquet_metadata();
542        let budget = RowBudget::new(None, None);
543
544        // Row group 1 is skipped the first time. A row group stays queued
545        // until its last occurrence is popped.
546        let mut local = RowGroupFrontier::new(
547            Arc::clone(&metadata),
548            RowGroupPlan::PerRowGroup(vec![
549                RowGroupSelection::new(0, None),
550                RowGroupSelection::new(1, Some(RowSelection::from(vec![RowSelector::skip(200)]))),
551                RowGroupSelection::new(0, None),
552                RowGroupSelection::new(1, None),
553            ]),
554            budget,
555            false,
556        )
557        .unwrap();
558        let queued = |frontier: &RowGroupFrontier| {
559            (frontier.queued.contains(0), frontier.queued.contains(1))
560        };
561        assert_eq!(queued(&local), (true, true));
562
563        assert_eq!(
564            local
565                .next_readable_row_group()
566                .unwrap()
567                .unwrap()
568                .row_group_idx,
569            0
570        );
571        assert_eq!(queued(&local), (true, true));
572        // Peeking does not change the counts of the frontier.
573        assert_eq!(local.peek_next_row_group().unwrap(), Some(0));
574        assert_eq!(queued(&local), (true, true));
575
576        // Skips the first occurrence of row group 1.
577        assert_eq!(
578            local
579                .next_readable_row_group()
580                .unwrap()
581                .unwrap()
582                .row_group_idx,
583            0
584        );
585        assert_eq!(queued(&local), (false, true));
586
587        assert_eq!(
588            local
589                .next_readable_row_group()
590                .unwrap()
591                .unwrap()
592                .row_group_idx,
593            1
594        );
595        assert_eq!(queued(&local), (false, false));
596        assert!(local.queued.counts.is_empty());
597        assert!(local.next_readable_row_group().unwrap().is_none());
598
599        // An exhausted limit clears the queue and its counts.
600        let mut global = RowGroupFrontier::new(
601            metadata,
602            global_plan(Some(vec![0, 1, 0]), None),
603            RowBudget::new(None, Some(200)),
604            false,
605        )
606        .unwrap();
607        assert_eq!(
608            global
609                .next_readable_row_group()
610                .unwrap()
611                .unwrap()
612                .row_group_idx,
613            0
614        );
615        assert_eq!(queued(&global), (true, true));
616        global.update_budget_after_row_group(RowBudget::new(None, Some(0)));
617        assert!(global.next_readable_row_group().unwrap().is_none());
618        assert_eq!(queued(&global), (false, false));
619        assert!(global.queued.counts.is_empty());
620    }
621
622    #[test]
623    fn frontier_reports_invalid_global_row_group_while_peeking() {
624        let metadata = test_file_parquet_metadata();
625        let frontier = RowGroupFrontier::new(
626            metadata,
627            global_plan(Some(vec![2]), None),
628            RowBudget::new(None, None),
629            false,
630        )
631        .unwrap();
632
633        let error = frontier.peek_next_row_group().unwrap_err();
634        assert!(
635            error
636                .to_string()
637                .contains("Row group index 2 out of bounds for file with 2 row groups")
638        );
639    }
640
641    #[test]
642    fn metadata_row_count_overflow_is_reported() {
643        let metadata = test_file_parquet_metadata();
644        let mut builder = metadata.as_ref().clone().into_builder();
645        let mut row_groups = builder.take_row_groups();
646        let negative_row_group = row_groups
647            .remove(0)
648            .into_builder()
649            .set_num_rows(-1)
650            .build()
651            .unwrap();
652        let metadata = builder.set_row_groups(vec![negative_row_group]).build();
653
654        let error = metadata.row_group_num_rows(0).unwrap_err();
655        assert!(error.to_string().contains("Row count overflow"));
656    }
657}