You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@parquet.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2026/05/01 15:35:47 UTC
Re: [PR] GH-533: Add ALP (Adaptive Lossless floating-Point) encoding specification [parquet-format]
alamb commented on code in PR #557:
URL: https://github.com/apache/parquet-format/pull/557#discussion_r3173623909
##########
Encodings.md:
##########
@@ -22,29 +22,17 @@ Parquet encoding definitions
This file contains the specification of all supported encodings.
-Unless otherwise stated in page or encoding documentation, any encoding can be
-used with any page type.
-
-### Supported Encodings
-
-For details on current implementation status, see the [Implementation Status](https://parquet.apache.org/docs/file-format/implementationstatus/#encodings) page.
-
-| Encoding type | Encoding enum | Supported Types |
-| ------------------------------------------------ | --------------------------------------------------------- | ------------------------------------------------- |
-| [Plain](#PLAIN) | PLAIN = 0 | All Physical Types |
-| [Dictionary Encoding](#DICTIONARY) | PLAIN_DICTIONARY = 2 (Deprecated) <br> RLE_DICTIONARY = 8 | All Physical Types |
-| [Run Length Encoding / Bit-Packing Hybrid](#RLE) | RLE = 3 | BOOLEAN, Dictionary Indices |
-| [Delta Encoding](#DELTAENC) | DELTA_BINARY_PACKED = 5 | INT32, INT64 |
-| [Delta-length byte array](#DELTALENGTH) | DELTA_LENGTH_BYTE_ARRAY = 6 | BYTE_ARRAY |
-| [Delta Strings](#DELTASTRING) | DELTA_BYTE_ARRAY = 7 | BYTE_ARRAY, FIXED_LEN_BYTE_ARRAY |
-| [Byte Stream Split](#BYTESTREAMSPLIT) | BYTE_STREAM_SPLIT = 9 | INT32, INT64, FLOAT, DOUBLE, FIXED_LEN_BYTE_ARRAY |
-
-### Deprecated Encodings
-
-| Encoding type | Encoding enum |
-| ------------------------------------- | -------------- |
-| [Bit-packed (Deprecated)](#BITPACKED) | BIT_PACKED = 4 |
-
+| Encoding | ID | Supported Types |
Review Comment:
Something seems strange to me about this chart. The version on main
https://github.com/apache/parquet-format/blob/96edf77704b60b6f3ca2232c218c64eff6c874d3/Encodings.md?plain=1#L28-L40
Doesn't appear in this document.
I would expect this PR that adds the new ALP encoding to add a new entry to the existing table, rather than add an entirely new table.
Maybe we need to merge up from main to this branch (I am happy to do this and I think I have the permissions to push to your branch, but I don't want to mess things up on you)
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
Review Comment:
I don't understand this sentence. The C++ implementation does not seem to change sign order from what I can tell:
https://github.com/apache/arrow/pull/48345/changes#diff-f9ab708cab94060b4067fff0a6739e9c3751b450422115663b2bd0badfcc748bR487-R490
```c++
/// \brief Convert a float to an int without rounding
static inline auto FastRound(T n) -> SignedExactType {
n = n + Constants::kMagicNumber - Constants::kMagicNumber;
return static_cast<SignedExactType>(n);
}
```
Also the ["Fast Rounding"](https://ir.cwi.nl/pub/33334/33334.pdf) section of the ALP paper doesn't mention sign reversal that I can find
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
Review Comment:
```suggestion
enabling random access to individual values and parallel encode/decode.
```
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
Review Comment:
I think *SHOULD* is too strong a word here. Maybe we could soften it to a suggestion
```suggestion
To avoid the cost of exhaustive search on every vector, implementations
can use a sampling approach. One such approach, described in the paper, is to
select up to 5 candidate (exponent, factor) combinations (the "encoding preset")
at the start of each column chunk, and when encoding each vector,
test each of the 5 candidates for the fewest exceptions.
```
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
Review Comment:
I think it would help to use consistent terminology here to above.
```suggestion
The `fast_round` function uses a "magic number" technique for branchless rounding.
`fast_round(value)` is defined as follows:
```
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
Review Comment:
This section has a worked example of FOR / bitpacking so perhaps we could write it like
```suggestion
##### Example: Frame of Reference and Bit-Packing
```
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
+
+After decimal encoding and exception substitution:
+
+```
++---------------------------------------------------------------------+
+| Encoded: [ 123, 456, 789, 12 ] |
+| |
+| min_val = 12 (stored as frame_of_reference) |
+| |
+| Deltas: [ 111, 444, 777, 0 ] <-- all non-negative |
++---------------------------------------------------------------------+
+```
+
+| Step | Formula | Example |
+|------------------------|---------------------------------------|-----------------------------|
+| 1. Find min | min\_val = min(encoded\[\]) | 12 |
+| 2. Compute deltas | delta\[i\] = encoded\[i\] - min\_val | \[111, 444, 777, 0\] |
+| 3. Calculate bit width | bit\_width = ceil(log2(max\_delta+1)) | ceil(log2(778)) = 10 |
+| 4. Pack values | Each value uses bit\_width bits | 4 * 10 = 40 bits = 5 bytes |
+
+Special case: If all values are identical, bit\_width = 0 and no packed data is stored.
+
+#### Decoding
+
+```
+ Input: Serialized vector bytes
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. BIT UNPACKING |
+ | Unpack num_elements values at bit_width bits each |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. REVERSE FOR |
+ | encoded[i] = delta[i] + frame_of_reference |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. DECIMAL DECODING |
+ | value[i] = encoded[i] * 10^factor * 10^(-exponent) |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. PATCH EXCEPTIONS |
+ | value[pos[j]] = exception_values[j] |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Original float/double array
+```
+
+For each vector:
+
+1. Read AlpInfo and ForInfo from the vector header.
+2. Unpack `bit_width`-bit integers from PackedValues.
+3. Add `frame_of_reference` to each unpacked integer.
+4. Decode: multiply each integer by `10^factor` then by `10^(-exponent)`.
+5. Patch exceptions: for each (position, value) in the exception arrays,
+ overwrite the decoded output at that position with the stored value.
+
+#### Example 1: Simple Decimal Values
+
+**Input:** `float values[4] = { 1.23, 4.56, 7.89, 0.12 }`
+
+**Step 1: Find Best Exponent/Factor**
+
+Testing (exponent=2, factor=0) means multiply by 10^2 = 100:
+
+| Value | value * 100 | Rounded | Verify: rounded * 1.0 * 0.01 | Match? |
+|-------|-------------|---------|-------------------------------|--------|
+| 1.23 | 123.0 | 123 | 1.23 | Yes |
+| 4.56 | 456.0 | 456 | 4.56 | Yes |
+| 7.89 | 789.0 | 789 | 7.89 | Yes |
+| 0.12 | 12.0 | 12 | 0.12 | Yes |
+
+All values round-trip correctly -- no exceptions.
+
+**Step 2: Frame of Reference**
+
+| Encoded | min = 12 | Delta (encoded - min) |
+|---------|----------|-----------------------|
+| 123 | - | 111 |
+| 456 | - | 444 |
+| 789 | - | 777 |
+| 12 | - | 0 |
+
+**Step 3: Bit Packing**
+
+max\_delta = 777, bit\_width = ceil(log2(778)) = 10 bits,
+packed\_size = ceil(4 * 10 / 8) = 5 bytes
+
+**Serialized Vector:**
+
+| Section | Content | Size |
+|---------------------|----------------------------------------|----------|
+| AlpInfo | e=2, f=0, num\_exceptions=0 | 4 bytes |
+| ForInfo | frame\_of\_reference=12, bit\_width=10 | 5 bytes |
+| PackedValues | \[111, 444, 777, 0\] at 10 bits each | 5 bytes |
+| ExceptionPositions | (none) | 0 bytes |
+| ExceptionValues | (none) | 0 bytes |
+| **Total** | | **14 bytes** |
+
+Compared to PLAIN encoding (4 * 4 = 16 bytes). With 1024 values, the 9-byte
+vector header becomes negligible and compression ratios of 2-8x are typical.
+
+#### Example 2: Values with Exceptions
+
+**Input:** `float values[4] = { 1.5, NaN, 2.5, 0.333... }`
+
+**Step 1: Decimal Encoding with (e=1, f=0)**
+
+Multiply by 10^1 = 10:
+
+| Index | Value | value * 10 | Rounded | Verify | Exception? |
+|-------|----------|------------|---------|----------------|------------|
+| 0 | 1.5 | 15.0 | 15 | 1.5 = 1.5 | No |
+| 1 | NaN | - | - | - | Yes (NaN) |
+| 2 | 2.5 | 25.0 | 25 | 2.5 = 2.5 | No |
+| 3 | 0.333... | 3.333... | 3 | 0.3 != 0.333...| Yes (round-trip) |
+
+**Step 2: Handle Exceptions**
+
+Exception positions: \[1, 3\]
+Exception values: \[NaN, 0.333...\]
+Placeholder: 15 (first non-exception encoded value)
+Encoded with placeholders: \[15, 15, 25, 15\]
+
+**Step 3: Frame of Reference**
+
+| Encoded | min = 15 | Delta |
+|------------------|----------|-------|
+| 15 | - | 0 |
+| 15 (placeholder) | - | 0 |
+| 25 | - | 10 |
+| 15 (placeholder) | - | 0 |
+
+**Step 4: Bit Packing**
+
+max\_delta = 10, bit\_width = ceil(log2(11)) = 4 bits,
+packed\_size = ceil(4 * 4 / 8) = 2 bytes
+
+**Serialized Vector:**
+
+| Section | Content | Size |
+|---------------------|----------------------------------------|----------|
+| AlpInfo | e=1, f=0, num\_exceptions=2 | 4 bytes |
+| ForInfo | frame\_of\_reference=15, bit\_width=4 | 5 bytes |
+| PackedValues | \[0, 0, 10, 0\] at 4 bits each | 2 bytes |
+| ExceptionPositions | \[1, 3\] | 4 bytes |
+| ExceptionValues | \[NaN, 0.333...\] | 8 bytes |
+| **Total** | | **23 bytes** |
+
+#### Example 3: Monetary Data (1024 values)
+
+1024 price values ranging from $0.01 to $999.99 (e.g., product prices).
+
+Optimal encoding: (exponent=2, factor=0)
+
+| Metric | Value | Calculation |
+|---------------|-------------|--------------------------------------|
+| Exponent | 2 | Multiply by 100 for 2 decimal places |
+| Factor | 0 | No additional scaling needed |
+| Encoded range | 1 to 99,999 | $0.01 -> 1, $999.99 -> 99999 |
+| FOR min | 1 | Assuming $0.01 is present |
+| Delta range | 0 to 99,998 | After FOR subtraction |
+| Bit width | 17 | ceil(log2(99999)) = 17 bits |
+| Packed size | 2,176 bytes | ceil(1024 * 17 / 8) |
+
+**Size Comparison:**
+
+| Encoding | Size | Ratio |
+|---------------|--------------|----------------------|
+| PLAIN (float) | 4,096 bytes | 1.0x |
+| ALP | ~2,185 bytes | 0.53x (47% smaller) |
+
+#### Characteristics
+
+| Property | Description |
+|----------------|----------------------------------------------------------------------------------------|
+| Lossless | All original floating-point values are perfectly recoverable, including NaN, Inf, -0.0 |
+| Adaptive | Exponent/factor selection adapts per vector based on data characteristics |
+| Vectorized | Fixed-size vectors enable SIMD-optimized bit packing/unpacking |
+| Exception-safe | Values that don't fit decimal model are stored separately |
+
+**Best use cases:**
+
+* Monetary/financial data (prices, transactions)
+* Sensor readings with fixed precision
+* Scientific measurements with limited decimal places
+* GPS coordinates and geographic data
+* Normalized scores and percentages
+
+**Worst case scenarios:**
+
+* Random floating-point values (high exception rate)
+* High-precision scientific data (many decimal places)
+* Data with many special values (NaN, Inf)
+* Very small datasets (header overhead dominates)
+
+**Comparison with other encodings:**
+
+| Encoding | Type Support | Compression | Best For |
+|---------------------|--------------|-------------|---------------------|
+| PLAIN | All | None | General purpose |
+| BYTE\_STREAM\_SPLIT | Float/Double | Moderate | Random floats |
+| ALP | Float/Double | High | Decimal-like floats |
+| DELTA\_BINARY\_PACKED | Int32/Int64 | High | Sequential integers |
+
+Unlike [Byte Stream Split](#BYTE_STREAM_SPLIT), ALP does not require a subsequent
+compression step to achieve size reduction -- the bit-packing directly reduces the
+encoded size. However, ALP and Byte Stream Split can be complementary: ALP
+exploits decimal structure while Byte Stream Split exploits byte-level correlation.
+
+#### Size Calculations
+
+##### Vector Size Formula
+
+```
+vector_bytes = vector_header_size // FLOAT: 9, DOUBLE: 13
+ + ceil(num_elements * bit_width / 8) // packed values
+ + num_exceptions * 2 // exception positions (uint16)
+ + num_exceptions * sizeof(T) // exception values (4 or 8)
+```
+
+##### Page Size Formula
+
+```
+page_bytes = 7 // page header
+ + num_vectors * 4 // offset array
+ + sum(vector_bytes for each vector) // all vectors
+```
+
+#### Constants Reference
Review Comment:
This appears to be C/++ implementation details -- I am not sure it adds any value to the spec
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
+
+After decimal encoding and exception substitution:
+
+```
++---------------------------------------------------------------------+
+| Encoded: [ 123, 456, 789, 12 ] |
+| |
+| min_val = 12 (stored as frame_of_reference) |
+| |
+| Deltas: [ 111, 444, 777, 0 ] <-- all non-negative |
++---------------------------------------------------------------------+
+```
+
+| Step | Formula | Example |
+|------------------------|---------------------------------------|-----------------------------|
+| 1. Find min | min\_val = min(encoded\[\]) | 12 |
+| 2. Compute deltas | delta\[i\] = encoded\[i\] - min\_val | \[111, 444, 777, 0\] |
+| 3. Calculate bit width | bit\_width = ceil(log2(max\_delta+1)) | ceil(log2(778)) = 10 |
+| 4. Pack values | Each value uses bit\_width bits | 4 * 10 = 40 bits = 5 bytes |
+
+Special case: If all values are identical, bit\_width = 0 and no packed data is stored.
+
+#### Decoding
+
+```
+ Input: Serialized vector bytes
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. BIT UNPACKING |
+ | Unpack num_elements values at bit_width bits each |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. REVERSE FOR |
+ | encoded[i] = delta[i] + frame_of_reference |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. DECIMAL DECODING |
+ | value[i] = encoded[i] * 10^factor * 10^(-exponent) |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. PATCH EXCEPTIONS |
+ | value[pos[j]] = exception_values[j] |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Original float/double array
+```
+
+For each vector:
+
+1. Read AlpInfo and ForInfo from the vector header.
+2. Unpack `bit_width`-bit integers from PackedValues.
+3. Add `frame_of_reference` to each unpacked integer.
+4. Decode: multiply each integer by `10^factor` then by `10^(-exponent)`.
+5. Patch exceptions: for each (position, value) in the exception arrays,
+ overwrite the decoded output at that position with the stored value.
+
+#### Example 1: Simple Decimal Values
+
+**Input:** `float values[4] = { 1.23, 4.56, 7.89, 0.12 }`
+
+**Step 1: Find Best Exponent/Factor**
+
+Testing (exponent=2, factor=0) means multiply by 10^2 = 100:
+
+| Value | value * 100 | Rounded | Verify: rounded * 1.0 * 0.01 | Match? |
+|-------|-------------|---------|-------------------------------|--------|
+| 1.23 | 123.0 | 123 | 1.23 | Yes |
+| 4.56 | 456.0 | 456 | 4.56 | Yes |
+| 7.89 | 789.0 | 789 | 7.89 | Yes |
+| 0.12 | 12.0 | 12 | 0.12 | Yes |
+
+All values round-trip correctly -- no exceptions.
+
+**Step 2: Frame of Reference**
+
+| Encoded | min = 12 | Delta (encoded - min) |
+|---------|----------|-----------------------|
+| 123 | - | 111 |
+| 456 | - | 444 |
+| 789 | - | 777 |
+| 12 | - | 0 |
+
+**Step 3: Bit Packing**
+
+max\_delta = 777, bit\_width = ceil(log2(778)) = 10 bits,
+packed\_size = ceil(4 * 10 / 8) = 5 bytes
+
+**Serialized Vector:**
+
+| Section | Content | Size |
+|---------------------|----------------------------------------|----------|
+| AlpInfo | e=2, f=0, num\_exceptions=0 | 4 bytes |
+| ForInfo | frame\_of\_reference=12, bit\_width=10 | 5 bytes |
+| PackedValues | \[111, 444, 777, 0\] at 10 bits each | 5 bytes |
+| ExceptionPositions | (none) | 0 bytes |
+| ExceptionValues | (none) | 0 bytes |
+| **Total** | | **14 bytes** |
+
+Compared to PLAIN encoding (4 * 4 = 16 bytes). With 1024 values, the 9-byte
+vector header becomes negligible and compression ratios of 2-8x are typical.
+
+#### Example 2: Values with Exceptions
+
+**Input:** `float values[4] = { 1.5, NaN, 2.5, 0.333... }`
+
+**Step 1: Decimal Encoding with (e=1, f=0)**
+
+Multiply by 10^1 = 10:
+
+| Index | Value | value * 10 | Rounded | Verify | Exception? |
+|-------|----------|------------|---------|----------------|------------|
+| 0 | 1.5 | 15.0 | 15 | 1.5 = 1.5 | No |
+| 1 | NaN | - | - | - | Yes (NaN) |
+| 2 | 2.5 | 25.0 | 25 | 2.5 = 2.5 | No |
+| 3 | 0.333... | 3.333... | 3 | 0.3 != 0.333...| Yes (round-trip) |
+
+**Step 2: Handle Exceptions**
+
+Exception positions: \[1, 3\]
+Exception values: \[NaN, 0.333...\]
+Placeholder: 15 (first non-exception encoded value)
+Encoded with placeholders: \[15, 15, 25, 15\]
+
+**Step 3: Frame of Reference**
+
+| Encoded | min = 15 | Delta |
+|------------------|----------|-------|
+| 15 | - | 0 |
+| 15 (placeholder) | - | 0 |
+| 25 | - | 10 |
+| 15 (placeholder) | - | 0 |
+
+**Step 4: Bit Packing**
+
+max\_delta = 10, bit\_width = ceil(log2(11)) = 4 bits,
+packed\_size = ceil(4 * 4 / 8) = 2 bytes
+
+**Serialized Vector:**
+
+| Section | Content | Size |
+|---------------------|----------------------------------------|----------|
+| AlpInfo | e=1, f=0, num\_exceptions=2 | 4 bytes |
+| ForInfo | frame\_of\_reference=15, bit\_width=4 | 5 bytes |
+| PackedValues | \[0, 0, 10, 0\] at 4 bits each | 2 bytes |
+| ExceptionPositions | \[1, 3\] | 4 bytes |
+| ExceptionValues | \[NaN, 0.333...\] | 8 bytes |
+| **Total** | | **23 bytes** |
+
+#### Example 3: Monetary Data (1024 values)
+
+1024 price values ranging from $0.01 to $999.99 (e.g., product prices).
+
+Optimal encoding: (exponent=2, factor=0)
+
+| Metric | Value | Calculation |
+|---------------|-------------|--------------------------------------|
+| Exponent | 2 | Multiply by 100 for 2 decimal places |
+| Factor | 0 | No additional scaling needed |
+| Encoded range | 1 to 99,999 | $0.01 -> 1, $999.99 -> 99999 |
+| FOR min | 1 | Assuming $0.01 is present |
+| Delta range | 0 to 99,998 | After FOR subtraction |
+| Bit width | 17 | ceil(log2(99999)) = 17 bits |
+| Packed size | 2,176 bytes | ceil(1024 * 17 / 8) |
+
+**Size Comparison:**
+
+| Encoding | Size | Ratio |
+|---------------|--------------|----------------------|
+| PLAIN (float) | 4,096 bytes | 1.0x |
+| ALP | ~2,185 bytes | 0.53x (47% smaller) |
+
+#### Characteristics
Review Comment:
as above, this is great stuff but probably doesn't belong in the spec
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
+
+After decimal encoding and exception substitution:
+
+```
++---------------------------------------------------------------------+
+| Encoded: [ 123, 456, 789, 12 ] |
+| |
+| min_val = 12 (stored as frame_of_reference) |
+| |
+| Deltas: [ 111, 444, 777, 0 ] <-- all non-negative |
++---------------------------------------------------------------------+
+```
+
+| Step | Formula | Example |
+|------------------------|---------------------------------------|-----------------------------|
+| 1. Find min | min\_val = min(encoded\[\]) | 12 |
+| 2. Compute deltas | delta\[i\] = encoded\[i\] - min\_val | \[111, 444, 777, 0\] |
+| 3. Calculate bit width | bit\_width = ceil(log2(max\_delta+1)) | ceil(log2(778)) = 10 |
+| 4. Pack values | Each value uses bit\_width bits | 4 * 10 = 40 bits = 5 bytes |
+
+Special case: If all values are identical, bit\_width = 0 and no packed data is stored.
+
+#### Decoding
+
+```
+ Input: Serialized vector bytes
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. BIT UNPACKING |
+ | Unpack num_elements values at bit_width bits each |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. REVERSE FOR |
+ | encoded[i] = delta[i] + frame_of_reference |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. DECIMAL DECODING |
+ | value[i] = encoded[i] * 10^factor * 10^(-exponent) |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. PATCH EXCEPTIONS |
+ | value[pos[j]] = exception_values[j] |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Original float/double array
+```
+
+For each vector:
+
+1. Read AlpInfo and ForInfo from the vector header.
+2. Unpack `bit_width`-bit integers from PackedValues.
+3. Add `frame_of_reference` to each unpacked integer.
+4. Decode: multiply each integer by `10^factor` then by `10^(-exponent)`.
+5. Patch exceptions: for each (position, value) in the exception arrays,
+ overwrite the decoded output at that position with the stored value.
+
+#### Example 1: Simple Decimal Values
Review Comment:
I reviewed this section and I think the content in the Examples is really nice but too verbose to include all of them in the spec.
Specifically
1. I think one fully worked example (with exceptions) would help understand how this works
2. The size analysis and comparison to PLAIN encoding or other encodings is too much detail for this spec (it makes the spec change significantly longer, and does not help someone implement the encoding, but rather decide when to use ALP / why it was added to the spec)
3. None of the examples shows a `f` factor other than zero -- it would be good to add an example with a non zero f
Thus I propose:
1. Reduce to a single example (I think Example 2)
2. Update the example with `f != 0`
3. Move the other examples and comparisons to the blog post we will write for ALP (simplarly to https://parquet.apache.org/blog/2026/02/27/variant-type-in-apache-parquet-for-semi-structured-data/ or https://parquet.apache.org/blog/2026/02/13/native-geospatial-types-in-apache-parquet/)
Would it be ok if I started writing a blog post about this feature (and thus we had a place to move these examples)?
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
+
+After decimal encoding and exception substitution:
Review Comment:
```suggestion
Given the following data after decimal encoding and exception substitution:
```
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
Review Comment:
I don't understand what "use identical power-of-10 values" means. **ALL** encoders and decoders must to use the exact same values (and floating point arithmetic) as I understand it.
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
+
+After decimal encoding and exception substitution:
+
+```
++---------------------------------------------------------------------+
+| Encoded: [ 123, 456, 789, 12 ] |
+| |
+| min_val = 12 (stored as frame_of_reference) |
+| |
+| Deltas: [ 111, 444, 777, 0 ] <-- all non-negative |
++---------------------------------------------------------------------+
+```
+
+| Step | Formula | Example |
+|------------------------|---------------------------------------|-----------------------------|
+| 1. Find min | min\_val = min(encoded\[\]) | 12 |
+| 2. Compute deltas | delta\[i\] = encoded\[i\] - min\_val | \[111, 444, 777, 0\] |
+| 3. Calculate bit width | bit\_width = ceil(log2(max\_delta+1)) | ceil(log2(778)) = 10 |
+| 4. Pack values | Each value uses bit\_width bits | 4 * 10 = 40 bits = 5 bytes |
+
+Special case: If all values are identical, bit\_width = 0 and no packed data is stored.
+
+#### Decoding
+
+```
+ Input: Serialized vector bytes
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. BIT UNPACKING |
+ | Unpack num_elements values at bit_width bits each |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. REVERSE FOR |
+ | encoded[i] = delta[i] + frame_of_reference |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. DECIMAL DECODING |
+ | value[i] = encoded[i] * 10^factor * 10^(-exponent) |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. PATCH EXCEPTIONS |
+ | value[pos[j]] = exception_values[j] |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Original float/double array
+```
+
+For each vector:
+
+1. Read AlpInfo and ForInfo from the vector header.
+2. Unpack `bit_width`-bit integers from PackedValues.
+3. Add `frame_of_reference` to each unpacked integer.
+4. Decode: multiply each integer by `10^factor` then by `10^(-exponent)`.
+5. Patch exceptions: for each (position, value) in the exception arrays,
+ overwrite the decoded output at that position with the stored value.
+
+#### Example 1: Simple Decimal Values
Review Comment:
Here is a ticket that describes the ALP blog:
- https://github.com/apache/parquet-site/issues/175
##########
Encodings.md:
##########
@@ -391,3 +375,518 @@ After applying the transformation, the data has the following representation:
```
Bytes AA 00 A3 BB 11 B4 CC 22 C5 DD 33 D6
```
+
+<a name="ALP"></a>
+### Adaptive Lossless floating-Point: (ALP = 10)
+
+Supported Types: FLOAT, DOUBLE
+
+This encoding is adapted from the paper
+["ALP: Adaptive Lossless floating-Point Compression"](https://dl.acm.org/doi/10.1145/3626717)
+by Afroozeh and Boncz (SIGMOD 2024).
+
+ALP works by converting floating-point values to integers using decimal scaling
+(controlled by an *exponent* `e` and *factor* `f`), then applying Frame of
+Reference (FOR) encoding and bit-packing. Values that cannot be losslessly
+converted are stored separately as *exceptions*. The encoding achieves high
+compression for decimal-like floating-point data (e.g., monetary values, sensor
+readings) while remaining fully lossless. Each value is encoded independently,
+enabling random access to individual vectors and parallel encode/decode.
+
+#### Overview
+
+ALP encoding consists of a page-level header followed by an offset array and one
+or more encoded vectors (batches of values). Each vector contains up to
+`vector_size` elements (default 1024).
+
+```
++-------------+-----------------------------+--------------------------------------+
+| Header | Offset Array | Vector Data |
+| (7 bytes) | (num_vectors * 4 bytes) | (variable) |
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+| Page Header | off0 | off1 | ... | off N-1 | Vector 0 | Vector 1 | ... | Vec N-1 |
+| (7 bytes) | (4B) | (4B) | | (4B) |(variable)|(variable)| |(variable)|
++-------------+------+------+-----+---------+----------+----------+-----+----------+
+```
+
+The compression pipeline for each vector is:
+
+```
+ Input: float/double array
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. CHOOSE PARAMETERS |
+ | Select (exponent, factor) pair for this vector |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. DECIMAL ENCODING |
+ | encoded[i] = fast_round(value[i] * 10^e * 10^(-f)) |
+ | Detect exceptions where decode(encode(v)) != v |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. FRAME OF REFERENCE (FOR) |
+ | min_val = min(encoded[]) |
+ | delta[i] = encoded[i] - min_val |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. BIT PACKING |
+ | bit_width = ceil(log2(max_delta + 1)) |
+ | Pack each delta into bit_width bits |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Serialized vector bytes
+```
+
+#### Page Layout
+
+##### Header (7 bytes)
+
+All multi-byte values are stored in little-endian order.
+
+```
+ Byte: 0 1 2 3 4 5 6
+ +----------------+---------------+--------------+----+----+----+----+
+ | compression | integer | log_vector | num_elements |
+ | _mode | _encoding | _size | (int32 LE) |
+ +----------------+---------------+--------------+----+----+----+----+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | compression_mode | 1 byte | uint8 | Compression mode (0 = ALP). Reserved for future variants (e.g., ALP-RD). |
+| 1 | integer_encoding | 1 byte | uint8 | Integer encoding (must be 0 = FOR + bit-packing) |
+| 2 | log_vector_size | 1 byte | uint8 | log2(vector\_size). Must be in the inclusive range \[3, 15\]. Recommended default: 10 (vector size 1024) |
+| 3 | num_elements | 4 bytes | int32 | Total number of floating-point values in the page |
+
+The number of vectors is `ceil(num_elements / vector_size)`. The last vector may
+contain fewer than `vector_size` elements.
+
+**Note:** The number of elements per vector is NOT stored in the header — it is
+derived: `vector_size` for all vectors except the last, which may be smaller.
+
+##### Offset Array
+
+Immediately following the header is an array of `num_vectors` little-endian uint32
+values. Each offset gives the byte position of the corresponding vector's data,
+measured from the start of the offset array itself.
+
+The first offset always equals `num_vectors * 4` (pointing just past the offset array).
+Each subsequent offset equals the previous offset plus the stored size of the
+previous vector.
+
+##### Vector Format
+
+Each vector is self-describing and contains the encoding parameters, FOR metadata,
+bit-packed encoded values, and exception data.
+
+```
++-------------------+-----------------+-------------------+---------------------+-------------------+
+| AlpInfo | ForInfo | PackedValues | ExceptionPositions | ExceptionValues |
+| (4 bytes) | (5B or 9B) | (variable) | (variable) | (variable) |
++-------------------+-----------------+-------------------+---------------------+-------------------+
+```
+
+Vector header sizes:
+| Type | AlpInfo | ForInfo | Total Header |
+|--------|---------|---------|--------------|
+| FLOAT | 4 bytes | 5 bytes | 9 bytes |
+| DOUBLE | 4 bytes | 9 bytes | 13 bytes |
+
+Data section sizes:
+| Section | Size Formula | Description |
+|---------------------|-----------------------------|------------------------------|
+| PackedValues | ceil(num\_elements\_in\_vector * bit\_width / 8) | Bit-packed delta values |
+| ExceptionPositions | num\_exceptions * 2 bytes | uint16 indices of exceptions |
+| ExceptionValues | num\_exceptions * sizeof(type) (4 for FLOAT, 8 for DOUBLE) | Original float/double values |
+
+###### AlpInfo (4 bytes, both types)
+
+```
+ Byte: 0 1 2 3
+ +----------+----------+---------+---------+
+ | exponent | factor | num_exceptions |
+ | (uint8) | (uint8) | (uint16 LE) |
+ +----------+----------+---------+---------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | exponent | 1 byte | uint8 | Power-of-10 exponent *e*. Range: \[0, 10\] for FLOAT, \[0, 18\] for DOUBLE. |
+| 1 | factor | 1 byte | uint8 | Power-of-10 factor *f*. Range: \[0, *e*\]. |
+| 2 | num_exceptions | 2 bytes | uint16 | Number of exception values in this vector. |
+
+###### ForInfo for FLOAT (5 bytes)
+
+```
+ Byte: 0 1 2 3 4
+ +----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int32 LE) | (uint8) |
+ +----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 4 bytes | int32 | Minimum encoded integer in the vector |
+| 4 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 32\]. |
+
+###### ForInfo for DOUBLE (9 bytes)
+
+```
+ Byte: 0 1 2 3 4 5 6 7 8
+ +----+----+----+----+----+----+----+----+-----------+
+ | frame_of_reference | bit_width |
+ | (int64 LE) | (uint8) |
+ +----+----+----+----+----+----+----+----+-----------+
+```
+
+| Offset | Field | Size | Type | Description |
+|--------|-------|------|------|-------------|
+| 0 | frame_of_reference | 8 bytes | int64 | Minimum encoded long in the vector |
+| 8 | bit_width | 1 byte | uint8 | Bits per packed value. Range: \[0, 64\]. |
+
+###### PackedValues
+
+The FOR-encoded deltas, bit-packed into `ceil(num_elements_in_vector * bit_width / 8)` bytes.
+Values are bit-packed using the same LSB-first packing order as the
+[RLE/Bit-Packing Hybrid](#RLE) encoding.
+
+If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all encoded
+integers are equal to `frame_of_reference`).
+
+###### ExceptionPositions
+
+An array of `num_exceptions` little-endian uint16 values, each giving
+the 0-based index within the vector of an exception value.
+
+###### ExceptionValues
+
+An array of `num_exceptions` values in the original floating-point type
+(4 bytes little-endian IEEE 754 for FLOAT, 8 bytes for DOUBLE), stored in
+the same order as the corresponding positions.
+
+#### Encoding
+
+##### Encoding Formula
+
+```
++-------------------------------------------------------------------+
+| |
+| encoded = fast_round( value * 10^e * 10^(-f) ) |
+| |
+| decoded = encoded * 10^f * 10^(-e) |
+| |
++-------------------------------------------------------------------+
+```
+
+The encoding uses two separate multiplications (not a single multiplication by
+`10^(e-f)`, and not division) to ensure that implementations produce identical
+floating-point rounding across languages. Implementations must ensure that the
+encoder and decoder use identical power-of-10 values for a given exponent.
+
+##### Fast Rounding
+
+The rounding function uses a "magic number" technique for branchless rounding:
+
+| Type | Magic Number | Formula |
+|--------|-----------------------------------|----------------------------------|
+| FLOAT | 2^22 + 2^23 = 12,582,912 | `(int32_t)((value + magic) - magic)` |
+| DOUBLE | 2^51 + 2^52 = 6,755,399,441,055,744 | `(int64_t)((value + magic) - magic)` |
+
+For negative values, the signs are reversed: `(int32_t)((value - magic) + magic)` for FLOAT, `(int64_t)((value - magic) + magic)` for DOUBLE.
+
+##### Parameter Selection
+
+The encoder selects the (exponent, factor) pair that minimizes exceptions.
+Valid combinations satisfy 0 ≤ factor ≤ exponent:
+
+| Type | Max Exponent | Total Combinations |
+|--------|--------------|--------------------|
+| FLOAT | 10 | 66 |
+| DOUBLE | 18 | 190 |
+
+To avoid the cost of exhaustive search on every vector, implementations
+SHOULD use sampling to select up to 5 candidate (exponent, factor)
+combinations (the "encoding preset") at the start of each column chunk.
+Each vector then searches only those 5 candidates.
+
+Sampling parameters:
+
+| Parameter | Value | Description |
+|----------------------|-------|-------------------------------------|
+| Vector Size | 1024 | Elements compressed as a unit |
+| Sample Size | 256 | Values sampled per vector |
+| Max Combinations | 5 | Best (e,f) pairs kept in preset |
+| Sample Vectors | 8 | Vectors sampled per row group |
+
+##### Exception Detection
+
+A value becomes an exception if any of the following is true:
+
+| Condition | Example | Reason |
+|--------------------|----------------------------|----------------------------------|
+| NaN | `NaN` | Cannot convert to integer |
+| Infinity | `+Inf`, `-Inf` | Cannot convert to integer |
+| Negative zero | `-0.0` | Would become `+0.0` after encoding |
+| Out of range | value * 10^e > INT32\_MAX | Exceeds target integer limits |
+| Round-trip failure | `0.333...` with e=1, f=0 | `decode(encode(v)) != v` |
+
+Exception values at positions in the vector are replaced with a placeholder
+(the encoded integer of the first non-exception value, or 0 if all values
+are exceptions) before FOR encoding. This keeps the FOR range tight.
+
+##### Frame of Reference and Bit-Packing
+
+After decimal encoding and exception substitution:
+
+```
++---------------------------------------------------------------------+
+| Encoded: [ 123, 456, 789, 12 ] |
+| |
+| min_val = 12 (stored as frame_of_reference) |
+| |
+| Deltas: [ 111, 444, 777, 0 ] <-- all non-negative |
++---------------------------------------------------------------------+
+```
+
+| Step | Formula | Example |
+|------------------------|---------------------------------------|-----------------------------|
+| 1. Find min | min\_val = min(encoded\[\]) | 12 |
+| 2. Compute deltas | delta\[i\] = encoded\[i\] - min\_val | \[111, 444, 777, 0\] |
+| 3. Calculate bit width | bit\_width = ceil(log2(max\_delta+1)) | ceil(log2(778)) = 10 |
+| 4. Pack values | Each value uses bit\_width bits | 4 * 10 = 40 bits = 5 bytes |
+
+Special case: If all values are identical, bit\_width = 0 and no packed data is stored.
+
+#### Decoding
+
+```
+ Input: Serialized vector bytes
+ |
+ v
+ +----------------------------------------------------------+
+ | 1. BIT UNPACKING |
+ | Unpack num_elements values at bit_width bits each |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 2. REVERSE FOR |
+ | encoded[i] = delta[i] + frame_of_reference |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 3. DECIMAL DECODING |
+ | value[i] = encoded[i] * 10^factor * 10^(-exponent) |
+ +----------------------------------------------------------+
+ |
+ v
+ +----------------------------------------------------------+
+ | 4. PATCH EXCEPTIONS |
+ | value[pos[j]] = exception_values[j] |
+ +----------------------------------------------------------+
+ |
+ v
+ Output: Original float/double array
+```
+
+For each vector:
+
+1. Read AlpInfo and ForInfo from the vector header.
+2. Unpack `bit_width`-bit integers from PackedValues.
+3. Add `frame_of_reference` to each unpacked integer.
+4. Decode: multiply each integer by `10^factor` then by `10^(-exponent)`.
+5. Patch exceptions: for each (position, value) in the exception arrays,
+ overwrite the decoded output at that position with the stored value.
+
+#### Example 1: Simple Decimal Values
+
+**Input:** `float values[4] = { 1.23, 4.56, 7.89, 0.12 }`
+
+**Step 1: Find Best Exponent/Factor**
+
+Testing (exponent=2, factor=0) means multiply by 10^2 = 100:
+
+| Value | value * 100 | Rounded | Verify: rounded * 1.0 * 0.01 | Match? |
+|-------|-------------|---------|-------------------------------|--------|
+| 1.23 | 123.0 | 123 | 1.23 | Yes |
+| 4.56 | 456.0 | 456 | 4.56 | Yes |
+| 7.89 | 789.0 | 789 | 7.89 | Yes |
+| 0.12 | 12.0 | 12 | 0.12 | Yes |
+
+All values round-trip correctly -- no exceptions.
+
+**Step 2: Frame of Reference**
+
+| Encoded | min = 12 | Delta (encoded - min) |
+|---------|----------|-----------------------|
+| 123 | - | 111 |
+| 456 | - | 444 |
+| 789 | - | 777 |
+| 12 | - | 0 |
+
+**Step 3: Bit Packing**
+
+max\_delta = 777, bit\_width = ceil(log2(778)) = 10 bits,
+packed\_size = ceil(4 * 10 / 8) = 5 bytes
+
+**Serialized Vector:**
+
+| Section | Content | Size |
+|---------------------|----------------------------------------|----------|
+| AlpInfo | e=2, f=0, num\_exceptions=0 | 4 bytes |
+| ForInfo | frame\_of\_reference=12, bit\_width=10 | 5 bytes |
+| PackedValues | \[111, 444, 777, 0\] at 10 bits each | 5 bytes |
+| ExceptionPositions | (none) | 0 bytes |
+| ExceptionValues | (none) | 0 bytes |
+| **Total** | | **14 bytes** |
+
+Compared to PLAIN encoding (4 * 4 = 16 bytes). With 1024 values, the 9-byte
+vector header becomes negligible and compression ratios of 2-8x are typical.
+
+#### Example 2: Values with Exceptions
+
+**Input:** `float values[4] = { 1.5, NaN, 2.5, 0.333... }`
+
+**Step 1: Decimal Encoding with (e=1, f=0)**
+
+Multiply by 10^1 = 10:
+
+| Index | Value | value * 10 | Rounded | Verify | Exception? |
+|-------|----------|------------|---------|----------------|------------|
+| 0 | 1.5 | 15.0 | 15 | 1.5 = 1.5 | No |
+| 1 | NaN | - | - | - | Yes (NaN) |
+| 2 | 2.5 | 25.0 | 25 | 2.5 = 2.5 | No |
+| 3 | 0.333... | 3.333... | 3 | 0.3 != 0.333...| Yes (round-trip) |
+
+**Step 2: Handle Exceptions**
+
+Exception positions: \[1, 3\]
+Exception values: \[NaN, 0.333...\]
+Placeholder: 15 (first non-exception encoded value)
+Encoded with placeholders: \[15, 15, 25, 15\]
+
+**Step 3: Frame of Reference**
+
+| Encoded | min = 15 | Delta |
+|------------------|----------|-------|
+| 15 | - | 0 |
+| 15 (placeholder) | - | 0 |
+| 25 | - | 10 |
+| 15 (placeholder) | - | 0 |
+
+**Step 4: Bit Packing**
+
+max\_delta = 10, bit\_width = ceil(log2(11)) = 4 bits,
+packed\_size = ceil(4 * 4 / 8) = 2 bytes
+
+**Serialized Vector:**
+
+| Section | Content | Size |
+|---------------------|----------------------------------------|----------|
+| AlpInfo | e=1, f=0, num\_exceptions=2 | 4 bytes |
+| ForInfo | frame\_of\_reference=15, bit\_width=4 | 5 bytes |
+| PackedValues | \[0, 0, 10, 0\] at 4 bits each | 2 bytes |
+| ExceptionPositions | \[1, 3\] | 4 bytes |
+| ExceptionValues | \[NaN, 0.333...\] | 8 bytes |
+| **Total** | | **23 bytes** |
+
+#### Example 3: Monetary Data (1024 values)
+
+1024 price values ranging from $0.01 to $999.99 (e.g., product prices).
+
+Optimal encoding: (exponent=2, factor=0)
+
+| Metric | Value | Calculation |
+|---------------|-------------|--------------------------------------|
+| Exponent | 2 | Multiply by 100 for 2 decimal places |
+| Factor | 0 | No additional scaling needed |
+| Encoded range | 1 to 99,999 | $0.01 -> 1, $999.99 -> 99999 |
+| FOR min | 1 | Assuming $0.01 is present |
+| Delta range | 0 to 99,998 | After FOR subtraction |
+| Bit width | 17 | ceil(log2(99999)) = 17 bits |
+| Packed size | 2,176 bytes | ceil(1024 * 17 / 8) |
+
+**Size Comparison:**
+
+| Encoding | Size | Ratio |
+|---------------|--------------|----------------------|
+| PLAIN (float) | 4,096 bytes | 1.0x |
+| ALP | ~2,185 bytes | 0.53x (47% smaller) |
+
+#### Characteristics
+
+| Property | Description |
+|----------------|----------------------------------------------------------------------------------------|
+| Lossless | All original floating-point values are perfectly recoverable, including NaN, Inf, -0.0 |
+| Adaptive | Exponent/factor selection adapts per vector based on data characteristics |
+| Vectorized | Fixed-size vectors enable SIMD-optimized bit packing/unpacking |
+| Exception-safe | Values that don't fit decimal model are stored separately |
+
+**Best use cases:**
+
+* Monetary/financial data (prices, transactions)
+* Sensor readings with fixed precision
+* Scientific measurements with limited decimal places
+* GPS coordinates and geographic data
+* Normalized scores and percentages
+
+**Worst case scenarios:**
+
+* Random floating-point values (high exception rate)
+* High-precision scientific data (many decimal places)
+* Data with many special values (NaN, Inf)
+* Very small datasets (header overhead dominates)
+
+**Comparison with other encodings:**
+
+| Encoding | Type Support | Compression | Best For |
+|---------------------|--------------|-------------|---------------------|
+| PLAIN | All | None | General purpose |
+| BYTE\_STREAM\_SPLIT | Float/Double | Moderate | Random floats |
+| ALP | Float/Double | High | Decimal-like floats |
+| DELTA\_BINARY\_PACKED | Int32/Int64 | High | Sequential integers |
+
+Unlike [Byte Stream Split](#BYTE_STREAM_SPLIT), ALP does not require a subsequent
+compression step to achieve size reduction -- the bit-packing directly reduces the
+encoded size. However, ALP and Byte Stream Split can be complementary: ALP
+exploits decimal structure while Byte Stream Split exploits byte-level correlation.
+
+#### Size Calculations
Review Comment:
I don't think we need to add add to the Parquet spec -- it isn't required to implement the encoder/decoder for ALP.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org