lance-format / lance-format/lance

Revisit layered ByteStreamSplit design for miniblock encoders

Open
#5,135 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-encoding enhancement
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

While experimenting with treating ByteStreamSplit (BSS) as a reusable “layer” that wraps other miniblock encoders (RLE, bitpacking, etc.), we discovered a fundamental flaw in the current architecture: BSS rewrites value bytes into fixed 2^k-sized chunks, but it hands the entire rewritten buffer to the inner encoder without exposing those chunk boundaries. Any inner encoder that applies its own chunking (the norm for RLE/bitpack) will cut the BSS-reordered data at different offsets. On read-back, BSS attempts to invert the transform using the inner chunk sizes, so chunks that start in the middle of BSS’s layout are decoded with the wrong byte streams and silently corrupt the values.

In short, “BSS → RLE/bitpack” is unsafe today because the two layers disagree on chunk layout, and the current MiniBlockCompressed format does not capture the additional ordering information needed to reconcile them. Fixing this requires a larger design:

  • Give miniblock encoders a way to accept and honor externally provided chunk plans (or expose their own plans for upstream transforms).
  • Perform length-preserving transforms (BSS, delta, xor, …) per-chunk, using the same chunk boundaries that the downstream encoder will encode.
  • Decode in reverse order using the recorded chunk metadata.

Because this change touches core traits (MiniBlockCompressor), multiple encoder implementations, and potentially new helpers for transform layers, we are postponing the effort.

This issue documents the root problem so we can revisit the layered pipeline design later, once we are ready to refactor chunk planning/coordination across transform and compression layers.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the MiniBlockCompressor traits, the RLE and bitpacking encoders, and the MiniBlockCompressed format described in the issue. Trace how ByteStreamSplit rewrites buffers and how chunk sizes are used during decoding. Done means the layered pipeline has coordinated chunk plans and enough recorded metadata to reverse the transforms without corruption.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.