Support reverse order for Parquet streams
- Dominant language
- Rust
- Stars
- 3.6k
- Forks
- 1.3k
- Avg merge
- 2d 14h
- Merged PRs (30d)
- 167
Description
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
I have been evaluating Parquet and Arrow Datafusion for use at my company. While testing out Datafusion I noticed that queries like `SELECT * FROM table ORDER BY field DESC LIMIT n` causes it to read the whole file, even though the existing data was sorted in ascending order.
Upon further investigation, this made sense because the Parquet reader can't return data in any order except the ordering that it was stored in. But this makes it hard to minimize the amount of work done while executing certain queries, e.g. get the last N events sorted by time before a certain known timestamp (especially for small N).
**Describe the solution you'd like**
A new function added to `ArrowReaderBuilder`, something like this:
```rust
pub fn with_reverse(self, reverse: bool) -> Self {
Self { reverse, ..self }
}
```
which would cause the data to be streamed in the reverse of its native order as well as individual record batches being reversed, respecting limits all the while. E.g. `with_limit(100).with_reverse(true)` would return the last 100 rows satisfying the query.
Setting `with_reverse` should probably not affect the order of the row groups, since there are no guarantees on the organization of Parquet row groups anyway.
**Describe alternatives you've considered**
After realizing that implementing this feature would be non-trivial, I tried implementing my own querying code by fetching a whole row group at a time, using the existing query builder, then reversing the entire row group. See [here](https://github.com/suremarc/polygon-arrow-rs/blob/master/src/main.rs). It works, but it has to deserialize the entire row group, even though the limit might be 1. A more sophisticated implementation would deserialize only the minimum number of pages before stopping early, as the existing code in the Parquet library does.
If the library had lower-level API it might be possible to support specific use cases like reverse ordering without overloading the existing logic (which is already quite complex by the looks of it). However I am not sure what such an API would look like.
**Additional context**
Contributor guide
Research direction
Start at the ArrowReaderBuilder entry point and trace the existing query builder's limit and streaming behavior through the Parquet reader. Check how record batches and row groups are currently ordered, then define tests for reverse batches, limits, and the stated row-group behavior. Done means the requested reverse-order behavior is covered without changing row-group ordering guarantees.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100