Small residuals, fixed-width arithmetic, and bit packing

For a sequence of integers, preserve the first value and form differences between consecutive values. A block can then choose its minimum delta as a reference and store nonnegative residuals relative to that minimum. If every delta equals the same step, all residuals are zero, requiring no residual payload bits in the ideal case. The step and framing still require representation. This is different from dictionary encoding: a steadily increasing timestamp column may have almost every absolute value distinct while its deltas remain highly predictable.

Parquet DELTA_BINARY_PACKED supports its specified INT32 and INT64 streams and uses blocks subdivided into miniblocks with their own bit widths. The block header, reference deltas, and counts establish how values are reconstructed. Actual block sizes have format constraints, so a four-number classroom example is an arithmetic illustration, not a literal valid tiny Parquet block. A reader must stop at the declared value count rather than expose padding as real rows. Byte-array delta-length and prefix encodings are related but have different layouts and supported types; their names do not make them interchangeable.

Fixed-width integers complicate the exact-arithmetic derivation. Parquet specifies two's-complement wrapping behavior for the relevant delta subtractions and inverse additions when overflow occurs. Implementations must arrange that behavior deliberately in languages where signed overflow is undefined or where integers have unbounded precision. An unsigned-domain implementation can preserve bit patterns, but must still apply the required signed interpretation at the correct stages. Simply enabling a compiler optimization and hoping signed subtraction wraps is not a portable encoding strategy.

An outlier can increase the width needed for its miniblock without forcing every value in the entire file to use that width. That adaptability trades compactness against headers, decoding branches, vectorization opportunities, and implementation complexity. Original integer-compression research shows why decoder throughput matters alongside compression ratio; do not copy historical performance numbers to a different CPU or distribution. Test boundaries near minimum and maximum representable values, negative steps, constant deltas, short final blocks, and changing miniblock widths. Round-trip tests should check exact bit patterns and declared row counts.

Sorting often reduces changes between neighbors, but delta encoding can still help unsorted data when differences have a narrow local distribution. Conversely, a monotone sequence with wildly varying gaps may compress less effectively than expected. Inspect actual encoded pages and decode cost with representative gaps, nulls, and groups. Nulls are carried through structural information rather than invented integer values in the nonnull stream. Preserve the relationship between that stream and the reconstructed rows; a decoder that produces the right integers at wrong row positions is still incorrect.

The modular lab isolates wrapping with a small visible modulus. Reset, set both modulus m=16 and additive step a=3, predict residue zero initially and residue three after one Step, then inspect it. Each Step advances half a second and one addition because n=floor(2t). Further steps produce six and nine before wrapping eventually. The sixteen-element cycle is a four-bit arithmetic analogy, not a DELTA_BINARY_PACKED encoder; the lab has no minimum-delta selection, miniblocks, page headers, or INT32 overflow test. Changing controls retains elapsed time, so Reset before a separate comparison.