adriangb commented on code in PR #10784:
URL: https://github.com/apache/arrow-rs/pull/10784#discussion_r3836791268
##########
parquet/src/file/metadata/mod.rs:
##########
@@ -412,6 +412,176 @@ impl PageIndex {
None
}
}
+
+ /// Convert this `PageIndex` into a [`PageIndexBuilder`]
+ pub fn into_builder(self) -> PageIndexBuilder {
+ self.into()
+ }
+}
+
+/// Builder for constructing [`PageIndex`] structures
+///
+/// It supports:
+/// - Allocating space for indexes based on [`PageIndexPolicy`]
+/// - Populating column indexes for predicate columns (for page filtering)
+/// - Populating offset indexes for projected columns (for direct I/O)
+/// - Automatic conversion of empty structures to `None` to save memory
+pub struct PageIndexBuilder {
+ column_indexes: Option<Vec<Vec<Option<ColumnIndexMetaData>>>>,
+ offset_indexes: Option<Vec<Vec<Option<OffsetIndexMetaData>>>>,
Review Comment:
The basic idea is to have something like:
```rust
pub struct Keep { kept: Option<Arc<[u32]>>, span: u32 }
impl Keep {
pub(crate) fn new(kept: Option<Arc<[u32]>>, span: usize) -> Self { Self
{ kept, span: span as u32 } }
/// Where index `i` lives in the rectangle, if it is stored at all.
pub fn position(&self, i: usize) -> Option<usize> {
match &self.kept {
None => (i < self.span as usize).then_some(i),
Some(k) => k.binary_search(&u32::try_from(i).ok()?).ok(),
}
}
pub fn len(&self) -> usize { self.kept.as_ref().map_or(self.span as
usize, |k| k.len()) }
}
```
Where `kept` are sorted, deduped indexes or elements that are set in the
container.
So `[None, None, Some(...), Some(...), None, Some(...)]` becomes `[2, 3, 5]`.
To check if a position is set you do a binary search.
Composing two `Keep` into a `Grid` lets you represent a mapping from row
groups x columns to a value:
```rust
struct Grid<T> { rows: Keep, cols: Keep, cells: Vec<Option<T>> }
impl Grid<T> {
fn new(rows: Keep, cols: Keep) -> Self {
let mut cells = Vec::new();
cells.resize_with(rows.len() * cols.len(), || None);
Self { rows, cols, cells }
}
fn get(&self, rg: usize, col: usize) -> Option<&T> {
let (r, c) = (self.rows.position(rg)?, self.cols.position(col)?);
self.cells[r * self.cols.len() + c].as_ref()
}
}
```
And so you end up with:
```rust
pub struct PageIndexBuilder {
column_indexes: Option<Grid<ColumnIndexMetaData>>,
offset_indexes: Option<Grid<OffsetIndexMetaData>>,
}
```
We'd probably have to test different strategies. There's going to be
tradeoffs depending on the number of elements in each dimension, the sparsity,
build time performance vs. performance on each probe, etc.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
