You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Support load page index metadata with specified column id instead of all columns #7582
Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Currently, we only support load page index metadata of all columns, this issue will add support for supporting load page index metadata with specified column id. Which will benefit for apache datafusion, we can choose which column page index metadata to load, it can improve the performance.
Following up here with some experiments. What I've been doing can be seen in this diff. I didn't open a PR since we continue to drown in them.
Anyway, I've pushed forward on a few fronts. The first is returning to one of my old ideas of using the PageIndexPolicy to communicate down into the metadata parser which rows and columns are wanted for the indexes. I've added three new variants OnlyColumns, OnlyRowGroups, and OnlyRowGroupsColumns. These keep a sorted set of column or row group indices (why they need to be sorted will become clear soon).
The next change is to rework PageIndex to allow for different storage strategies for the indexes. I ran with @adriangb's idea of a Grid<T> composed of Keep sets for the row group and column indices. The Keep uses sorted indices to use a binary search to map a given index to a position within the kept indices. I wrapped the old Vec<Vec<Option<Index>>> and the new Grid<Index> in a new PageIndexStorage<T> enum, with Dense and Sparse variants. This allows for pretty memory efficient storage, but does impact the metadata memory size test a bit due to the new enum.
To compare between the Dense and Sparse memory footprints I wrote a quick-and-dirty test to print out some different configurations. All tests are 10 row groups, with varying fractions of columns populated. The sparse formulation is almost always smaller in footprint, even up to keeping 100% of columns. (An earlier version that used nested HashMaps got larger at around 50% populated).
Given the results above, I think we might just want to switch over to the Grid formulation for everything. There's an optimization in the Keep implementation for the "keep all indices" case...we could opt to use that formulation when the provided keep set is over a certain percentage of row groups or columns.
I also added a bench to benches/metadata.rs to show the speed up. The "reduced columns" keeps 3 out of the 12 columns in the schema.
Also included is a test @alamb requested (in parquet/tests/arrow_reader/custom_page_index_provider.rs) that tests reading a file with a custom index provider while doing row selection.
I also played with skipping the PageIndexStorage and instead doing a SparsePageIndex with it's own builder, but that got to be a lot of code, and one nice feature of the variant here is one can use the dense storage for one index, and sparse for the other (although, again, given that sparse is looking pretty good, this might be moot).
PTAL when you have a chance and let me know if you think any of these ideas are worth pursuing.
I'd be excited to see that get across the line and would be happy to help review a sparse index implementation.
We can work behind the trait and then if numbers show we should always use sparse or a simple heuristic makes it always win we can remove the trait down the road.
Another data point. I've added a bench of fetching the column index from various shapes of PageIndex. The results are not surprising. The dense form has O(1) lookup behavior, and the sparse is O(log(n)) where n is the number of kept indices. For the special case of n == span we fall back to O(1).
The grid approach sounds good to me . Is the PR ready to go? Or do we need to revive it?
I'm currently breaking it up into smaller chunks. I've got the row group/column selection piece ready to go (but it's stacked on #11031 and #11132), and then can add the Grid piece after. And I think none of it will involve breaking changes.
One thing I though of while working on this is that the Keep/Grid approach could also be used to selectively populate the metadata itself. We could keep the in-file indexing for row groups and columns, but only store the subset of metadata needed for a given query.
One thing I though of while working on this is that the Keep/Grid approach could also be used to selectively populate the metadata itself. We could keep the in-file indexing for row groups and columns, but only store the subset of metadata needed for a given query.
This is phase three fanciness -- I love it
Whereby phase three is my three level model of optimization (initial implementation --> rewrite to be good --> rewrite to be really good, but also can't be made any better without a rearchitecture)
I think we are getting near phase three with some parts of this crate
Activity
zhuqi-lucas commentedon Jun 1, 2025
take
alamb commentedon Jun 2, 2025
FYI @adriangb
Parquet: Make page index decoders public (#10899)
Parquet: Make page index decoders public (apache#10899)
Add `PageIndexBuilder` and `PageIndexProvider` for Parquet page index…
etseidl commentedon Sep 15, 2026
Following up here with some experiments. What I've been doing can be seen in this diff. I didn't open a PR since we continue to drown in them.
Anyway, I've pushed forward on a few fronts. The first is returning to one of my old ideas of using the
PageIndexPolicyto communicate down into the metadata parser which rows and columns are wanted for the indexes. I've added three new variantsOnlyColumns,OnlyRowGroups, andOnlyRowGroupsColumns. These keep a sorted set of column or row group indices (why they need to be sorted will become clear soon).The next change is to rework
PageIndexto allow for different storage strategies for the indexes. I ran with @adriangb's idea of aGrid<T>composed ofKeepsets for the row group and column indices. TheKeepuses sorted indices to use a binary search to map a given index to a position within the kept indices. I wrapped the oldVec<Vec<Option<Index>>>and the newGrid<Index>in a newPageIndexStorage<T>enum, withDenseandSparsevariants. This allows for pretty memory efficient storage, but does impact the metadata memory size test a bit due to the new enum.To compare between the
DenseandSparsememory footprints I wrote a quick-and-dirty test to print out some different configurations. All tests are 10 row groups, with varying fractions of columns populated. The sparse formulation is almost always smaller in footprint, even up to keeping 100% of columns. (An earlier version that used nested HashMaps got larger at around 50% populated).Given the results above, I think we might just want to switch over to the
Gridformulation for everything. There's an optimization in theKeepimplementation for the "keep all indices" case...we could opt to use that formulation when the provided keep set is over a certain percentage of row groups or columns.I also added a bench to
benches/metadata.rsto show the speed up. The "reduced columns" keeps 3 out of the 12 columns in the schema.Also included is a test @alamb requested (in
parquet/tests/arrow_reader/custom_page_index_provider.rs) that tests reading a file with a custom index provider while doing row selection.I also played with skipping the
PageIndexStorageand instead doing aSparsePageIndexwith it's own builder, but that got to be a lot of code, and one nice feature of the variant here is one can use the dense storage for one index, and sparse for the other (although, again, given that sparse is looking pretty good, this might be moot).PTAL when you have a chance and let me know if you think any of these ideas are worth pursuing.
Thanks!
cc @jhorstmann
adriangb commentedon Sep 15, 2026
I'd be excited to see that get across the line and would be happy to help review a sparse index implementation.
We can work behind the trait and then if numbers show we should always use sparse or a simple heuristic makes it always win we can remove the trait down the road.
etseidl commentedon Sep 16, 2026
Another data point. I've added a bench of fetching the column index from various shapes of
PageIndex. The results are not surprising. The dense form has O(1) lookup behavior, and the sparse is O(log(n)) where n is the number of kept indices. For the special case ofn == spanwe fall back to O(1).Honestly I don't think even the worst case is all that bad considering the space savings. Here's the memory use for the 10k column cases
I think this argues heavily for simply replacing the dense
Vec<Vec<Option<T>>>withGrid<T>.Parquet: Make page index decoders public (apache#10899)
Add `PageIndexBuilder` and `PageIndexProvider` for Parquet page index…
alamb commentedon Sep 21, 2026
The grid approach sounds good to me . Is the PR ready to go? Or do we need to revive it?
etseidl commentedon Sep 21, 2026
I'm currently breaking it up into smaller chunks. I've got the row group/column selection piece ready to go (but it's stacked on #11031 and #11132), and then can add the Grid piece after. And I think none of it will involve breaking changes.
One thing I though of while working on this is that the Keep/Grid approach could also be used to selectively populate the metadata itself. We could keep the in-file indexing for row groups and columns, but only store the subset of metadata needed for a given query.
Parquet: Make page index decoders public (apache#10899)
Add `PageIndexBuilder` and `PageIndexProvider` for Parquet page index…
alamb commentedon Sep 21, 2026
This is phase three fanciness -- I love it
Whereby phase three is my three level model of optimization (initial implementation --> rewrite to be good --> rewrite to be really good, but also can't be made any better without a rearchitecture)
I think we are getting near phase three with some parts of this crate
Parquet: Make page index decoders public (apache#10899)
feat: Allow for partial population of the Parquet Page Index (apache#…
feat: Add separate Parquet `PageIndex` decoder to `ParquetMetaDataPus…
etseidl commentedon Nov 12, 2026
I've been hung with my own rope 🤣 (#12163)
@zhuqi-lucas I've removed your assignment so my agent will work on #11475.
feat(parquet): Improved back-end storage for `PageIndex` (apache#11475)