apache / apache/arrow-rs

Parquet: level encoding cost should be proportional to RLE output size

Open
#9,652 0 comments 0 reactions 0 assignees View on GitHub
enhancement
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.**
Very sparse columns (high null ratio) are just as expensive to write as writing dense, high-cardinality ones, even though the underlying encoding (RLE) compresses long runs of identical values into a single entry.

The cost of writing should reflect the cost of encoding: writing the same value a million times should be roughly as cheap as writing it once.

**Describe the solution you'd like**
The writer should perform per-run work instead of per-value work wherever possible. When long runs of identical definition/repetition levels are detected (as is typical for sparse columns), counting, histogram updates, and RLE encoding should all be amortized over the entire run in O(1) rather than O(n). Entirely-null columns should be an especially cheap special case

**Describe alternatives you've considered**
N/A

**Additional context**
N/A

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.