lance-format / lance-format/lance
Simpler and more efficient block bitpacking
@Xuanwo is already working on this.
Since Sep 15, 2025.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
The block compressor / decompressor for bitpacking could be simplified. Right now we use inline bitpacking if there are fewer than 1024 values and out-of-line bitpacking if there are more than 1024 values. However, we could change either one to work for both cases.
Inline bitpacking can't work today because it expects there to be at most 1024 values. This is because it wants to read the compressed bit width from the start of the buffer and then apply that to the next 1024 values. This works well for mini-block since we've created a mini-block for each 1024 values and we decompress a block at a time. To fix inline bitpacking we would need to make an unpack method that handles more than 1024 values. It would work something like this...
while not_at_end {
let compressed_bit_width = read_from_buffer_start(buffer);
unpack(buffer, output);
buffer += bytes_in_chunk;
}
Out-of-line bitpacking works today but the last block may be inefficiently compressed. This is because the last block might not have a full 1024 values. Currently we always solve this by padding with zeros and then bitpacking. For very small last blocks this is inefficient. For example, if I have 1025 values then the last block of size 1 is probably not going to benefit from bitpacking. Instead we should just encode the last block as-is. Then, during decompression, we can look at the size of the last block. If it equals T * num_values_in_last_block we can assume it is just uncompressed data and skip the unpacking.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.