Skip to content

feat: add RLE v2 run length widths#7376

Merged
Xuanwo merged 3 commits into
mainfrom
xuanwo/rle-v2-run-length-widths
Jul 6, 2026
Merged

feat: add RLE v2 run length widths#7376
Xuanwo merged 3 commits into
mainfrom
xuanwo/rle-v2-run-length-widths

Conversation

@Xuanwo

@Xuanwo Xuanwo commented Jun 19, 2026

Copy link
Copy Markdown
Collaborator

Summary

Adds RLE v2 run-length widths so newly created datasets can write RLE pages with u16 or u32 run lengths instead of splitting every run at 255 values. The capability is recorded as a reader feature flag and is only enabled when a new dataset is created with WriteParams::enable_rle_v2; existing unflagged datasets reject attempts to turn it on mid-stream.

Closes #7327.

Benchmark

Ran on xuanwo-lance-lazy-metadata-bench with a #6941-style sorted low-cardinality asset_id workload.

workload Lance default Lance RLE2 reduction
150M rows / 5k assets / random5 value 167.36 MiB 164.57 MiB 1.67%
150M rows / 5k assets / by-asset5 value 7.62 MiB 2.03 MiB 73.34%

The first row keeps the random low-cardinality value column from the issue-like workload, which dominates total size. The second row isolates the long-run case RLE2 targets.

Validation

Validated with focused RLE2 tests and full Rust clippy before publishing.

@github-actions github-actions Bot added A-encoding Encoding, IO, file reader/writer A-format On-disk format: protos and format spec docs A-namespace Namespace impls labels Jun 19, 2026
@github-actions

Copy link
Copy Markdown
Contributor

Important

This PR touches the Lance format specification.

Substantive changes to the format specification — the .proto definitions
and the spec docs under docs/src/format/ — require a PMC vote before merge.
Minor edits such as typo fixes, wording, or formatting are excluded; use your
judgment.

If this is a meaningful format change:

  • Start a vote following the Lance community voting process.
    Format specification modifications need 3 binding +1 votes (excluding the
    proposer), held on GitHub Discussions, with a minimum voting period of 1 week.
  • Once the vote passes, link the completed vote in this PR. It should not be
    merged until the vote is linked.

@github-actions github-actions Bot added the enhancement New feature or request label Jun 19, 2026
@codecov

codecov Bot commented Jun 19, 2026

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 82.47863% with 82 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
rust/lance-encoding/src/encodings/physical/rle.rs 80.96% 60 Missing and 7 partials ⚠️
rust/lance-encoding/src/compression.rs 86.11% 8 Missing and 7 partials ⚠️

📢 Thoughts on this report? Let us know!

@Xuanwo
Xuanwo marked this pull request as ready for review June 22, 2026 13:47

@westonpace westonpace left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why are we doing this as a feature flag and not part of the 2.3 file version?

Is the goal to somehow get something out faster than a 2.3 release?

Or maybe we want to move towards a more incremental release strategy?

I don't think it's wrong, but it is different, and I am curious why the change.

@Xuanwo

Xuanwo commented Jul 6, 2026

Copy link
Copy Markdown
Collaborator Author

Why are we doing this as a feature flag and not part of the 2.3 file version?

My first thought is that the RLE v2 change is not significant enough to be worth including in v2.3. However, I agree it is better to follow the same pattern. I have updated the code.

Comment thread rust/lance-encoding/src/compression.rs
@Xuanwo
Xuanwo merged commit 06447f1 into main Jul 6, 2026
30 checks passed
@Xuanwo
Xuanwo deleted the xuanwo/rle-v2-run-length-widths branch July 6, 2026 08:15
jackye1995 added a commit that referenced this pull request Jul 9, 2026
…value count (#7708)

#7376 made the RLE miniblock decoder reject chunks whose run lengths sum
past the declared value count. The legacy (pre run-length-width)
miniblock encoder rolled back to a power-of-2 checkpoint after a run had
already crossed it, so existing files contain chunks that declare 2048
values but hold runs summing slightly more; the excess values are
re-encoded at the start of the next chunk. The legacy decoder truncated
the excess, so those files were valid when written — after #7376 they
fail to read with:

```
Invalid user input: RLE decoding overflowed expected value count: produced at least 2080, expected 2048
```

This restores the truncating behavior for miniblock decoding: clamp the
final crossing run at the declared count and ignore trailing legacy
runs, while still rejecting underflow and zero run lengths. Block
payloads have no chunk boundaries, so an overflow there can only be
corruption and remains a hard error. Current encoders emit exact chunks,
so this only changes how legacy files are read. Includes regression
tests for the legacy chunk-boundary overflow and the strict block path.

<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->
## Summary by CodeRabbit

* **Bug Fixes**
* Improved run-length (RLE) decoding to cap results to the expected
number of values, avoiding failures when runs exceed the requested
range.
* Enhanced compatibility with legacy data by clamping miniblock overflow
at chunk boundaries and ensuring decoded output matches the expected
length and values.
* Updated miniblock test coverage to reflect the new overflow semantics,
and added a regression test for boundary-crossing truncation.
* Preserved strict overflow handling for full block payloads, which
still reports an error.
<!-- end of auto-generated comment: release notes by coderabbit.ai -->
Xuanwo pushed a commit that referenced this pull request Jul 15, 2026
## Summary
- fail RLE miniblock encoding when chunk selection cannot advance
instead of returning partial buffers with the original value count
- assert that raw encoded run lengths match each declared chunk count
across U8, U16, and U32 run-length widths
- retain the exact-prefix implementation introduced in #7376; this does
not change the file format

## Context
`LANCE_MINIBLOCK_MAX_VALUES=1` is currently accepted, but a multi-value
RLE page cannot represent a non-final one-value chunk because
`log_num_values == 0` identifies the final chunk. The encoder previously
broke out of the loop and returned incomplete data while retaining the
original `num_values`.

## Test plan
- [x] `cargo test -p lance-encoding` (430 passed, 5 ignored)
- [x] `cargo fmt --all -- --check`
- [x] `cargo clippy --all --tests --benches -- -D warnings`

Made with [Cursor](https://cursor.com)

<!-- This is an auto-generated comment: release notes by coderabbit.ai
-->

## Summary by CodeRabbit

* **Bug Fixes**
* Prevented incomplete or invalid compressed data from being returned
when encoding cannot make progress.
* Improved error reporting with contextual details for encoding
failures.
  * Fixed run-length handling across the 2,048-value boundary.

* **Tests**
* Added coverage for multiple run-length widths and zero-progress
encoding scenarios.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

Co-authored-by: Cursor <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

A-encoding Encoding, IO, file reader/writer A-format On-disk format: protos and format spec docs A-namespace Namespace impls enhancement New feature or request

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Add opt-in RLE v2 run-length widths

3 participants