Skip to main content

parquet/file/metadata/
column_chunk.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//! Sparse storage keyed by row-group and column coordinates.
6//!
7//! Builders use [`ColumnChunkMap`] for arbitrary insertion and replacement. Finished indexes
8//! use [`ColumnChunkEntries`], a sorted boxed slice containing only populated entries. This reduces
9//! retained memory at the cost of binary-search vs hash lookups.
10
11use crate::errors::{ParquetError, Result};
12use crate::file::metadata::memory::HeapSize;
13use std::collections::HashMap;
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16pub(crate) struct ColumnChunkKey(u64);
17
18impl ColumnChunkKey {
19    pub(crate) fn try_new(row_group_idx: usize, column_idx: usize) -> Result<Self> {
20        let row_group_idx = u32::try_from(row_group_idx).map_err(|_| {
21            ParquetError::General(format!(
22                "row group index exceeds packed coordinate limit: {row_group_idx}"
23            ))
24        })?;
25        let column_idx = u32::try_from(column_idx).map_err(|_| {
26            ParquetError::General(format!(
27                "column index exceeds packed coordinate limit: {column_idx}"
28            ))
29        })?;
30        Ok(Self(
31            (u64::from(row_group_idx) << u32::BITS) | u64::from(column_idx),
32        ))
33    }
34
35    pub(crate) fn coordinates(self) -> (usize, usize) {
36        ((self.0 >> u32::BITS) as usize, (self.0 as u32) as usize)
37    }
38}
39
40impl HeapSize for ColumnChunkKey {
41    fn heap_size(&self) -> usize {
42        0
43    }
44}
45
46fn validate_dimensions(num_row_groups: usize, num_columns: usize) -> Result<()> {
47    // Parquet metadata collection lengths are represented by signed 32-bit Thrift values.
48    i32::try_from(num_row_groups).map_err(|_| {
49        ParquetError::General(format!(
50            "row group count exceeds i32::MAX: {num_row_groups}"
51        ))
52    })?;
53    i32::try_from(num_columns).map_err(|_| {
54        ParquetError::General(format!("column count exceeds i32::MAX: {num_columns}"))
55    })?;
56    Ok(())
57}
58
59// Chunk storage backed by a HashMap to allow builders to insert to arbitrary positions.
60#[derive(Debug, Clone, PartialEq)]
61pub(crate) struct ColumnChunkMap<T> {
62    num_row_groups: usize,
63    num_columns: usize,
64    entries: HashMap<ColumnChunkKey, T>,
65}
66
67impl<T> ColumnChunkMap<T> {
68    pub(crate) fn try_new(num_row_groups: usize, num_columns: usize) -> Result<Self> {
69        validate_dimensions(num_row_groups, num_columns)?;
70        Ok(Self {
71            num_row_groups,
72            num_columns,
73            entries: HashMap::new(),
74        })
75    }
76
77    pub(crate) fn num_row_groups(&self) -> usize {
78        self.num_row_groups
79    }
80
81    pub(crate) fn num_columns(&self) -> usize {
82        self.num_columns
83    }
84
85    pub(crate) fn is_empty(&self) -> bool {
86        self.entries.is_empty()
87    }
88
89    fn key(&self, row_group_idx: usize, column_idx: usize) -> Result<ColumnChunkKey> {
90        if row_group_idx >= self.num_row_groups || column_idx >= self.num_columns {
91            return Err(ParquetError::General(format!(
92                "column chunk coordinate out of bounds: row group {row_group_idx}, column \
93                 {column_idx}; dimensions are {} by {}",
94                self.num_row_groups, self.num_columns
95            )));
96        }
97        ColumnChunkKey::try_new(row_group_idx, column_idx)
98    }
99
100    /// Inserts or replaces an entry.
101    pub(crate) fn try_insert(
102        &mut self,
103        row_group_idx: usize,
104        column_idx: usize,
105        value: T,
106    ) -> Result<Option<T>> {
107        let key = self.key(row_group_idx, column_idx)?;
108        if let Some(existing) = self.entries.get_mut(&key) {
109            return Ok(Some(std::mem::replace(existing, value)));
110        }
111
112        self.entries.try_reserve(1).map_err(|err| {
113            ParquetError::General(format!(
114                "failed to reserve storage for column chunk at row group {row_group_idx}, \
115                 column {column_idx}: {err}"
116            ))
117        })?;
118        Ok(self.entries.insert(key, value))
119    }
120
121    pub(crate) fn try_freeze(self) -> Result<ColumnChunkEntries<T>> {
122        validate_dimensions(self.num_row_groups, self.num_columns)?;
123        let num_entries = self.entries.len();
124        let mut entries = Vec::new();
125        entries.try_reserve_exact(num_entries).map_err(|err| {
126            ParquetError::General(format!(
127                "failed to allocate storage for {num_entries} column chunk entries: {err}"
128            ))
129        })?;
130        for entry in self.entries {
131            entries.push(entry);
132        }
133        entries.sort_unstable_by_key(|(key, _)| *key);
134        ColumnChunkEntries::try_from_sorted_entries(self.num_row_groups, self.num_columns, entries)
135    }
136}
137
138impl<T: HeapSize> HeapSize for ColumnChunkMap<T> {
139    fn heap_size(&self) -> usize {
140        self.entries.heap_size()
141    }
142}
143
144// Chunk storage backed by a boxed slice. Finished (immutable) indexes use this to save memory.
145#[derive(Debug, Clone, PartialEq)]
146pub(crate) struct ColumnChunkEntries<T> {
147    num_row_groups: usize,
148    num_columns: usize,
149    entries: Box<[(ColumnChunkKey, T)]>,
150}
151
152impl<T> ColumnChunkEntries<T> {
153    /// Constructs immutable storage from entries in strictly increasing row-major order.
154    /// Missing coordinates need no placeholder; dimensions only bound the stored keys.
155    pub(crate) fn try_from_sorted_entries(
156        num_row_groups: usize,
157        num_columns: usize,
158        entries: Vec<(ColumnChunkKey, T)>,
159    ) -> Result<Self> {
160        validate_dimensions(num_row_groups, num_columns)?;
161        let mut previous = None;
162        for (key, _) in &entries {
163            let (row_group_idx, column_idx) = key.coordinates();
164            if row_group_idx >= num_row_groups || column_idx >= num_columns {
165                return Err(ParquetError::General(format!(
166                    "column chunk coordinate out of bounds: row group {row_group_idx}, column \
167                     {column_idx}; dimensions are {num_row_groups} by {num_columns}"
168                )));
169            }
170            if previous.is_some_and(|previous| previous >= *key) {
171                return Err(ParquetError::General(
172                    "column chunk entries must be unique and in row-major order".to_string(),
173                ));
174            }
175            previous = Some(*key);
176        }
177        Ok(Self {
178            num_row_groups,
179            num_columns,
180            entries: entries.into_boxed_slice(),
181        })
182    }
183
184    pub(crate) fn try_from_rows(rows: Vec<Vec<Option<T>>>) -> Result<Self> {
185        let num_row_groups = rows.len();
186        let num_columns = rows.iter().map(Vec::len).max().unwrap_or_default();
187        validate_dimensions(num_row_groups, num_columns)?;
188        let num_entries = rows
189            .iter()
190            .map(|columns| columns.iter().filter(|value| value.is_some()).count())
191            .try_fold(0_usize, |total, count| total.checked_add(count))
192            .ok_or_else(|| {
193                ParquetError::General("column chunk entry count exceeds usize::MAX".to_string())
194            })?;
195        let mut entries = Vec::new();
196        entries.try_reserve_exact(num_entries).map_err(|err| {
197            ParquetError::General(format!(
198                "failed to allocate storage for {num_entries} column chunk entries: {err}"
199            ))
200        })?;
201        for (row_group_idx, columns) in rows.into_iter().enumerate() {
202            for (column_idx, value) in columns.into_iter().enumerate() {
203                if let Some(value) = value {
204                    entries.push((ColumnChunkKey::try_new(row_group_idx, column_idx)?, value));
205                }
206            }
207        }
208        Self::try_from_sorted_entries(num_row_groups, num_columns, entries)
209    }
210
211    pub(crate) fn is_empty(&self) -> bool {
212        self.entries.is_empty()
213    }
214
215    fn key(&self, row_group_idx: usize, column_idx: usize) -> Result<ColumnChunkKey> {
216        if row_group_idx >= self.num_row_groups || column_idx >= self.num_columns {
217            return Err(ParquetError::General(format!(
218                "column chunk coordinate out of bounds: row group {row_group_idx}, column \
219                 {column_idx}; dimensions are {} by {}",
220                self.num_row_groups, self.num_columns
221            )));
222        }
223        ColumnChunkKey::try_new(row_group_idx, column_idx)
224    }
225
226    pub(crate) fn get(&self, row_group_idx: usize, column_idx: usize) -> Result<Option<&T>> {
227        let key = self.key(row_group_idx, column_idx)?;
228        let Ok(entry_idx) = self
229            .entries
230            .binary_search_by_key(&key, |(entry_key, _)| *entry_key)
231        else {
232            return Ok(None);
233        };
234        let Some((_, value)) = self.entries.get(entry_idx) else {
235            return Err(ParquetError::General(format!(
236                "column chunk binary search returned invalid entry index {entry_idx}"
237            )));
238        };
239        Ok(Some(value))
240    }
241
242    #[cfg_attr(not(test), expect(unused))]
243    pub(crate) fn iter(&self) -> impl Iterator<Item = (ColumnChunkKey, &T)> {
244        self.entries.iter().map(|(key, value)| (*key, value))
245    }
246
247    pub(crate) fn into_iter(self) -> impl Iterator<Item = (ColumnChunkKey, T)> {
248        self.entries.into_vec().into_iter()
249    }
250
251    pub(crate) fn try_into_map(self) -> Result<ColumnChunkMap<T>> {
252        let mut map = ColumnChunkMap::try_new(self.num_row_groups, self.num_columns)?;
253        for (key, value) in self.entries {
254            let (row_group_idx, column_idx) = key.coordinates();
255            map.try_insert(row_group_idx, column_idx, value)?;
256        }
257        Ok(map)
258    }
259}
260
261impl<V: HeapSize> HeapSize for ColumnChunkEntries<V> {
262    fn heap_size(&self) -> usize {
263        self.entries.len() * std::mem::size_of::<(ColumnChunkKey, V)>()
264            + self
265                .entries
266                .iter()
267                .map(|(_, value)| value.heap_size())
268                .sum::<usize>()
269    }
270}
271
272#[cfg(test)]
273mod tests {
274    use super::*;
275
276    #[test]
277    fn sparse_storage_is_sorted_and_validates_coordinates() {
278        let mut map = ColumnChunkMap::try_new(2, 3).unwrap();
279        map.try_insert(1, 2, 12).unwrap();
280        map.try_insert(0, 1, 1).unwrap();
281        let entries = map.try_freeze().unwrap();
282
283        let coordinates = entries
284            .iter()
285            .map(|(key, _)| key.coordinates())
286            .collect::<Vec<_>>();
287        assert_eq!(coordinates, vec![(0, 1), (1, 2)]);
288        assert_eq!(entries.get(0, 1).unwrap(), Some(&1));
289        assert_eq!(entries.get(0, 2).unwrap(), None);
290        assert!(entries.get(2, 0).is_err());
291        assert!(entries.get(0, 3).is_err());
292    }
293
294    #[test]
295    fn sorted_entries_preserve_sparse_coordinates() {
296        let entries = ColumnChunkEntries::try_from_sorted_entries(
297            100,
298            1_000,
299            vec![
300                (ColumnChunkKey::try_new(0, 3).unwrap(), 3_i32),
301                (ColumnChunkKey::try_new(99, 999).unwrap(), 999),
302            ],
303        )
304        .unwrap();
305        assert_eq!(entries.get(0, 3).unwrap(), Some(&3));
306        assert_eq!(entries.get(0, 2).unwrap(), None);
307        assert_eq!(entries.get(99, 999).unwrap(), Some(&999));
308        assert_eq!(
309            entries.heap_size(),
310            2 * std::mem::size_of::<(ColumnChunkKey, i32)>()
311        );
312        assert!(
313            ColumnChunkEntries::<i32>::try_from_sorted_entries(0, 0, vec![])
314                .unwrap()
315                .is_empty()
316        );
317    }
318
319    #[test]
320    fn sorted_entries_reject_invalid_coordinates_and_order() {
321        let first = ColumnChunkKey::try_new(0, 0).unwrap();
322        let second = ColumnChunkKey::try_new(1, 1).unwrap();
323        for entries in [vec![(first, 1), (first, 2)], vec![(second, 1), (first, 2)]] {
324            assert!(ColumnChunkEntries::try_from_sorted_entries(2, 2, entries).is_err());
325        }
326        assert!(ColumnChunkEntries::try_from_sorted_entries(1, 2, vec![(second, 1)]).is_err());
327        assert!(ColumnChunkEntries::try_from_sorted_entries(2, 1, vec![(second, 1)]).is_err());
328        assert!(
329            ColumnChunkEntries::<i32>::try_from_sorted_entries(i32::MAX as usize + 1, 1, vec![],)
330                .is_err()
331        );
332    }
333
334    #[test]
335    fn zero_and_invalid_dimensions() {
336        assert!(ColumnChunkMap::<()>::try_new(0, 0).is_ok());
337        assert!(ColumnChunkMap::<()>::try_new(i32::MAX as usize + 1, 1).is_err());
338        assert!(ColumnChunkMap::<()>::try_new(1, i32::MAX as usize + 1).is_err());
339    }
340
341    #[test]
342    fn insertion_replaces_existing_value_without_growing() {
343        let mut map = ColumnChunkMap::try_new(1, 1).unwrap();
344        assert_eq!(map.try_insert(0, 0, "first").unwrap(), None);
345        let capacity = map.entries.capacity();
346
347        assert_eq!(map.try_insert(0, 0, "replacement").unwrap(), Some("first"));
348        assert_eq!(map.entries.len(), 1);
349        assert_eq!(map.entries.capacity(), capacity);
350    }
351
352    #[test]
353    fn freeze_and_thaw_preserve_entries() {
354        let mut map = ColumnChunkMap::try_new(2, 2).unwrap();
355        map.try_insert(1, 0, 3).unwrap();
356        let expected_entries = map.try_freeze().unwrap();
357
358        let mut map = ColumnChunkMap::try_new(2, 2).unwrap();
359        map.try_insert(1, 0, 3).unwrap();
360        let entries = map.try_freeze().unwrap();
361        let thawed = entries.try_into_map().unwrap();
362        assert_eq!(thawed.try_freeze().unwrap(), expected_entries);
363    }
364
365    #[test]
366    fn frozen_heap_size_uses_packed_key_layout() {
367        let entries = ColumnChunkEntries::try_from_rows(vec![vec![Some(1_i32)]]).unwrap();
368        assert_eq!(
369            entries.heap_size(),
370            std::mem::size_of::<(ColumnChunkKey, i32)>()
371        );
372    }
373}