Skip to main content

parquet/arrow/
in_memory_row_group.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
5use crate::arrow::ProjectionMask;
6use crate::arrow::array_reader::RowGroups;
7use crate::arrow::arrow_reader::RowSelection;
8use crate::column::page::{PageIterator, PageReader};
9use crate::errors::ParquetError;
10use crate::file::metadata::page_index::RowGroupPageIndex;
11use crate::file::metadata::{ParquetMetaData, RowGroupMetaData};
12use crate::file::page_index::offset_index::PageLocation;
13use crate::file::reader::{ChunkReader, Length, SerializedPageReader};
14use bytes::{Buf, Bytes};
15use std::ops::Range;
16use std::sync::Arc;
17
18/// An in-memory collection of column chunks
19#[derive(Debug)]
20pub(crate) struct InMemoryRowGroup<'a> {
21    pub(crate) page_index: Option<RowGroupPageIndex>,
22    /// Column chunks for this row group
23    pub(crate) column_chunks: Vec<Option<Arc<ColumnChunkData>>>,
24    pub(crate) row_count: usize,
25    pub(crate) row_group_idx: usize,
26    pub(crate) metadata: &'a ParquetMetaData,
27}
28
29/// What ranges to fetch for the columns in this row group
30#[derive(Debug)]
31pub(crate) struct FetchRanges {
32    /// The byte ranges to fetch
33    pub(crate) ranges: Vec<Range<u64>>,
34    /// If `Some`, the start offsets of each page for each column chunk, or
35    /// `None` for a column chunk without an offset index (fetched in full)
36    pub(crate) page_start_offsets: Option<Vec<Option<Vec<u64>>>>,
37}
38
39impl InMemoryRowGroup<'_> {
40    /// Returns the byte ranges to fetch for the columns specified in
41    /// `projection` and `selection`.
42    ///
43    /// `cache_mask` indicates which columns, if any, are being cached by
44    /// [`RowGroupCache`](crate::arrow::array_reader::RowGroupCache).
45    /// The `selection` for Cached columns is expanded to batch boundaries to simplify
46    /// accounting for what data is cached.
47    ///
48    /// The ranges of each column chunk come from [`ColumnFetch`].
49    pub(crate) fn fetch_ranges(
50        &self,
51        projection: &ProjectionMask,
52        selection: Option<&RowSelection>,
53        batch_size: usize,
54        cache_mask: Option<&ProjectionMask>,
55    ) -> FetchRanges {
56        let metadata = self.metadata.row_group(self.row_group_idx);
57        // With a `RowSelection` and an `OffsetIndex`, only fetch the pages
58        // required for the `RowSelection`
59        let page_index = self.page_index.as_ref().filter(|_| selection.is_some());
60        let expanded_selection = selection
61            .filter(|_| page_index.is_some() && cache_mask.is_some())
62            .map(|selection| selection.expand_to_batch_boundaries(batch_size, self.row_count));
63
64        // Consider preallocating outer vec: https://github.com/apache/arrow-rs/issues/8667
65        let mut page_start_offsets: Option<Vec<Option<Vec<u64>>>> = page_index.map(|_| vec![]);
66        let mut ranges = vec![];
67        let columns = columns_to_fetch(projection, self.column_chunks.len(), |idx| {
68            self.column_chunks[idx].is_some()
69        });
70        for idx in columns {
71            let locations = page_index
72                .and_then(|page_index| page_index.offset_index(idx))
73                .map(|offset_index| offset_index.page_locations().as_slice());
74            let column_selection =
75                column_selection(selection, expanded_selection.as_ref(), cache_mask, idx);
76            let (start, len) = metadata.column(idx).byte_range();
77            let fetch = ColumnFetch::new(start..start + len, locations, column_selection);
78            let first = ranges.len();
79            ranges.extend(fetch.ranges());
80            if let Some(page_start_offsets) = page_start_offsets.as_mut() {
81                page_start_offsets.push(match fetch {
82                    // No offset index for this column, fetch the entire column
83                    ColumnFetch::Chunk { .. } => None,
84                    ColumnFetch::Pages { .. } => {
85                        Some(ranges[first..].iter().map(|range| range.start).collect())
86                    }
87                });
88            }
89        }
90        FetchRanges {
91            ranges,
92            page_start_offsets,
93        }
94    }
95
96    /// Fills in `self.column_chunks` with the data fetched from `chunk_data`.
97    ///
98    /// This function **must** be called with the data from the ranges returned by
99    /// `fetch_ranges` and the corresponding page_start_offsets, with the exact same and `selection`.
100    pub(crate) fn fill_column_chunks<I>(
101        &mut self,
102        projection: &ProjectionMask,
103        page_start_offsets: Option<Vec<Option<Vec<u64>>>>,
104        chunk_data: I,
105    ) where
106        I: IntoIterator<Item = Bytes>,
107    {
108        let mut chunk_data = chunk_data.into_iter();
109        let metadata = self.metadata.row_group(self.row_group_idx);
110        if let Some(page_start_offsets) = page_start_offsets {
111            // If we have a `RowSelection` and an `OffsetIndex` then only fetch pages required for the
112            // `RowSelection`
113            let mut page_start_offsets = page_start_offsets.into_iter();
114
115            for (idx, chunk) in self.column_chunks.iter_mut().enumerate() {
116                if chunk.is_some() || !projection.leaf_included(idx) {
117                    continue;
118                }
119
120                match page_start_offsets.next() {
121                    // No offset index: `fetch_ranges` requested the whole chunk
122                    Some(None) => {
123                        if let Some(data) = chunk_data.next() {
124                            *chunk = Some(Arc::new(ColumnChunkData::Dense {
125                                offset: metadata.column(idx).byte_range().0 as usize,
126                                data,
127                            }));
128                        }
129                    }
130                    Some(Some(offsets)) => {
131                        let mut chunks = Vec::with_capacity(offsets.len());
132                        for _ in 0..offsets.len() {
133                            chunks.push(chunk_data.next().unwrap());
134                        }
135
136                        *chunk = Some(Arc::new(ColumnChunkData::Sparse {
137                            length: metadata.column(idx).byte_range().1 as usize,
138                            data: offsets
139                                .into_iter()
140                                .map(|x| x as usize)
141                                .zip(chunks)
142                                .collect(),
143                        }))
144                    }
145                    None => {}
146                }
147            }
148        } else {
149            for (idx, chunk) in self.column_chunks.iter_mut().enumerate() {
150                if chunk.is_some() || !projection.leaf_included(idx) {
151                    continue;
152                }
153
154                if let Some(data) = chunk_data.next() {
155                    *chunk = Some(Arc::new(ColumnChunkData::Dense {
156                        offset: metadata.column(idx).byte_range().0 as usize,
157                        data,
158                    }));
159                }
160            }
161        }
162    }
163}
164
165/// The leaf columns in `projection` that are not yet read, in column order.
166///
167/// A decoding stage of a row group does not fetch a column that an earlier
168/// stage of the same row group read.
169#[inline]
170pub(crate) fn columns_to_fetch<'a>(
171    projection: &'a ProjectionMask,
172    num_columns: usize,
173    is_read: impl Fn(usize) -> bool + 'a,
174) -> impl Iterator<Item = usize> + 'a {
175    (0..num_columns).filter(move |&idx| projection.leaf_included(idx) && !is_read(idx))
176}
177
178/// The selection that [`InMemoryRowGroup::fetch_ranges`] uses to choose the
179/// pages of column `idx`: `expanded_selection` (the selection expanded to
180/// batch boundaries) if `cache_mask` includes the column, else `selection`.
181#[inline]
182pub(crate) fn column_selection<'a>(
183    selection: Option<&'a RowSelection>,
184    expanded_selection: Option<&'a RowSelection>,
185    cache_mask: Option<&ProjectionMask>,
186    idx: usize,
187) -> Option<&'a RowSelection> {
188    match expanded_selection {
189        Some(expanded) if cache_mask.is_some_and(|mask| mask.leaf_included(idx)) => Some(expanded),
190        _ => selection,
191    }
192}
193
194/// What [`InMemoryRowGroup::fetch_ranges`] fetches for one column chunk.
195///
196/// This is the one place that decides which bytes of a column chunk are
197/// requested, so other users of this rule cannot differ from the decoder.
198#[derive(Debug, Clone, PartialEq, Eq)]
199pub(crate) enum ColumnFetch<'a> {
200    /// The whole column chunk, as one range. This is the case if there is
201    /// no selection or the column has no offset index.
202    Chunk {
203        /// Byte range of the column chunk.
204        range: Range<u64>,
205    },
206    /// The dictionary page, if any, and the data pages that contain a
207    /// selected row.
208    Pages {
209        /// Byte range of the dictionary page, if the column chunk has one.
210        dictionary: Option<Range<u64>>,
211        /// The page locations of the column chunk.
212        locations: &'a [PageLocation],
213        /// Indexes in `locations` of the data pages to fetch, in page order.
214        pages: Vec<usize>,
215    },
216}
217
218impl<'a> ColumnFetch<'a> {
219    /// The fetch of the column chunk at byte range `chunk`, with page
220    /// locations `locations` from its offset index, if any, and row
221    /// selection `selection`, if any.
222    #[inline]
223    pub(crate) fn new(
224        chunk: Range<u64>,
225        locations: Option<&'a [PageLocation]>,
226        selection: Option<&RowSelection>,
227    ) -> Self {
228        let (Some(selection), Some(locations)) = (selection, locations) else {
229            return Self::Chunk { range: chunk };
230        };
231        // `scan_ranges` returns the ranges of the selected pages in page
232        // order. Map them back to page indexes.
233        let fetched = selection.scan_ranges(locations);
234        let mut fetched = fetched.iter().peekable();
235        let pages = locations
236            .iter()
237            .enumerate()
238            .filter(|(_, location)| {
239                fetched
240                    .next_if(|range| range.start == location.offset as u64)
241                    .is_some()
242            })
243            .map(|(idx, _)| idx)
244            .collect();
245        Self::Pages {
246            dictionary: dictionary_range(chunk.start, locations),
247            locations,
248            pages,
249        }
250    }
251
252    /// The byte ranges to fetch, in file order.
253    pub(crate) fn ranges(&self) -> impl Iterator<Item = Range<u64>> + '_ {
254        let (chunk, dictionary, pages) = match self {
255            Self::Chunk { range, .. } => (Some(range.clone()), None, None),
256            Self::Pages {
257                dictionary,
258                locations,
259                pages,
260            } => (None, dictionary.clone(), Some((*locations, pages))),
261        };
262        let data_pages = pages
263            .into_iter()
264            .flat_map(|(locations, pages)| pages.iter().map(|&page| page_range(&locations[page])));
265        chunk.into_iter().chain(dictionary).chain(data_pages)
266    }
267}
268
269/// Byte range of the dictionary page of a column chunk that starts at
270/// `chunk_start`: the bytes before the first data page, if any.
271#[inline]
272pub(crate) fn dictionary_range(chunk_start: u64, locations: &[PageLocation]) -> Option<Range<u64>> {
273    match locations.first() {
274        Some(first) if first.offset as u64 != chunk_start => Some(chunk_start..first.offset as u64),
275        _ => None,
276    }
277}
278
279/// Byte range of a data page.
280#[inline]
281pub(crate) fn page_range(location: &PageLocation) -> Range<u64> {
282    let start = location.offset as u64;
283    start..start + location.compressed_page_size as u64
284}
285
286impl RowGroups for InMemoryRowGroup<'_> {
287    fn num_rows(&self) -> usize {
288        self.row_count
289    }
290
291    /// Return chunks for column i
292    fn column_chunks(&self, i: usize) -> crate::errors::Result<Box<dyn PageIterator>> {
293        match &self.column_chunks[i] {
294            None => Err(ParquetError::General(format!(
295                "Invalid column index {i}, column was not fetched"
296            ))),
297            Some(data) => {
298                let page_locations = self
299                    .page_index
300                    .as_ref()
301                    .and_then(|pi| pi.page_locations(i).cloned());
302                let column_chunk_metadata = self.metadata.row_group(self.row_group_idx).column(i);
303                let page_reader = SerializedPageReader::new(
304                    data.clone(),
305                    column_chunk_metadata,
306                    self.row_count,
307                    page_locations,
308                )?;
309                let page_reader = page_reader.add_crypto_context(
310                    self.row_group_idx,
311                    i,
312                    self.metadata,
313                    column_chunk_metadata,
314                )?;
315
316                let page_reader: Box<dyn PageReader> = Box::new(page_reader);
317
318                Ok(Box::new(ColumnChunkIterator {
319                    reader: Some(Ok(page_reader)),
320                }))
321            }
322        }
323    }
324
325    fn row_groups(&self) -> Box<dyn Iterator<Item = &RowGroupMetaData> + '_> {
326        Box::new(std::iter::once(self.metadata.row_group(self.row_group_idx)))
327    }
328
329    fn metadata(&self) -> &ParquetMetaData {
330        self.metadata
331    }
332}
333
334/// An in-memory column chunk.
335/// This allows us to hold either dense column chunks or sparse column chunks and easily
336/// access them by offset.
337#[derive(Clone, Debug)]
338pub(crate) enum ColumnChunkData {
339    /// Column chunk data representing only a subset of data pages.
340    /// For example if a row selection (possibly caused by a filter in a query) causes us to read only
341    /// a subset of the rows in the column.
342    Sparse {
343        /// Length of the full column chunk
344        length: usize,
345        /// Subset of data pages included in this sparse chunk.
346        ///
347        /// Each element is a tuple of (page offset within file, page data).
348        /// Each entry is a complete page and the list is ordered by offset.
349        data: Vec<(usize, Bytes)>,
350    },
351    /// Full column chunk and the offset within the original file
352    Dense { offset: usize, data: Bytes },
353}
354
355impl ColumnChunkData {
356    /// Return the data for this column chunk at the given offset
357    fn get(&self, start: u64) -> crate::errors::Result<Bytes> {
358        match &self {
359            ColumnChunkData::Sparse { data, .. } => data
360                .binary_search_by_key(&start, |(offset, _)| *offset as u64)
361                .map(|idx| data[idx].1.clone())
362                .map_err(|_| {
363                    ParquetError::General(format!(
364                        "Invalid offset in sparse column chunk data: {start}, no matching page found.\
365                         If you are using a `SelectionStrategyPolicy::Mask`, ensure that the OffsetIndex is provided when \
366                         creating the InMemoryRowGroup."
367                    ))
368                }),
369            ColumnChunkData::Dense { offset, data } => {
370                let start = start as usize - *offset;
371                Ok(data.slice(start..))
372            }
373        }
374    }
375}
376
377impl Length for ColumnChunkData {
378    /// Return the total length of the full column chunk
379    fn len(&self) -> u64 {
380        match &self {
381            ColumnChunkData::Sparse { length, .. } => *length as u64,
382            ColumnChunkData::Dense { data, .. } => data.len() as u64,
383        }
384    }
385}
386
387impl ChunkReader for ColumnChunkData {
388    type T = bytes::buf::Reader<Bytes>;
389
390    fn get_read(&self, start: u64) -> crate::errors::Result<Self::T> {
391        Ok(self.get(start)?.reader())
392    }
393
394    fn get_bytes(&self, start: u64, length: usize) -> crate::errors::Result<Bytes> {
395        let data = self.get(start)?;
396        if data.len() < length {
397            return Err(general_err!(
398                "column chunk data at offset {start} has {} bytes, expected {length}",
399                data.len()
400            ));
401        }
402        Ok(data.slice(..length))
403    }
404}
405
406/// Implements [`PageIterator`] for a single column chunk, yielding a single [`PageReader`]
407struct ColumnChunkIterator {
408    reader: Option<crate::errors::Result<Box<dyn PageReader>>>,
409}
410
411impl Iterator for ColumnChunkIterator {
412    type Item = crate::errors::Result<Box<dyn PageReader>>;
413
414    fn next(&mut self) -> Option<Self::Item> {
415        self.reader.take()
416    }
417}
418
419impl PageIterator for ColumnChunkIterator {}
420
421#[cfg(test)]
422mod tests {
423    use super::*;
424
425    #[test]
426    fn get_bytes_errors_on_short_data() {
427        let dense = ColumnChunkData::Dense {
428            offset: 100,
429            data: Bytes::from_static(b"0123456789"),
430        };
431        assert_eq!(
432            dense.get_bytes(105, 5).unwrap(),
433            Bytes::from_static(b"56789")
434        );
435        let err = dense.get_bytes(105, 6).unwrap_err().to_string();
436        assert!(err.contains("has 5 bytes, expected 6"), "{err}");
437    }
438}