This is an automated email from the ASF dual-hosted git repository.
alamb pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/parquet-format.git
The following commit(s) were added to refs/heads/master by this push:
new 24102ed GH-602: Move ALP encoding specification to `AlpEncoding.md`
(#608)
24102ed is described below
commit 24102ed5c56e51b610a4897e5f79e76e43732d1d
Author: Andrew Lamb <[email protected]>
AuthorDate: Wed Aug 19 07:32:55 2026 -0400
GH-602: Move ALP encoding specification to `AlpEncoding.md` (#608)
* GH-602: Move detailed ALP encoding specification to AlpEncoding.md
Move the ALP algorithm description (everything from the Overview section
onward) out of Encodings.md into a new AlpEncoding.md, keeping the
introductory description and a link in Encodings.md.
The content is moved verbatim; the only edit is updating the
RLE/Bit-Packing Hybrid link to point back to Encodings.md.
Co-Authored-By: Claude Fable 5 <[email protected]>
* GH-602: Fix ALP document heading hierarchy
---------
Co-authored-by: Claude Fable 5 <[email protected]>
---
Encodings.md => AlpEncoding.md | 442 +++--------------------------------------
Encodings.md | 438 +---------------------------------------
2 files changed, 25 insertions(+), 855 deletions(-)
diff --git a/Encodings.md b/AlpEncoding.md
similarity index 52%
copy from Encodings.md
copy to AlpEncoding.md
index c8610f5..670d2a0 100644
--- a/Encodings.md
+++ b/AlpEncoding.md
@@ -17,408 +17,13 @@
- under the License.
-->
-Parquet encoding definitions
+ALP (Adaptive Lossless floating-Point) Encoding
====
-This file contains the specification of all supported encodings.
+This file contains the detailed specification of the
+[ALP encoding](Encodings.md#ALP) (`ALP = 10`).
-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 |
-| [ALP](#ALP) | ALP = 10
| FLOAT, DOUBLE
|
-
-### Deprecated Encodings
-
-| Encoding type | Encoding enum |
-| ------------------------------------- | -------------- |
-| [Bit-packed (Deprecated)](#BITPACKED) | BIT_PACKED = 4 |
-
-<a name="PLAIN"></a>
-### Plain: (PLAIN = 0)
-
-Supported Types: all
-
-This is the plain encoding that must be supported for types. It is
-intended to be the simplest encoding. Values are encoded back to back.
-
-The plain encoding is used whenever a more efficient encoding cannot be used.
It
-stores the data in the following format:
- - BOOLEAN: bit-packed, LSB first (using the same packing scheme as the
- [RLE/bit-packing hybrid](#RLE) encoding)
- - INT32: 4 bytes little endian
- - INT64: 8 bytes little endian
- - INT96: 12 bytes little endian (deprecated)
- - FLOAT: 4 bytes IEEE little endian
- - DOUBLE: 8 bytes IEEE little endian
- - BYTE_ARRAY: length in 4 bytes little endian followed by the bytes contained
in the array
- - FIXED_LEN_BYTE_ARRAY: the bytes contained in the array
-
-For native types, this outputs the data as little endian. Floating
- point types are encoded in IEEE.
-
-For the byte array type, it encodes the length as a 4-byte little
-endian integer, followed by the bytes.
-
-<a name="DICTIONARY"></a>
-### Dictionary Encoding (PLAIN_DICTIONARY = 2 and RLE_DICTIONARY = 8)
-The dictionary encoding builds a dictionary of values encountered in a given
column. The
-dictionary will be stored in a dictionary page per column chunk. The values
are stored as integers
-using the [RLE/Bit-Packing Hybrid](#RLE) encoding. If the dictionary grows too
big, whether in size
-or number of distinct values, the encoding will fall back to the plain
encoding. The dictionary page is
-written first, before the data pages of the column chunk.
-
-Dictionary page format: the entries in the dictionary using the
[plain](#PLAIN) encoding.
-
-Data page format: the bit width used to encode the entry ids stored as 1 byte
(max bit width = 32),
-followed by the values encoded using the RLE/Bit-Packing described above (with
the given bit width).
-
-Using the `PLAIN_DICTIONARY` enum value is deprecated, use `RLE_DICTIONARY`
-in a data page and `PLAIN` in a dictionary page for new Parquet files.
-
-<a name="RLE"></a>
-### Run Length Encoding / Bit-Packing Hybrid (RLE = 3)
-
-This encoding uses a combination of bit-packing and run length encoding to
more efficiently store repeated values.
-
-The grammar for this encoding looks like this, given a fixed bit-width known
in advance:
-```
-rle-bit-packed-hybrid: <length> <encoded-data>
-// length is not always prepended, please check the table below for more detail
-length := length of the <encoded-data> in bytes stored as 4 bytes little
endian (unsigned int32)
-encoded-data := <run>*
-run := <bit-packed-run> | <rle-run>
-bit-packed-run := <bit-packed-header> <bit-packed-values>
-bit-packed-header := varint-encode(<bit-pack-scaled-run-len> << 1 | 1)
-// we always bit-pack a multiple of 8 values at a time, so we only store the
number of values / 8
-bit-pack-scaled-run-len := (bit-packed-run-len) / 8
-bit-packed-run-len := *see 3 below*
-bit-packed-values := *see 1 below*
-rle-run := <rle-header> <repeated-value>
-rle-header := varint-encode( (rle-run-len) << 1)
-rle-run-len := *see 3 below*
-repeated-value := value that is repeated, using a fixed-width of
round-up-to-next-byte(bit-width)
-```
-
-1. The bit-packing here is done in a different order than the one in the
[deprecated bit-packing](#BITPACKED) encoding.
- The values are packed from the least significant bit of each byte to the
most significant bit,
- though the order of the bits in each value remains in the usual order of
most significant to least
- significant. For example, to pack the same values as the example in the
deprecated encoding above:
-
- The numbers 1 through 7 using bit width 3:
- ```
- dec value: 0 1 2 3 4 5 6 7
- bit value: 000 001 010 011 100 101 110 111
- bit label: ABC DEF GHI JKL MNO PQR STU VWX
- ```
-
- would be encoded like this where spaces mark byte boundaries (3 bytes):
- ```
- bit value: 10001000 11000110 11111010
- bit label: HIDEFABC RMNOJKLG VWXSTUPQ
- ```
-
- The reason for this packing order is to have fewer word-boundaries on
little-endian hardware
- when deserializing more than one byte at a time. This is because 4 bytes
can be read into a
- 32-bit register (or 8 bytes into a 64-bit register) and values can be
unpacked just by
- shifting and ORing with a mask. (to make this optimization work on a
big-endian machine,
- you would have to use the ordering used in the [deprecated
bit-packing](#BITPACKED) encoding)
-
-2. varint-encode() is ULEB-128 encoding, see
https://en.wikipedia.org/wiki/LEB128
-
-3. bit-packed-run-len and rle-run-len must be in the range \[1, 2<sup>31</sup>
- 1\].
- This means that a Parquet implementation can always store the run length in
a signed
- 32-bit integer. This length restriction was not part of the Parquet 2.5.0
and earlier
- specifications, but longer runs were not readable by the most common Parquet
- implementations so, in practice, were not safe for Parquet writers to emit.
-
-
-Note that the RLE encoding method is only supported for the following types of
-data:
-
-* Repetition and definition levels
-* Dictionary indices
-* Boolean values in data pages, as an alternative to PLAIN encoding
-
-Whether or not to prepend the four-byte `length` to the `encoded-data` is
summarized in the table below:
-```
-+--------------+------------------------+-----------------+
-| Page kind | RLE-encoded data kind | Prepend length? |
-+--------------+------------------------+-----------------+
-| Data page v1 | Definition levels | Y |
-| | Repetition levels | Y |
-| | Dictionary indices | N |
-| | Boolean values | Y |
-+--------------+------------------------+-----------------+
-| Data page v2 | Definition levels | N |
-| | Repetition levels | N |
-| | Dictionary indices | N |
-| | Boolean values | Y |
-+--------------+------------------------+-----------------+
-```
-
-<a name="BITPACKED"></a>
-### Bit-packed (Deprecated) (BIT_PACKED = 4)
-
-This is a bit-packed only encoding, which is deprecated; it has been replaced
by the [RLE/bit-packing](#RLE) hybrid encoding.
-Each value is encoded back to back using a fixed width.
-There is no padding between values (except for the last byte, which is padded
with 0s).
-For example, if the max repetition level was 3 (2 bits) and the max definition
level was 3
-(2 bits), to encode 30 values, we would have 30 * 2 = 60 bits = 8 bytes.
-
-This implementation is deprecated because the [RLE/bit-packing](#RLE) hybrid
is a superset of this implementation.
-For compatibility reasons, this implementation packs values from the most
significant bit to the least significant bit,
-which is not the same as the [RLE/bit-packing](#RLE) hybrid.
-
-For example, the numbers 1 through 7 using bit width 3:
-```
-dec value: 0 1 2 3 4 5 6 7
-bit value: 000 001 010 011 100 101 110 111
-bit label: ABC DEF GHI JKL MNO PQR STU VWX
-```
-would be encoded like this where spaces mark byte boundaries (3 bytes):
-```
-bit value: 00000101 00111001 01110111
-bit label: ABCDEFGH IJKLMNOP QRSTUVWX
-```
-
-Note that the BIT_PACKED encoding method is only supported for encoding
-repetition and definition levels.
-
-<a name="DELTAENC"></a>
-### Delta Encoding (DELTA_BINARY_PACKED = 5)
-Supported Types: INT32, INT64
-
-This encoding is adapted from the Binary packing described in
-["Decoding billions of integers per second through
vectorization"](https://arxiv.org/pdf/1209.2137v5.pdf)
-by D. Lemire and L. Boytsov.
-
-In delta encoding we make use of variable length integers for storing various
-numbers (not the deltas themselves). For unsigned values, we use ULEB128,
-which is the unsigned version of LEB128
(https://en.wikipedia.org/wiki/LEB128#Unsigned_LEB128).
-For signed values, we use zigzag encoding
(https://developers.google.com/protocol-buffers/docs/encoding#signed-integers)
-to map negative values to positive ones and apply ULEB128 on the result.
-
-Delta encoding consists of a header followed by blocks of delta encoded values
-binary packed. Each block is made of miniblocks, each of them binary packed
with its own bit width.
-
-The header is defined as follows:
-```
-<block size in values> <number of miniblocks in a block> <total value count>
<first value>
-```
- * the block size is a multiple of 128; it is stored as a ULEB128 int
- * the miniblock count per block is a divisor of the block size such that their
- quotient, the number of values in a miniblock, is a multiple of 32; it is
- stored as a ULEB128 int
- * the total value count is stored as a ULEB128 int
- * the first value is stored as a zigzag ULEB128 int
-
-Each block contains
-```
-<min delta> <list of bitwidths of miniblocks> <miniblocks>
-```
- * the min delta is a zigzag ULEB128 int (we compute a minimum as we need
- positive integers for bit packing)
- * the bitwidth of each miniblock is stored as a byte
- * each miniblock is a list of bit-packed ints according to the bit width
- stored at the beginning of the block
-
-To encode a block, we will:
-
-1. Compute the differences between consecutive elements. For the first
- element in the block, use the last element in the previous block or, in
- the case of the first block, use the first value of the whole sequence,
- stored in the header.
-
-2. Compute the frame of reference (the minimum of the deltas in the block).
- Subtract this min delta from all deltas in the block. This guarantees that
- all values are non-negative.
-
-3. Encode the frame of reference (min delta) as a zigzag ULEB128 int followed
- by the bit widths of the miniblocks and the delta values (minus the min
- delta) bit-packed per miniblock.
-
-Having multiple blocks allows us to adapt to changes in the data by changing
-the frame of reference (the min delta) which can result in smaller values
-after the subtraction which, again, means we can store them with a lower bit
width.
-
-If there are not enough values to fill the last miniblock, we pad the miniblock
-so that its length is always the number of values in a full miniblock
multiplied
-by the bit width. The values of the padding bits should be zero, but readers
-must accept paddings consisting of arbitrary bits as well.
-
-If, in the last block, less than ```<number of miniblocks in a block>```
-miniblocks are needed to store the values, the bytes storing the bit widths
-of the unneeded miniblocks are still present, their value should be zero,
-but readers must accept arbitrary values as well. There are no additional
-padding bytes for the miniblock bodies though, as if their bit widths were 0
-(regardless of the actual byte values). The reader knows when to stop reading
-by keeping track of the number of values read.
-
-Subtractions in steps 1) and 2) may incur signed arithmetic overflow, and so
-will the corresponding additions when decoding. Overflow should be allowed
-and handled as wrapping around in 2's complement notation so that the original
-values are correctly restituted. This may require explicit care in some
programming
-languages (for example by doing all arithmetic in the unsigned domain). Writers
-must not use more bits when bit packing the miniblock data than would be
required
-to PLAIN encode the physical type (e.g. INT32 data must not use more than 32
bits).
-
-The following examples use 8 as the block size to keep the examples short,
-but in real cases it would be invalid.
-
-#### Example 1
-1, 2, 3, 4, 5
-
-After step 1), we compute the deltas as:
-
-1, 1, 1, 1
-
-The minimum delta is 1 and after step 2, the relative deltas become:
-
-0, 0, 0, 0
-
-The final encoded data is:
-
- header:
-8 (block size), 1 (miniblock count), 5 (value count), 1 (first value)
-
- block:
-1 (minimum delta), 0 (bitwidth), (no data needed for bitwidth 0)
-
-#### Example 2
-7, 5, 3, 1, 2, 3, 4, 5, the deltas would be
-
--2, -2, -2, 1, 1, 1, 1
-
-The minimum is -2, so the relative deltas are:
-
-0, 0, 0, 3, 3, 3, 3
-
-The encoded data is
-
- header:
-8 (block size), 1 (miniblock count), 8 (value count), 7 (first value)
-
- block:
--2 (minimum delta), 2 (bitwidth), 00000011111111b (0,0,0,3,3,3,3 packed on 2
bits)
-
-#### Characteristics
-This encoding is similar to the [RLE/bit-packing](#RLE) encoding. However the
[RLE/bit-packing](#RLE) encoding is specifically used when the range of ints is
small over the entire page, as is true of repetition and definition levels. It
uses a single bit width for the whole page.
-The delta encoding algorithm described above stores a bit width per miniblock
and is less sensitive to variations in the size of encoded integers. It is also
somewhat doing RLE encoding as a block containing all the same values will be
bit packed to a zero bit width thus being only a header.
-
-<a name="DELTALENGTH"></a>
-### Delta-length byte array: (DELTA_LENGTH_BYTE_ARRAY = 6)
-
-Supported Types: BYTE_ARRAY
-
-This encoding is always preferred over PLAIN for byte array columns.
-
-For this encoding, we will take all the byte array lengths and encode them
using delta
-encoding (DELTA_BINARY_PACKED). The byte array data follows all of the length
data just
-concatenated back to back. The expected savings is from the cost of encoding
the lengths
-and possibly better compression in the data (it is no longer interleaved with
the lengths).
-
-The data stream looks like:
-```
-<Delta Encoded Lengths> <Byte Array Data>
-```
-
-For example, if the data was "Hello", "World", "Foobar", "ABCDEF"
-
-then the encoded data would be comprised of the following segments:
-- DeltaEncoding(5, 5, 6, 6) (the string lengths)
-- "HelloWorldFoobarABCDEF"
-
-<a name="DELTASTRING"></a>
-### Delta Strings: (DELTA_BYTE_ARRAY = 7)
-
-Supported Types: BYTE_ARRAY, FIXED_LEN_BYTE_ARRAY
-
-This is also known as incremental encoding or front compression: for each
element in a
-sequence of strings, store the prefix length of the previous entry plus the
suffix.
-
-For a longer description, see
https://en.wikipedia.org/wiki/Incremental_encoding.
-
-This is stored as a sequence of delta-encoded prefix lengths
(DELTA_BINARY_PACKED), followed by
-the suffixes encoded as delta length byte arrays (DELTA_LENGTH_BYTE_ARRAY).
-
-For example, if the data was "axis", "axle", "babble", "babyhood"
-
-then the encoded data would be comprised of the following segments:
-- DeltaEncoding(0, 2, 0, 3) (the prefix lengths)
-- DeltaEncoding(4, 2, 6, 5) (the suffix lengths)
-- "axislebabbleyhood"
-
-Note that, even for FIXED_LEN_BYTE_ARRAY, all lengths are encoded despite the
redundancy.
-
-<a name="BYTESTREAMSPLIT"></a>
-### Byte Stream Split: (BYTE_STREAM_SPLIT = 9)
-
-Supported Types: FLOAT, DOUBLE, INT32, INT64, FIXED_LEN_BYTE_ARRAY
-
-This encoding does not reduce the size of the data but can lead to a
significantly better
-compression ratio and speed when a compression algorithm is used afterwards.
-
-This encoding creates K byte-streams of length N where K is the size in bytes
of the data
-type and N is the number of elements in the data sequence. For example, K is 4
for FLOAT
-type and 8 for DOUBLE type.
-
-The bytes of each value are scattered to the corresponding streams. The 0-th
byte goes to the
-0-th stream, the 1-st byte goes to the 1-st stream and so on.
-The streams are concatenated in the following order: 0-th stream, 1-st stream,
etc.
-The total length of encoded streams is K * N bytes. Because it does not have
any metadata
-to indicate the total length, the end of the streams is also the end of data
page. No padding
-is allowed inside the data page.
-
-Example:
-Original data is three 32-bit floats and for simplicity we look at their raw
representation.
-```
- Element 0 Element 1 Element 2
-Bytes AA BB CC DD 00 11 22 33 A3 B4 C5 D6
-```
-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)
-
-**As of 2026-08-01, this encoding is in Preview.**
-
-**Note**: Preview means that:
-1. The encoding is finalized (the specification is stable).
-2. The implementation is ongoing in the ecosystem (e.g., parquet-java, etc.)
but may not be complete.
-3. The Parquet community recommends only using the encoding when you are sure
your reader supports it.
-4. Writers are recommended to provide an opt-in flag to enable this encoding.
-
-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, Kuffo, 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 values and parallel encoding/decoding.
-
-#### Overview
+## Overview
For each data page, ALP encoding consists of a header followed by an offset
array
and one or more encoded vectors (batches of values). Each vector contains up to
@@ -476,9 +81,9 @@ byte layout and the [Decoding](#decoding) procedure are
normative.
The `fast_round` used in step 2 is one recommended rounding technique,
described in
[Fast Rounding](#fast-rounding) below; it is informative, not normative.
-#### Page Layout
+## Page Layout
-##### Header (7 bytes)
+### Header (7 bytes)
All multi-byte values are stored in little-endian order.
@@ -503,7 +108,7 @@ 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
+### 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,
@@ -521,7 +126,7 @@ size of the ALP header. (When the page is uncompressed and
carries no repetition
or definition levels, `alp_data_start` coincides with the first byte after the
page's Thrift header.)
-##### Vector Format
+### Vector Format
Each vector is self-describing and contains the encoding parameters, FOR
metadata,
bit-packed encoded values, and exception data. The layout described here
applies
@@ -557,7 +162,7 @@ Data section sizes:
Here `bit_width` and `num_exceptions` are read from the vector header
(`ForInfo`
and `AlpInfo` respectively), described below.
-###### AlpInfo (4 bytes, both types)
+#### AlpInfo (4 bytes, both types)
```
Byte: 0 1 2 3
@@ -573,7 +178,7 @@ and `AlpInfo` respectively), described below.
| 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)
+#### ForInfo for FLOAT (5 bytes)
```
Byte: 0 1 2 3 4
@@ -588,7 +193,7 @@ and `AlpInfo` respectively), described below.
| 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)
+#### ForInfo for DOUBLE (9 bytes)
```
Byte: 0 1 2 3 4 5 6 7 8
@@ -603,11 +208,11 @@ and `AlpInfo` respectively), described below.
| 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
+#### 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. When the total number of packed bits
is
+[RLE/Bit-Packing Hybrid](Encodings.md#RLE) encoding. When the total number of
packed bits is
not a multiple of 8, the final byte is padded with zero bits in its most
significant positions.
@@ -621,12 +226,12 @@ vector, every delta is non-negative.
If `bit_width` is 0, no bytes are stored (all deltas are zero, meaning all
encoded
integers are equal to `frame_of_reference`).
-###### ExceptionPositions
+#### ExceptionPositions
An array of `num_exceptions` little-endian uint16 values, each giving
the 0-based index within the vector of an exception value.
-###### ExceptionValues
+#### 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
@@ -634,9 +239,9 @@ the same order as the corresponding positions. Each value
is stored as its exact
IEEE 754 bit pattern; implementations MUST NOT canonicalize NaN or otherwise
alter
the bits, so that decoding reproduces the original value bit-for-bit.
-#### Encoding
+## Encoding
-##### Encoding Formula
+### Encoding Formula
```
+-------------------------------------------------------------------+
@@ -667,7 +272,7 @@ is stored as an exception. The rounding method therefore
affects only compressio
ratio and exception count, never correctness or what a reader decodes. The
`fast_round` technique below is one recommended implementation.
-##### Fast Rounding (informative)
+### Fast Rounding (informative)
`fast_round` recovers the integer intended by `value * 10^e * 10^(-f)` — which
carries floating-point rounding noise — by rounding it to the nearest integer
@@ -690,7 +295,7 @@ The two forms round some large-magnitude inputs
differently, but since any value
that fails to round-trip is stored as an exception, the choice affects only
compression ratio, never correctness.
-##### Parameter Selection
+### Parameter Selection
Any valid (exponent, factor) pair produces a correct encoding — the decoder is
agnostic to the selection strategy, and the exception mechanism guarantees
@@ -722,7 +327,7 @@ Suggested sampling parameters (from the paper):
| Max Combinations | 5 | Best (e,f) pairs kept in preset |
| Sample Vectors | 8 | Vectors sampled per row group |
-##### Exception Detection
+### Exception Detection
A value becomes an exception if any of the following is true:
@@ -738,7 +343,7 @@ 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.
-##### Example: Frame of Reference and Bit-Packing
+### Example: Frame of Reference and Bit-Packing
Given the following data after decimal encoding and exception substitution:
@@ -761,7 +366,7 @@ Given the following data after decimal encoding and
exception substitution:
Special case: If all values are identical, bit\_width = 0 and no packed data
is stored.
-#### Decoding
+## Decoding
```
Input: Serialized vector bytes
@@ -803,7 +408,7 @@ For each vector:
5. Patch exceptions: for each (position, value) in the exception arrays,
overwrite the decoded output at that position with the stored value.
-#### Worked Example: Exceptions and Non-Zero Factor
+## Worked Example: Exceptions and Non-Zero Factor
**Input:** `double values[4] = { 1500.0, NaN, 2500.0, 333.5 }`
@@ -853,4 +458,3 @@ packed\_size = ceil(4 * 15 / 8) = 8 bytes
Compared to PLAIN encoding (4 * 8 = 32 bytes). With 1024 values, the 13-byte
vector header becomes negligible and compression ratios of 2-8x are typical.
-
diff --git a/Encodings.md b/Encodings.md
index c8610f5..0a07100 100644
--- a/Encodings.md
+++ b/Encodings.md
@@ -418,439 +418,5 @@ 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 values and parallel encoding/decoding.
-#### Overview
-
-For each data page, ALP encoding consists of a 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 below describes *one* way to produce a conforming
-vector. It is informative, not normative: an encoder may use any strategy as
long
-as it emits the byte layout defined in [Page Layout](#page-layout). Only that
-byte layout and the [Decoding](#decoding) procedure are normative.
-
-```
- Input: float/double array
- |
- v
- +----------------------------------------------------------+
- | 1. CHOOSE PARAMETERS |
- | Select (exponent, factor) pair for this array |
- +----------------------------------------------------------+
- |
- 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
-```
-
-The `fast_round` used in step 2 is one recommended rounding technique,
described in
-[Fast Rounding](#fast-rounding) below; it is informative, not normative.
-
-#### 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 non-null 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. No padding is inserted between vectors.
-
-Offsets are relative to the start of the offset array. A vector's absolute byte
-position is `alp_data_start + 7 + offset`, where `alp_data_start` is the first
-byte of the ALP header within the *decoded* page data — that is, after the page
-has been decompressed and after any repetition/definition levels — and `7` is
the
-size of the ALP header. (When the page is uncompressed and carries no
repetition
-or definition levels, `alp_data_start` coincides with the first byte after the
-page's Thrift header.)
-
-##### Vector Format
-
-Each vector is self-describing and contains the encoding parameters, FOR
metadata,
-bit-packed encoded values, and exception data. The layout described here
applies
-when `compression_mode` = 0 (ALP) and `integer_encoding` = 0 (FOR +
bit-packing);
-future modes may define different vector contents and need not include
`AlpInfo`
-or `ForInfo`.
-
-```
-<----------- Vector Header -----------><----------------------- Data Section
----------------------->
-+-------------------+-----------------+-------------------+---------------------+-------------------+
-| AlpInfo | ForInfo | PackedValues | ExceptionPositions
| ExceptionValues |
-| (4 bytes) | (5B or 9B) | (variable) | (variable)
| (variable) |
-+-------------------+-----------------+-------------------+---------------------+-------------------+
-```
-
-The first two components (`AlpInfo` and `ForInfo`) form the *vector header*;
the
-remaining three (`PackedValues`, `ExceptionPositions`, `ExceptionValues`) form
the
-*data section*.
-
-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(encoded type) (float=4 and
double=8) | Original values, stored as their exact IEEE-754 bits (NaN not
canonicalized) |
-
-Here `bit_width` and `num_exceptions` are read from the vector header
(`ForInfo`
-and `AlpInfo` respectively), described below.
-
-###### 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. When the total number of packed bits
is
-not a multiple of 8, the final byte is padded with zero bits in its most
-significant positions.
-
-Each delta is `encoded[i] - frame_of_reference`, computed in unsigned
(wrapping)
-arithmetic and stored as an unsigned integer. Computing it as unsigned avoids
-signed-integer overflow when the vector's range (`max - min`) exceeds the
signed
-maximum of the encoded type, and it means no sign extension is applied when
-unpacking. Because `frame_of_reference` is the minimum encoded integer in the
-vector, every delta is non-negative.
-
-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. Each value is stored as its
exact
-IEEE 754 bit pattern; implementations MUST NOT canonicalize NaN or otherwise
alter
-the bits, so that decoding reproduces the original value bit-for-bit.
-
-#### Encoding
-
-##### Encoding Formula
-
-```
-+-------------------------------------------------------------------+
-| |
-| encoded = fast_round( value * 10^e * 10^(-f) ) |
-| |
-| decoded = encoded * 10^f * 10^(-e) |
-| |
-+-------------------------------------------------------------------+
-```
-
-The formula uses two separate multiplications (not a single multiplication by
-`10^(e-f)`, and not division). This is a requirement of the **decode** path,
which
-is normative: to reconstruct a value every reader MUST compute
-`decoded = encoded * 10^f * 10^(-e)` using the same two-step multiplication
and the
-same power-of-10 constants, so that all implementations reproduce the stored
value
-bit-for-bit. The power-of-10 constants MUST be the correctly-rounded IEEE 754
-values of the decimal literals `1e0`, `1e1`, ..., `1e18` and `1e-1`, `1e-2`,
...,
-`1e-18` as defined by the decimal-to-binary conversion in IEEE 754-2008
§5.12.2.
-Implementations MUST NOT compute these constants at runtime via `pow()` or
-equivalent functions, which are not guaranteed to be correctly rounded.
-
-The **encode** direction — mapping each value to the integer it will be stored
as,
-via `fast_round(value * 10^e * 10^(-f))` — is informative, not normative. An
-encoder MAY choose that integer by any means, because every value is checked
-against the normative decode above and any value that does not round-trip
exactly
-is stored as an exception. The rounding method therefore affects only
compression
-ratio and exception count, never correctness or what a reader decodes. The
-`fast_round` technique below is one recommended implementation.
-
-##### Fast Rounding (informative)
-
-`fast_round` recovers the integer intended by `value * 10^e * 10^(-f)` — which
-carries floating-point rounding noise — by rounding it to the nearest integer
-(ties to even), without a division or a call to a library rounding function.
It is
-**not** normative: an encoder MAY use any rounding method, since values that
do not
-round-trip under the normative decode are stored as exceptions.
-
-The technique adds then subtracts a "magic number" (a power of two large
enough to
-discard the fractional bits), leaving the nearest integer. Implementations
vary:
-some apply it in a single branch-free form, others add a sign test.
-
-| Type | Magic Number | Formula (value ≥ 0)
| Formula (value < 0) |
-|--------|-----------------------------------|----------------------------------|----------------------------------|
-| FLOAT | 2^23 = 8,388,608 | `(int32_t)((value + magic) -
magic)` | `(int32_t)((value - magic) + magic)` |
-| DOUBLE | 2^52 = 4,503,599,627,370,496 | `(int64_t)((value + magic) -
magic)` | `(int64_t)((value - magic) + magic)` |
-
-The `value ± magic` operations must be evaluated in the value's own precision
-(FLOAT in binary32, DOUBLE in binary64); only the final cast converts to an
integer.
-The two forms round some large-magnitude inputs differently, but since any
value
-that fails to round-trip is stored as an exception, the choice affects only
-compression ratio, never correctness.
-
-##### Parameter Selection
-
-Any valid (exponent, factor) pair produces a correct encoding — the decoder is
-agnostic to the selection strategy, and the exception mechanism guarantees
-round-trip fidelity regardless of which pair is chosen. The choice only affects
-compression ratio.
-
-The encoder SHOULD select the (exponent, factor) pair that produces the
smallest
-encoded output. A simple heuristic is to minimize exception count; a more
precise
-approach accounts for both bit-width and exception overhead.
-
-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
-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,
-evaluate each candidate for the best compression.
-
-Suggested sampling parameters (from the paper):
-
-| Parameter | Value | Description |
-|----------------------|-------|-------------------------------------|
-| 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 | scaled value outside int32 (FLOAT) or int64 (DOUBLE) |
Exceeds target integer type range |
-| 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.
-
-##### Example: Frame of Reference and Bit-Packing
-
-Given the following data 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.
-
-#### Worked Example: Exceptions and Non-Zero Factor
-
-**Input:** `double values[4] = { 1500.0, NaN, 2500.0, 333.5 }`
-
-Best encoding found: (exponent=4, factor=3). This means:
-`encoded = fast_round(value * 10^4 * 10^(-3)) = fast_round(value * 10)`
-
-**Step 1: Decimal Encoding**
-
-| Index | Value | value * 10^4 * 10^(-3) | Rounded | Decoded: rounded * 10^3
* 10^(-4) | Exception? |
-|-------|---------|------------------------|---------|------------------------------------|------------|
-| 0 | 1500.0 | 15000.0 | 15000 | 1500.0
| No |
-| 1 | NaN | - | - | -
| Yes (NaN) |
-| 2 | 2500.0 | 25000.0 | 25000 | 2500.0
| No |
-| 3 | 333.5 | 3335.0 | 3335 | 333.5
| No |
-
-**Step 2: Handle Exceptions**
-
-Exception positions: \[1\]
-Exception values: \[NaN\]
-Placeholder: 15000 (first non-exception encoded value)
-Encoded with placeholders: \[15000, 15000, 25000, 3335\]
-
-**Step 3: Frame of Reference**
-
-| Encoded | min = 3335 | Delta |
-|--------------------|------------|-------|
-| 15000 | - | 11665 |
-| 15000 (placeholder)| - | 11665 |
-| 25000 | - | 21665 |
-| 3335 | - | 0 |
-
-**Step 4: Bit Packing**
-
-max\_delta = 21665, bit\_width = ceil(log2(21666)) = 15 bits,
-packed\_size = ceil(4 * 15 / 8) = 8 bytes
-
-**Serialized Vector:**
-
-| Section | Content |
Size |
-|---------------------|--------------------------------------------------|----------|
-| AlpInfo | e=4, f=3, num\_exceptions=1 | 4
bytes |
-| ForInfo | frame\_of\_reference=3335, bit\_width=15 | 9
bytes |
-| PackedValues | \[11665, 11665, 21665, 0\] at 15 bits each | 8
bytes |
-| ExceptionPositions | \[1\] | 2
bytes |
-| ExceptionValues | \[NaN\] | 8
bytes |
-| **Total** | |
**31 bytes** |
-
-Compared to PLAIN encoding (4 * 8 = 32 bytes). With 1024 values, the 13-byte
-vector header becomes negligible and compression ratios of 2-8x are typical.
-
+The detailed specification of the ALP encoding, including the page layout and
+the encoding and decoding procedures, is in [AlpEncoding.md](AlpEncoding.md).
