apache / apache/arrow-rs

API for filtering / evaluation directly on encoded data

Open
#8,842 5 comments 8 reactions 1 assignee Claimed by @sdf-jkl View on GitHub
enhancement parquet
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 18h
Merged PRs (30d)
169

Description

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
The idea of [executing directly on "compressed" (encoded) data](https://www.cs.umd.edu/~abadi/papers/abadisigmod06.pdf) is a well known technique in the academic columnar store literature. The Parquet format currently supports several different [encodings](https://github.com/apache/parquet-format/blob/master/Encodings.md) such as:
- Plain
- Dictionary (and hybrid)
- RLE/Bitpacked
- DeltaBinaryPacked
- DeltaByteArray
- ByteStreamSplit

The current Rust Parquet reader supports evaluating predicates during the scan via the [ArrowReaderBuilder::with_row_filter](https://docs.rs/parquet/latest/parquet/arrow/arrow_reader/struct.ArrowReaderBuilder.html#method.with_row_filter). However, the current [RowFilter](https://docs.rs/parquet/latest/parquet/arrow/arrow_reader/struct.RowFilter.html) API only permits evaluation on Arrow arrays, aka **after** decompression and decoding.

It would be interesting to consider supporting evaluating predicates directly on parquet encoded data, to avoid decode costs when unnecessary -- for example when doing "needle in the haystack" type queries that filter out almost all rows

As the community considers [adding more encodings], such as ALP and FSST that are even more amenable to encoded operation, the benefit of such an API will increase.

**Describe the solution you'd like**
I would like some way to evaluate predicates directly on the encoded Parquet data

**Describe alternatives you've considered**

One potential thing we could do is extend the existing RowFilter API so different implementations could be provided for different encodings
```rust
// add predicates evaluated on (decoded) Arrow arrays
let filter = RowFilter::new(arrow_predicates)
// add specializations that can evaluate directly on RLE encoded data
// if the data is not RLE encoded, fall back to the arrow ones
.with_rle_predicates(...)
```

We would have to do some more experiments to know what the API for RLE (and similar) predicates should be

**Additional context**

The Vortex file implementation seems to be heading towards adding their own Expression implementation for common expressions and then providing the evaluation implementation too

For example, see how VortexExpr::evaluate looks (it has all the knowledge of the types, etc)
https://docs.rs/vortex-expr/0.54.0/vortex_expr/trait.VortexExpr.html#method.evaluate

This might be necessary if Parquet ends up with generic cascaded encodings

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.