apache / apache/arrow-rs

Support reverse order for Parquet streams

Open
#3,922 5 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.