Skip to content

Support load page index metadata with specified column id instead of all columns #7582

Closed

Description

@zhuqi-lucas

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.

Details:
apache/datafusion#16200

Describe the solution you'd like

Describe alternatives you've considered

Additional context

Activity

  1. zhuqi-lucas commented on Jun 1, 2025

    @zhuqi-lucas
    ContributorAuthor

    take

  2. alamb commented on Jun 2, 2025

    @alamb
    Contributor
  3. etseidl commented on Sep 15, 2026

    @etseidl
    Contributor

    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).

    rg: 10 col:      1/10 dense   23950 sparse    2858
    rg: 10 col:      5/10 dense   25990 sparse   14194
    rg: 10 col:     10/10 dense   28540 sparse   28364
    rg: 10 col:     1/100 dense  232750 sparse    2858
    rg: 10 col:     5/100 dense  234790 sparse   14194
    rg: 10 col:    10/100 dense  237340 sparse   28364
    rg: 10 col:    50/100 dense  257740 sparse  141724
    rg: 10 col:    75/100 dense  270490 sparse  212574
    rg: 10 col:   100/100 dense  283240 sparse  283424
    rg: 10 col:   10/1000 dense 2325340 sparse   28364
    rg: 10 col:   50/1000 dense 2345740 sparse  141724
    rg: 10 col:  100/1000 dense 2371240 sparse  283424
    rg: 10 col:  500/1000 dense 2575240 sparse 1417024
    rg: 10 col:  750/1000 dense 2702740 sparse 2125524
    rg: 10 col: 1000/1000 dense 2830240 sparse 2834024
    

    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.

         Running benches/metadata.rs (target/release/deps/metadata-dbd53e9bb7806fb9)
    open(default)           time:   [10.714 µs 10.845 µs 10.988 µs]
    open(page index)        time:   [172.16 µs 174.69 µs 177.94 µs]
    open(page index reduced columns)
                            time:   [28.273 µs 28.630 µs 29.043 µs]
    

    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.

    Thanks!

    cc @jhorstmann

  4. adriangb commented on Sep 15, 2026

    @adriangb
    Contributor

    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.

  5. etseidl commented on Sep 16, 2026

    @etseidl
    Contributor

    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).

    page_index_dense(10,1/100)           1.00      6.4±0.20ns        ? ?/sec
    ...
    page_index_dense(10,7500/10000)      1.00      6.4±0.18ns        ? ?/sec
    page_index_sparse(10,1/100)          1.00      9.0±0.20ns        ? ?/sec
    page_index_sparse(10,10/100)         1.00     15.7±0.44ns        ? ?/sec
    page_index_sparse(10,10/1000)        1.00     15.6±0.37ns        ? ?/sec
    page_index_sparse(10,10/10000)       1.00     15.7±0.41ns        ? ?/sec
    page_index_sparse(10,100/100)        1.00      7.6±0.15ns        ? ?/sec
    page_index_sparse(10,100/1000)       1.00     27.0±0.52ns        ? ?/sec
    page_index_sparse(10,100/10000)      1.00     26.9±0.38ns        ? ?/sec
    page_index_sparse(10,1000/1000)      1.00      7.7±0.20ns        ? ?/sec
    page_index_sparse(10,1000/10000)     1.00     39.2±0.66ns        ? ?/sec
    page_index_sparse(10,10000/10000)    1.00      7.7±0.21ns        ? ?/sec
    page_index_sparse(10,5/100)          1.00     12.7±0.28ns        ? ?/sec
    page_index_sparse(10,50/100)         1.00     22.9±0.54ns        ? ?/sec
    page_index_sparse(10,50/1000)        1.00     22.8±0.40ns        ? ?/sec
    page_index_sparse(10,50/10000)       1.00     22.8±0.43ns        ? ?/sec
    page_index_sparse(10,500/1000)       1.00     35.7±0.59ns        ? ?/sec
    page_index_sparse(10,500/10000)      1.00     35.6±0.53ns        ? ?/sec
    page_index_sparse(10,5000/10000)     1.00     54.9±1.29ns        ? ?/sec
    page_index_sparse(10,75/100)         1.00     27.0±0.72ns        ? ?/sec
    page_index_sparse(10,750/1000)       1.00     39.2±0.39ns        ? ?/sec
    page_index_sparse(10,750/10000)      1.00     39.2±0.51ns        ? ?/sec
    page_index_sparse(10,7500/10000)     1.00     54.9±1.23ns        ? ?/sec
    

    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

    rg: 10 col:    10/10000 dense 23205340 sparse    28364
    rg: 10 col:    50/10000 dense 23225740 sparse   141724
    rg: 10 col:   100/10000 dense 23251240 sparse   283424
    rg: 10 col:   500/10000 dense 23455240 sparse  1417024
    rg: 10 col:   750/10000 dense 23582740 sparse  2125524
    rg: 10 col:  1000/10000 dense 23710240 sparse  2834024
    rg: 10 col:  5000/10000 dense 25750240 sparse 14170024
    rg: 10 col:  7500/10000 dense 27025240 sparse 21255024
    rg: 10 col: 10000/10000 dense 28300240 sparse 28300000
    

    I think this argues heavily for simply replacing the dense Vec<Vec<Option<T>>> with Grid<T>.

  6. alamb commented on Sep 21, 2026

    @alamb
    Contributor

    The grid approach sounds good to me . Is the PR ready to go? Or do we need to revive it?

  7. etseidl commented on Sep 21, 2026

    @etseidl
    Contributor

    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.

  8. alamb commented on Sep 21, 2026

    @alamb
    Contributor

    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

  9. etseidl commented on Nov 12, 2026

    @etseidl
    Contributor

    I've been hung with my own rope 🤣 (#12163)

    @zhuqi-lucas I've removed your assignment so my agent will work on #11475.

  10. added a commit that references this issue on Nov 13, 2026
    9cd60eb
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions