Exclude sign bit from bitpacked encoding if all values are negative

[albertlockett]

In https://github.com/lancedb/lance/pull/2662 we added support for bitpacking signed integers in LanceV2. In https://github.com/lancedb/lance/pull/2696, an optimization was made to exclude the sign bit if all the values for a signed type are positive.

We can make a further optimization to exclude the sign bit if all the values are negative.

The way to do this could be to:

• change the Bitpacked encoding proto message to have a flag indicating all the values are negative https://github.com/lancedb/lance/blob/35e38624b91a17c5202f38bb587d8b432914dd58/protos/encodings.proto#L176
• In bitpack_params_for_signed_type add logic to determine if all values are negative, and if so, don't add the sign bit to the number of bits. We can also modify the return type BitpackParams as suggested here: https://github.com/lancedb/lance/blob/b9990d935b0c68ca7149ed8efe45d2f4ee3d9249/rust/lance-encoding/src/encodings/physical/bitpack.rs#L79
• In the decoder, if all the bits are negative then determine this from the field on the encoding proto-message instead of checking the MSB of the encoded value like we do here: https://github.com/lancedb/lance/blob/b9990d935b0c68ca7149ed8efe45d2f4ee3d9249/rust/lance-encoding/src/encodings/physical/bitpack.rs#L440-L445

[thinh2]

Hi, I want to tackle this issue.

[westonpace]

Hi, I want to tackle this issue.

Great. I don't think anyone is actively working on this so feel free to create a PR.

[albertlockett]

Thanks @thinh2! If you have any questions I'm happy to help. I can also be reached on our discord (my username on there is nbtel).

[thinh2]

@westonpace @albertlockett

I think there is something wrong with the test_bitpack_primitive function.

I tried to set breakpoint inside the bitpack_params_for_signed_type<T> function and run the test_bitpack_primitive, the program doesn't stop at bitpack_params_for_signed_type.

The same happens for BitpackedPageDecoder.decode . Does it mean that test_bitpack_primitive doesn't use the bitpack encode/decode function ?

[westonpace]

The same happens for BitpackedPageDecoder.decode . Does it mean that test_bitpack_primitive doesn't use the bitpack encode/decode function ?

I'm pretty sure, at one point, it did not. We switched from guarding bitpacking with an environment variable (LANCE_USE_BITPACKING) to guarding bitpacking with the version (2.1) and the tests didn't get switched over. I ran into this at one point and I can't remember if my fix for it ever got merged or is still part of my in-progress PRs. I will check.

Also, in related news, @broccoliSpicy has been working on bitpacking as well, to try and utilize the pack/unpack routines in the fastlanes crate: https://github.com/lancedb/lance/pull/2886

[thinh2]

Hi @westonpace, how can I mitigate the test issue mentioned above ? have you found the fix for the test issue mention above?

[broccoliSpicy]

I tried to set breakpoint inside the bitpack_params_for_signed_type<T> function and run the test_bitpack_primitive, the program doesn't stop at bitpack_params_for_signed_type.

The same happens for BitpackedPageDecoder.decode . Does it mean that test_bitpack_primitive doesn't use the bitpack encode/decode function ?

yeah, in a recent PR cleaning environmental variables, some encodings have been disabled.

to enable bitpacking, you can do something similar to this in the choose_array_encoder function:

https://github.com/broccoliSpicy/lance/blob/697af4a88308df456a42a382edd688bf0ea9a3bd/rust/lance-encoding/src/encoder.rs#L340

            DataType::UInt8 | DataType::UInt16 | DataType::UInt32 | DataType::UInt64 => {
                if version >= LanceFileVersion::V2_1 {
                    let compressed_bit_width = compute_compressed_bit_width_for_non_neg(arrays);
                    Ok(Box::new(BitpackedForNonNegArrayEncoder::new(
                        compressed_bit_width as usize,
                        data_type.clone(),
                    )))
                } else {
                    Ok(Box::new(BasicEncoder::new(Box::new(
                        ValueEncoder::default(),
                    ))))
                }
            }

            // for signed integers, I intend to make it a cascaded encoding, a sparse array for the negative values and very wide(bit-width) values,
            // then a bitpacked array for the narrow(bit-width) values, I need `BitpackedForNeg` to be merged first
            DataType::Int8 | DataType::Int16 | DataType::Int32 | DataType::Int64 => {
                if version >= LanceFileVersion::V2_1 {
                    let compressed_bit_width = compute_compressed_bit_width_for_non_neg(arrays);
                    Ok(Box::new(BitpackedForNonNegArrayEncoder::new(
                        compressed_bit_width as usize,
                        data_type.clone(),
                    )))
                } else {
                    Ok(Box::new(BasicEncoder::new(Box::new(
                        ValueEncoder::default(),
                    ))))
                }
            }

for your testing purpose, you can omit the if version >= LanceFileVersion::V2_1 line, to use bitpack encoding, you can change the BitpackedForNonNegArrayEncoder to BitpackEncoder.

[thinh2]

Hi @broccoliSpicy, thanks for your help.

After integrating the code above, my test can use bitpack scheme. However, the test_bitpack_primitive keep failing. I tried to use the code from main branch (adding the code to enable bitpacking) and the test still failed.

Do I need to update the code to enable bitpacking anywhere else ? Here is what I added to the choose_array_encoder function:

           DataType:: Int32 => {
                    let params = bitpack_params(arrays[0].as_ref()).unwrap();
                    Ok(Box::new(BitpackedArrayEncoder::new(
                        params.num_bits,
                        params.signed,
                        //params.all_negative,
                    )))
            }

Currently, the decoder can only decode the first element correctly, other elements are 0.

[broccoliSpicy]

yeah, there is a mistake in https://github.com/lancedb/lance/blob/f763d425d65186d2df862705571a93beec806847/rust/lance-encoding/src/encodings/physical/bitpack.rs#L236

which caused the behavior you described:

Currently, the decoder can only decode the first element correctly, other elements are 0.

I think you can try change this line to:

            src_idx += partial_bytes_written + to_next_byte;

and the issue you described should be fixed.

However, I think there are also other issues in the current bitpack implementation, for example, in the encode: https://github.com/lancedb/lance/blob/f763d425d65186d2df862705571a93beec806847/rust/lance-encoding/src/encodings/physical/bitpack.rs#L128-L179

the encoder might also need to handle the case when DataBlock is nullable and allnull, I think you can find some inspiration in the basic.rs's encoder to add support for nullable and allnul datablocks: https://github.com/lancedb/lance/blob/f763d425d65186d2df862705571a93beec806847/rust/lance-encoding/src/encodings/physical/basic.rs#L190-L234

[broccoliSpicy]

After integrating the code above, my test can use bitpack scheme.

actually, there might be some other issues come up after doing this kind of encoding selection, I filled a issue https://github.com/lancedb/lance/issues/2927 and I am currently trying to find a way to fix it.

[thinh2]

@broccoliSpicy I tried to integrate the fix you mentioned above, but there is an error Bitpacking only supports fixed width data blocks . Will #2927 fix it?

[broccoliSpicy]

for the error Bitpacking only supports fixed width data blocks, I think you can try add code similar to this in the bitpack's encode method: [lance/rust/lance-encoding/src/encodings/physical/basic.rs]

https://github.com/lancedb/lance/blob/f763d425d65186d2df862705571a93beec806847/rust/lance-encoding/src/encodings/physical/basic.rs#L190-L234