etseidl commented on issue #7582: URL: https://github.com/apache/arrow-rs/issues/7582#issuecomment-5689726600
Following up here with some experiments. What I've been doing can be seen in this [diff](https://github.com/apache/arrow-rs/compare/main...etseidl:arrow-rs:sparse_pi1). 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 -- 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]
