parquet.alp

From "ALP: Adaptive Lossless floating-Point Compression" (Afroozeh, Kuffo and Boncz, SIGMOD 2024), specified for Parquet in AlpEncoding.md.

The idea is that most floating-point data in the wild is decimal in origin — prices, sensor readings, coordinates — so v * 10^e / 10^f lands exactly on an integer for some small e and f. Those integers are then frame-of-reference encoded and bit-packed, which is far denser than the original mantissas. Values that do not survive the round trip are stored verbatim as exceptions, so the encoding stays lossless whatever the input.

A page is a 7-byte header, an offset array, then independent vectors:

compression_mode : u8      0 = ALP
integer_encoding : u8      0 = frame of reference + bit-packing
log_vector_size  : u8      log2 of the values per vector, 3..15
num_elements     : i32 LE  values in the page
offsets          : u32 LE * num_vectors, from the start of the offset array

and each vector is

exponent         : u8      e
factor           : u8      f, <= e
num_exceptions   : u16 LE
frame_of_ref     : i32/i64 LE   4 bytes for FLOAT, 8 for DOUBLE
bit_width        : u8
packed           : ceil(n * bit_width / 8) bytes, LSB-first
exc_positions    : u16 LE * num_exceptions
exc_values       : the original IEEE 754 values

Decoding one value is (delta + frame_of_reference) * 10^f / 10^e, then the exceptions are written over the positions they name.

def decode_alp[dt: DType](data: Span[UInt8], count: Int) -> PhysBuffer