Skip to main content

parquet/arrow/push_decoder/scan_plan/
budget.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//! Offset/limit budget shared across the row groups of a scan.
6
7use crate::arrow::arrow_reader::ReadPlanBuilder;
8
9/// Running offset/limit budget shared across row groups.
10#[derive(Debug, Clone, Copy, Eq, PartialEq)]
11pub(crate) struct RowBudget {
12    offset: Option<usize>,
13    limit: Option<usize>,
14}
15
16impl RowBudget {
17    pub(crate) fn new(offset: Option<usize>, limit: Option<usize>) -> Self {
18        Self { offset, limit }
19    }
20
21    pub(crate) fn is_exhausted(self) -> bool {
22        matches!(self.limit, Some(0))
23    }
24
25    /// The offset still to be skipped before the next readable row group.
26    pub(crate) fn offset(self) -> Option<usize> {
27        self.offset
28    }
29
30    /// The number of output rows still permitted across the remaining row groups.
31    pub(crate) fn limit(self) -> Option<usize> {
32        self.limit
33    }
34
35    /// Returns how many selected rows remain after applying this budget.
36    pub(crate) fn rows_after(self, rows_before_budget: usize) -> usize {
37        let rows_after_offset = rows_before_budget.saturating_sub(self.offset.unwrap_or(0));
38        match self.limit {
39            Some(limit) => rows_after_offset.min(limit),
40            None => rows_after_offset,
41        }
42    }
43
44    /// Returns the number of selected rows needed before applying the offset.
45    pub(crate) fn selected_row_limit(self) -> Option<usize> {
46        self.limit
47            .map(|limit| limit.saturating_add(self.offset.unwrap_or(0)))
48    }
49
50    pub(crate) fn apply_to_plan(
51        self,
52        plan_builder: ReadPlanBuilder,
53        row_count: usize,
54    ) -> BudgetedReadPlan {
55        let rows_before_budget = plan_builder.num_rows_selected().unwrap_or(row_count);
56        let plan_builder = plan_builder
57            .limited(row_count)
58            .with_offset(self.offset)
59            .with_limit(self.limit)
60            .build_limited();
61        let rows_after_budget = self.rows_after(rows_before_budget);
62
63        BudgetedReadPlan {
64            plan_builder,
65            rows_before_budget,
66            rows_after_budget,
67            remaining_budget: self.advance(rows_before_budget, rows_after_budget),
68        }
69    }
70
71    /// Advance the budget past one row group.
72    ///
73    /// `rows_before_budget` is the number of rows selected before applying the
74    /// budget, and `rows_after_budget` is the number retained for output from
75    /// this row group.
76    pub(crate) fn advance(mut self, rows_before_budget: usize, rows_after_budget: usize) -> Self {
77        if let Some(offset) = &mut self.offset {
78            // Reduction is either because of offset or limit, as limit is applied
79            // after offset has been "exhausted" can just use saturating sub here.
80            *offset = offset.saturating_sub(rows_before_budget - rows_after_budget);
81        }
82
83        if rows_after_budget != 0
84            && let Some(limit) = &mut self.limit
85        {
86            *limit -= rows_after_budget;
87        }
88
89        self
90    }
91}
92
93#[derive(Debug)]
94pub(crate) struct BudgetedReadPlan {
95    /// Read plan after applying this row group's share of the offset/limit budget.
96    pub(crate) plan_builder: ReadPlanBuilder,
97    /// Number of rows selected by row selection and predicates before applying
98    /// this row group's offset/limit budget.
99    pub(crate) rows_before_budget: usize,
100    /// Number of selected rows that remain to be read after applying this row
101    /// group's offset/limit budget.
102    pub(crate) rows_after_budget: usize,
103    /// Budget remaining for later row groups.
104    pub(crate) remaining_budget: RowBudget,
105}
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110    use crate::arrow::arrow_reader::{RowSelection, RowSelector};
111
112    #[test]
113    fn test_row_budget_offset_limit_across_row_groups() {
114        let first =
115            RowBudget::new(Some(225), Some(20)).apply_to_plan(ReadPlanBuilder::new(1024), 200);
116        assert_eq!(first.rows_before_budget, 200);
117        assert_eq!(first.rows_after_budget, 0);
118        assert_eq!(first.remaining_budget, RowBudget::new(Some(25), Some(20)));
119        assert_eq!(first.plan_builder.num_rows_selected(), Some(0));
120
121        let second = first
122            .remaining_budget
123            .apply_to_plan(ReadPlanBuilder::new(1024), 200);
124        assert_eq!(second.rows_before_budget, 200);
125        assert_eq!(second.rows_after_budget, 20);
126        assert_eq!(second.remaining_budget, RowBudget::new(Some(0), Some(0)));
127        assert_eq!(second.plan_builder.num_rows_selected(), Some(20));
128    }
129
130    #[test]
131    fn test_row_budget_limit_only() {
132        let budgeted =
133            RowBudget::new(None, Some(20)).apply_to_plan(ReadPlanBuilder::new(1024), 200);
134        assert_eq!(budgeted.rows_before_budget, 200);
135        assert_eq!(budgeted.rows_after_budget, 20);
136        assert_eq!(budgeted.remaining_budget, RowBudget::new(None, Some(0)));
137        assert_eq!(budgeted.plan_builder.num_rows_selected(), Some(20));
138    }
139
140    #[test]
141    fn test_row_budget_empty_selection() {
142        let empty_selection = RowSelection::from(vec![RowSelector::skip(200)]);
143        let budgeted = RowBudget::new(Some(10), Some(20)).apply_to_plan(
144            ReadPlanBuilder::new(1024).with_selection(Some(empty_selection)),
145            200,
146        );
147        assert_eq!(budgeted.rows_before_budget, 0);
148        assert_eq!(budgeted.rows_after_budget, 0);
149        assert_eq!(
150            budgeted.remaining_budget,
151            RowBudget::new(Some(10), Some(20))
152        );
153        assert_eq!(budgeted.plan_builder.num_rows_selected(), Some(0));
154    }
155}