abedegno opened a new issue, #12366:
URL: https://github.com/apache/arrow-rs/issues/12366

   
   **Is your feature request related to a problem or challenge?**
   
   When a `RowSelection` skips rows and the file has an offset index, 
`GenericColumnReader::skip_records` skips one data
   page per loop turn. Each turn calls `PageReader::peek_next_page` and then 
`PageReader::skip_next_page`, both through
   `Box<dyn PageReader>`.
   
   With 1,048,576-row row groups written with 512-row pages, a column chunk has 
2,048 pages. A selection that reads a
   few rows from the middle of a row group, such as a point lookup, walks about 
2,000 page locations in every projected
   column. The offset index already gives the first row of every page, so the 
reader could find the last page that fits
   with one binary search instead.
   
   In my own needle search workload (parquet 59.3.2, vendored), this page walk 
was 7.6% of CPU.
   
   **Describe the solution you'd like**
   
   - Add a provided method to `PageReader`, `skip_pages_within(max_rows) -> 
Result<usize>`, that skips whole data pages
     holding at most `max_rows` rows in total and returns the rows skipped. The 
default returns `Ok(0)`, so other page
     readers behave exactly as before.
   - Implement it for `SerializedPageReader` when it has page locations and no 
pending dictionary page, using
     `partition_point` over `first_row_index`. The last page ends at the row 
group's row count.
   - Call it from `skip_records` at each page boundary, then continue with the 
existing loop for dictionary pages,
     partial pages and pages without a known row count.
   
   A draft implementation with a new benchmark (`arrow_reader_page_skip`) takes 
`page_index/needle` from 56.6 µs to
   15.9 µs on a dedicated-CPU Linux VM, and `page_index/sparse` from 214 µs to 
139 µs. The case that could get slower
   (`short_runs`, where no whole page fits) did not: 8.0 ms before, 7.7 ms 
after.
   
   A follow-up would stop cloning the `Vec<PageLocation>` from the page index 
into each `SerializedPageReader`, which
   is the subject of the existing `TODO(ets)` in 
`SerializedRowGroupReader::get_column_page_reader`.
   
   **Describe alternatives you've considered**
   
   - Change `skip_next_page` to skip several pages. It takes no row budget and 
callers rely on it moving exactly one
     page, so this would change its meaning for every implementation.
   - Expose the page locations from `PageReader` and do the binary search in 
`GenericColumnReader`. This publishes more
     of the reader's internals for the same result.
   - Keep the loop and make each turn cheaper. The cost is the number of turns, 
so this cannot remove it.
   
   **Additional context**
   
   Selections that never cover a whole page (e.g. read 100 rows, skip 300, with 
512-row pages) gain nothing and pay one
   extra call per page boundary. The draft returns after one comparison in that 
case, and the benchmark has a
   `short_runs` case to measure it.
   
   **Willingness to contribute**
   
   I plan to contribute to this feature independently.
   


-- 
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]

Reply via email to