Repository navigation
Proposal: 128-bit bitpacking for Decimal128 in Lance 2.3 #10935
Replies: 3 comments 3 replies
|
cc @Xuanwo @westonpace @wjones127 @BubbleCal for the format side, and @kamronis for open question 2, since #9603 added the direct inline-bitpacking decode path that 128-bit pages currently skip. I'd like to hear your thoughts on the open questions before I mark #10934 ready for review. |
FWIW Arrow supports decimal32 and decimal64, so another good solution is to support those and make sure we bitpack those. Relatedly, I think we eventually want to have a single Decimal data type, and the 32/64/128/256 bit width is just decided based on the scale and precision once and isn't a user concern. See #5864 and #7073 |
|
I think adding direct-to-output decoding as a follow-up is good. The generic path gives us a working decoder for #6858, and the 128-bit layout needs more than a new match arm in #9603. We just have to make sure the follow-up tests partial reads and benchmarks are showing perf increase on real Decimal128 data. |
Uh oh!
There was an error while loading. Please reload this page.
Summary
Lance bitpacks 8, 16, 32 and 64-bit values today, but never 128-bit ones. A
Decimal128column therefore stores 16 bytes per value even when every value fits in 24 bits, which is the common case for money and quantity columns such asdecimal(7,2). This proposal adds 128-bit bitpacking to the unstable 2.3 format. It needs no protobuf change:InlineBitpackingandOutOfLineBitpackingalready carryuncompressed_bits_per_value, and this defines what a value of 128 means. The implementation is in #6858.Why
I measured on an Apple M2 Max with both sides writing Lance 2.3. The baseline is current main, which stores
Decimal128values unpacked; the other side is #6858. Every run read back the same column sums.On TPC-DS SF=100
store_sales(288M rows), rewriting the table to 2.3 shrinks it from 33.8 GiB to 14.9 GiB. A local scan that sums sixdecimal(7,2)columns takes 1.85 s instead of 2.04 s.On 5M rows × 6
decimal(7,2)columns of synthetic data:Times are warm means over 4 runs, except MinIO reads, which are medians of 20 because the baseline varied between 140 and 480 ms. These end-to-end runs were taken before the 65 to 127 layout change described below. None of this data has a value of 2^64 or more, so it never reaches that range.
The CPU cost depends on the packed width. These are single-column in-memory benchmarks (5M values, every block pinned to one width), compared with main encoding and decoding the same column unpacked. Each range covers two runs:
wThe baseline itself moved by up to 9% between runs, which accounts for most of the spread at
w = 128. Decode stays within about 15% of unpacked values at every measured width, and encode is faster than unpacked at the three narrower ones. Earlier comments on #6858 quoted a 2.5x decode slowdown for widths below 128; those numbers were taken before the branch was merged with current main and before the 65 to 127 layout described below.Format
A 128-bit value is treated as an unsigned 128-bit integer, so a negative decimal has its top bit set. Every value in a packed block of 1024 values is below
2^w, where the packed widthwis from 0 to 128. A packed block isw * 128bytes, andwalone determines its layout:wkbits of each value in the transposed (FastLanes) layout that 32 and 64-bit bitpacking use, withk = 32whenwis at most 32 andk = 64otherwise.u64words, followed by the highw - 64bits packed exactly as 64-bit bitpacking packs them at widthw - 64.InlineBitpacking) start withw(0 to 128) as a little-endian 128-bit header, followed by the packed block. Each chunk picks its own width, and a final short chunk is zero-padded.OutOfLineBitpacking, used for dictionary items) use the encoding's single width for every complete block. The tail is padded or stored raw by the same rule as for narrower widths.Decimal128:FixedSizeBinary(16)andInterval(MonthDayNano)go through the same selector. Random values such as UUIDs need all 128 bits, so the writer leaves them unpacked.Compatibility
unimplemented!panic. 2.3 makes no compatibility promise, so I don't think this blocks anything. I'm happy to backport a change that turns the panic into an error if people want one.Design choices
The width selects the layout, and there is no separate kernel id in the format. The chunk header already carries the width and each width range has exactly one layout, so a second field could only disagree with it. The downside is that the table is fixed. Moving a width range to a different kernel later would change how existing files decode, so it would need a format change.
Inline and out-of-line bitpacking share one table. An earlier revision used a plain bit stream for every out-of-line width, which gave the same width two layouts in the same format. With one table the spec describes the layout once, and dictionary items decode through the same SIMD kernels as data pages.
Every range reuses the existing 32 and 64-bit layouts, so a reader that already decodes 64-bit bitpacking needs no new kernel, and the encoder and decoder use the FastLanes kernels Lance already ships. The 65 to 127 range splits each value into halves: the low 64 bits are stored as-is, because a width above 64 keeps all of them anyway, and only the high
w - 64bits are packed. An earlier revision packed this range as a plain 128-bit bit stream with a scalar kernel; in a kernel-only benchmark atw = 100, the split layout unpacks a block about 5x faster and packs it about 3x faster.Open questions
w = 128and is stored raw. A column with scattered negative values, such as a profit column, pays for this. Zigzag encoding or frame-of-reference would fix it, but either one adds a transform in front of the bit layout. Should that go into 2.3 before the format stabilizes, or be a separate encoding later?Next steps
The spec text is in #10934, a draft PR that only changes the Bitpacking section of
encoding.md. It also writes down the transposed layout itself. The docs have never described it, even for 8 to 64-bit values, and the 128-bit table can't be implemented without it. That part documents the existing 2.1 layout and changes nothing on disk. Following the format-change process, the vote happens on that PR. I'll mark it ready for review once the open questions above are settled, and rebase #6858 on it as the implementation. I'd like to hear your thoughts before then.All reactions