1use 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#[derive(Debug)]
17enum QueuedRowGroupDecision {
18 Read(NextRowGroup),
20 Skip { remaining_budget: RowBudget },
22}
23
24#[derive(Debug, Clone)]
26pub(crate) struct NextRowGroup {
27 pub(crate) row_group_idx: usize,
28 pub(crate) row_count: usize,
29 pub(crate) selection: Option<RowSelection>,
31 pub(crate) budget: RowBudget,
33}
34
35#[derive(Debug, Clone)]
38struct QueuedRowGroups {
39 queue: Queue,
40 counts: HashMap<usize, usize>,
43}
44
45impl QueuedRowGroups {
46 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 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 fn row_groups(&self) -> impl Iterator<Item = usize> + '_ {
71 self.counts.keys().copied()
72 }
73
74 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 fn global_selection_is_exhausted(&self) -> bool {
90 self.queue.global_selection_is_exhausted()
91 }
92
93 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#[derive(Debug, Clone)]
110enum Queue {
111 Global {
113 row_groups: VecDeque<usize>,
114 selection: Option<RowSelection>,
115 },
116 PerRowGroup(VecDeque<RowGroupSelection>),
118}
119
120impl Queue {
121 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 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 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 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 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 pub(super) parquet_metadata: Arc<ParquetMetaData>,
249 queued: QueuedRowGroups,
251 pub(super) budget: RowBudget,
253 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 pub(crate) fn queued_row_groups(&self) -> impl Iterator<Item = usize> + '_ {
277 self.queued.row_groups()
278 }
279
280 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 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 pub(crate) fn row_groups_remaining(&self) -> usize {
308 self.queued.len()
309 }
310
311 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 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 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 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 (
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 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 assert_eq!(local.peek_next_row_group().unwrap(), Some(0));
574 assert_eq!(queued(&local), (true, true));
575
576 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 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}