Exclude sign bit from bitpacked encoding if all values are negative

[albertlockett]

In #2662 we added support for bitpacking signed integers in LanceV2. In #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
  

  lance/protos/encodings.proto

  Line 176 in 35e3862

  message Bitpacked {

• 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:
  

  lance/rust/lance-encoding/src/encodings/physical/bitpack.rs

  Line 79 in b9990d9

  fn bitpack_params_for_signed_type<T>(arr: &PrimitiveArray<T>) -> Option<BitpackParams>

• 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:
  

  lance/rust/lance-encoding/src/encodings/physical/bitpack.rs

  Lines 440 to 445 in b9990d9

  	let is_negative = is_encoded_item_negative(
  	src,
  	src_idx,
  	src_offset,
  	self.bits_per_value as usize,
  	);

[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: #2886