Skip to content

Latest commit

 

History

History
847 lines (668 loc) · 40.4 KB

Encodings.md

File metadata and controls

847 lines (668 loc) · 40.4 KB

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 page.

Encoding type Encoding enum Supported Types
Plain PLAIN = 0 All Physical Types
Dictionary Encoding PLAIN_DICTIONARY = 2 (Deprecated)
RLE_DICTIONARY = 8
All Physical Types
Run Length Encoding / Bit-Packing Hybrid RLE = 3 BOOLEAN, Dictionary Indices
Delta Encoding DELTA_BINARY_PACKED = 5 INT32, INT64
Delta-length byte array DELTA_LENGTH_BYTE_ARRAY = 6 BYTE_ARRAY
Delta Strings DELTA_BYTE_ARRAY = 7 BYTE_ARRAY, FIXED_LEN_BYTE_ARRAY
Byte Stream Split BYTE_STREAM_SPLIT = 9 INT32, INT64, FLOAT, DOUBLE, FIXED_LEN_BYTE_ARRAY
ALP ALP = 10 FLOAT, DOUBLE

Deprecated Encodings

Encoding type Encoding enum
Bit-packed (Deprecated) BIT_PACKED = 4

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 can not be used. It stores the data in the following format:

  • BOOLEAN: Bit Packed, LSB first
  • 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, followed by the bytes.

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 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 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 RLE/Bit packed 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.

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 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 at 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 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, 231 - 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 prepending the four-byte length to the encoded-data is summarized as 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               |
+--------------+------------------------+-----------------+

Bit-packed (Deprecated) (BIT_PACKED = 4)

This is a bit-packed only encoding, which is deprecated and will be replaced by the RLE/bit-packing 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 as 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 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 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.

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" 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 block 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 encoding. However the RLE/bit-packing 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.

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"

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.

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

Adaptive Lossless floating-Point: (ALP = 10)

Supported Types: FLOAT, DOUBLE

This encoding is adapted from the paper "ALP: Adaptive Lossless floating-Point Compression" 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

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. Only that byte layout and the 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 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 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.