kuzu
kuzu copied to clipboard
Integer Bitpacking extensions
From the extra TODOs in #2004, ordered roughly from simplest to most complicated.
- [x] Var List offsets can be bitpacked
- [x] InternalIDs can be bitpacked
- [x] INT16 and INT8 bitpacking
- [x] Small reads/writes to bitpacked data could be optimized to work on individual data instead of relying on packing/unpacking a 32-value chunk to a temporary array.
- [x] Extra values could be packed into the end of each page when the page does not divide evenly into 32-value chunks.
- [ ] SIMD bitpacking
Notes
InternalIDs
Stored as offset_t (uint64_t), but would need an extra layer to handle widening the results into the internal_id_t struct. This could cause significant slowdowns when decompressing since we wouldn't be able to use the fast mass decompression functions directly. Since the current random access implementation is not very efficient (unpacks 32 values to get one) it would probably be more performant to unpack to a temporary buffer and then copy the values into the value vector
Filling the extra space at the end of each page
This would be trivial to implement when direct reads and writes of bitpacked data is implemented.
SIMD
Mostly complicated due to handling compiler support.
Benchmarks
It would also be helpful to set up some small benchmarks (maybe using google benchmark, essentially what I did when comparing implementations at the start) so that we can do some fast comparisons of the compression/decompression speed without having to deal with the overhead of the rest of the system (not that such integrated benchmarks aren't also useful).