Expand description
Row format as defined in arrow-rs.
This currently partially implements that format only for needed types.
For completeness sake the format as defined by arrow-rs is as followed:
Converts ArrayRef columns into a row-oriented format.
§Overview
The row format is a variable length byte sequence created by concatenating the encoded form of each column. The encoding for each column depends on its datatype (and sort options).
The encoding is carefully designed in such a way that escaping is unnecessary: it is never ambiguous as to whether a byte is part of a sentinel (e.g. null) or a value.
§Unsigned Integer Encoding
A null integer is encoded as a 0_u8, followed by a zero-ed number of bytes corresponding
to the integer’s length.
A valid integer is encoded as 1_u8, followed by the big-endian representation of the
integer.
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
3 │03│00│00│00│ │01│00│00│00│03│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
258 │02│01│00│00│ │01│00│00│01│02│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
23423 │7F│5B│00│00│ │01│00│00│5B│7F│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
NULL │??│??│??│??│ │00│00│00│00│00│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
32-bit (4 bytes) Row Format
Value Little Endian§Signed Integer Encoding
Signed integers have their most significant sign bit flipped, and are then encoded in the same manner as an unsigned integer.
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
5 │05│00│00│00│ │05│00│00│80│ │01│80│00│00│05│
└──┴──┴──┴──┘ └──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
-5 │FB│FF│FF│FF│ │FB│FF│FF│7F│ │01│7F│FF│FF│FB│
└──┴──┴──┴──┘ └──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
Value 32-bit (4 bytes) High bit flipped Row Format
Little Endian§Float Encoding
Floats are converted from IEEE 754 representation to a signed integer representation by flipping all bar the sign bit if they are negative after normalizing nans and signed zeros to a canonical representation.
They are then encoded in the same manner as a signed integer.
§Fixed Length Bytes Encoding
Fixed length bytes are encoded in the same fashion as primitive types above.
For a fixed length array of length n:
A null is encoded as 0_u8 null sentinel followed by n 0_u8 bytes
A valid value is encoded as 1_u8 followed by the value bytes
§Variable Length Bytes (including Strings) Encoding
A null is encoded as a 0_u8.
An empty byte array is encoded as 1_u8.
A non-null, non-empty byte array is encoded as 2_u8 followed by the byte array
encoded using a block based scheme described below.
The byte array is broken up into 32-byte blocks, each block is written in turn
to the output, followed by 0xFF_u8. The final block is padded to 32-bytes
with 0_u8 and written to the output, followed by the un-padded length in bytes
of this final block as a u8.
Note the following example encodings use a block size of 4 bytes, as opposed to 32 bytes for brevity:
┌───┬───┬───┬───┬───┬───┐
"MEEP" │02 │'M'│'E'│'E'│'P'│04 │
└───┴───┴───┴───┴───┴───┘
┌───┐
"" │01 |
└───┘
NULL ┌───┐
│00 │
└───┘
"Defenestration" ┌───┬───┬───┬───┬───┬───┐
│02 │'D'│'e'│'f'│'e'│FF │
└───┼───┼───┼───┼───┼───┤
│'n'│'e'│'s'│'t'│FF │
├───┼───┼───┼───┼───┤
│'r'│'a'│'t'│'r'│FF │
├───┼───┼───┼───┼───┤
│'a'│'t'│'i'│'o'│FF │
├───┼───┼───┼───┼───┤
│'n'│00 │00 │00 │01 │
└───┴───┴───┴───┴───┘This approach is loosely inspired by COBS encoding, and chosen over more traditional byte stuffing as it is more amenable to vectorisation, in particular AVX-256.
For the unordered row encoding we use a simpler scheme, we prepend the length encoded as 4 bytes followed by the raw data, with nulls being marked with a length of u32::MAX.
§Dictionary Encoding
RowsEncoded needs to support converting dictionary encoded arrays with unsorted, and
potentially distinct dictionaries. One simple mechanism to avoid this would be to reverse
the dictionary encoding, and encode the array values directly, however, this would lose
the benefits of dictionary encoding to reduce memory and CPU consumption.
As such the RowsEncoded creates an order-preserving mapping
for each dictionary encoded column, which allows new dictionary
values to be added whilst preserving the sort order.
A null dictionary value is encoded as 0_u8.
A non-null dictionary value is encoded as 1_u8 followed by a null-terminated byte array
key determined by the order-preserving dictionary encoding
┌──────────┐ ┌─────┐
│ "Bar" │ ───────────────▶│ 01 │
└──────────┘ └─────┘
┌──────────┐ ┌─────┬─────┐
│"Fabulous"│ ───────────────▶│ 01 │ 02 │
└──────────┘ └─────┴─────┘
┌──────────┐ ┌─────┐
│ "Soup" │ ───────────────▶│ 05 │
└──────────┘ └─────┘
┌──────────┐ ┌─────┐
│ "ZZ" │ ───────────────▶│ 07 │
└──────────┘ └─────┘
Example Order Preserving MappingUsing the map above, the corresponding row format will be
┌─────┬─────┬─────┬─────┐
"Fabulous" │ 01 │ 03 │ 05 │ 00 │
└─────┴─────┴─────┴─────┘
┌─────┬─────┬─────┐
"ZZ" │ 01 │ 07 │ 00 │
└─────┴─────┴─────┘
┌─────┐
NULL │ 00 │
└─────┘
Input Row Format§Struct Encoding
A null is encoded as a 0_u8.
A valid value is encoded as 1_u8 followed by the row encoding of each child.
This encoding effectively flattens the schema in a depth-first fashion.
For example
┌───────┬────────────────────────┬───────┐
│ Int32 │ Struct[Int32, Float32] │ Int32 │
└───────┴────────────────────────┴───────┘Is encoded as
┌───────┬───────────────┬───────┬─────────┬───────┐
│ Int32 │ Null Sentinel │ Int32 │ Float32 │ Int32 │
└───────┴───────────────┴───────┴─────────┴───────┘§List Encoding
Lists are encoded by first encoding all child elements to the row format.
A “canonical byte array” is then constructed by concatenating the row
encodings of all their elements into a single binary array, followed
by the lengths of each encoded row, and the number of elements, encoded
as big endian u32.
This canonical byte array is then encoded using the variable length byte encoding described above.
The lengths are not strictly necessary but greatly simplify decode, they may be removed in a future iteration.
For example given:
[1_u8, 2_u8, 3_u8]
[1_u8, null]
[]
nullThe elements would be converted to:
┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐
1 │01│01│ 2 │01│02│ 3 │01│03│ 1 │01│01│ null │00│00│
└──┴──┘ └──┴──┘ └──┴──┘ └──┴──┘ └──┴──┘Which would be grouped into the following canonical byte arrays:
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
[1_u8, 2_u8, 3_u8] │01│01│01│02│01│03│00│00│00│02│00│00│00│02│00│00│00│02│00│00│00│03│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
└──── rows ────┘ └───────── row lengths ─────────┘ └─ count ─┘
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
[1_u8, null] │01│01│00│00│00│00│00│02│00│00│00│02│00│00│00│02│
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘With [] represented by an empty byte array, and null a null byte array.
These byte arrays will then be encoded using the variable length byte encoding described above.
§Ordering
§Float Ordering
Floats are totally ordered just like in the rest of Polars, -inf < neg < -0.0 = 0.0 < pos < inf < nan, with all nans being equal.
§Null Ordering
The encoding described above will order nulls first, this can be inverted by representing
nulls as 0xFF_u8 instead of 0_u8
§Reverse Column Ordering
The order of a given column can be reversed by negating the encoded bytes of non-null values
Re-exports§
pub use encode::convert_columns;pub use encode::convert_columns_amortized;pub use encode::convert_columns_amortized_no_order;pub use encode::convert_columns_no_order;