lance-format / lance-format/lance

Implement ByteStreamSplit as a layer of encoding

Open
#4,258 1 comment 0 reactions 1 assignee View on GitHub

@Xuanwo is already working on this.

Since Jul 18, 2025.

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

Description

So this works, but there might be a simpler way to implement this. I often try to think of these encodings running layers (or maybe the right term is cascading). For example, here is the diagram from the BtrBlocks paper:

image

What you've done here is you've fused the byte stream split encoder and the ValueEncoder (which has the chunking logic) into a single encoding (reimplementing the chunking logic). You could simplify it by allowing the downstream encoder to be provided by the caller. For example:

#[derive(Debug, Clone)]
pub struct ByteStreamSplitEncoderMiniBlock {
  bits_per_value: usize,
  inner: Box<dyn MiniBlockCompressor>,
}

...

impl MiniBlockCompressor for ByteStreamSplitEncoderMiniBlock {
  fn compress(&self, page: DataBlock) -> Result<(MiniBlockCompressed, pb::ArrayEncoding)> {
    if DataBlock::FixedWidth(data) = page {
      // Do the actual byte stream split on the data buffer and make a new data buffer (no chunking)
      let split_buffer: Buffer = split_values(data.data);
      let split_data = DataBlock::FixedWidth(FixedWidthDataBlock {
        data: split_buffer,
        bits_per_value: data.bits_per_value,
        num_values: data.num_values,
        block_info: BlockInfo::new()
      };
      let (compressed, descr) = self.inner.compress(split_data);
      let wrapped_descr = ProtobufUtils::byte_stream_split(descr);
      Ok((compressed, wrapped_descr))
    } else {
      // error
    }
  }
}

This also makes it possible to do things like BSS -> Bitpacking + delta or some other layers of encoding (I don't know if that ever makes sense or we would need to do that).

Originally posted by @westonpace in https://github.com/lancedb/lance/pull/4236#discussion_r2215998795

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.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.