polars-row

polars-row 是 Polars 库的一个 内部子crate，为 Polars DataFrame 库提供行编码。

重要说明：此crate不打算对外使用。请参阅主 Polars crate 了解预期用途。

lib.rs:

行格式如 arrow-rs 中定义。目前该格式仅部分实现了所需类型。为了完整性，arrow-rs 中定义的格式如下：将 ArrayRef 列转换为面向行格式。

概述

行格式是由每个列的编码形式连接而成的可变长度字节序列。每列的编码取决于其数据类型（以及排序选项）。

编码设计得非常精心，不需要转义：始终明确一个字节是哨兵（例如null）的一部分还是值的一部分。

无符号整数编码

空整数编码为一个 0_u8，后跟与整数长度对应的零个字节的零填充。

有效整数编码为一个 1_u8，后跟整数的big-endian表示形式。

              ┌──┬──┬──┬──┐      ┌──┬──┬──┬──┬──┐
   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

有符号整数编码

有符号整数将最高有效位（符号位）反转，然后以与无符号整数相同的方式编码。

       ┌──┬──┬──┬──┐       ┌──┬──┬──┬──┐       ┌──┬──┬──┬──┬──┐
    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

浮点数编码

浮点数通过将它们从IEEE 754表示形式转换为有符号整数表示形式进行编码，如果它们在规范化nans和有符号零到规范表示形式后为负，则翻转所有除符号位以外的位。

然后以与有符号整数相同的方式进行编码。

固定长度字节编码

固定长度字节以与上述原始类型相同的方式进行编码。

对于长度为 n 的固定长度数组

空值以 0_u8 空哨兵编码，其后跟随 n 个 0_u8 字节。

有效值以 1_u8 编码，其后跟随值字节。

可变长度字节（包括字符串）编码

空值以 0_u8 编码。

空字节数组以 1_u8 编码。

非空、非空字节数组以 2_u8 编码，其后跟随使用以下所述的基于块的方案编码的字节组。

字节组被分割成 32 字节块，每个块依次写入输出，后跟 0xFF_u8。最后一个块用 0_u8 补充到 32 字节，并写入输出，后跟这个最终块的未填充字节数作为 u8。

注意以下示例编码使用 4 字节块大小，而不是 32 字节以节省篇幅。

                      ┌───┬───┬───┬───┬───┬───┐
 "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 │
                          └───┴───┴───┴───┴───┘

这种方法在某种程度上受到 COBS 编码的启发，并被选择用于更传统的 字节填充，因为它更适合向量化，特别是 AVX-256。

字典编码

RowsEncoded 需要支持将字典编码的数组转换为未排序的，以及可能的字典。一种避免这种情况的简单机制是将字典编码反转，并直接编码数组值，但这将失去字典编码减少内存和 CPU 消耗的好处。

因此，RowsEncoded 为每个字典编码列创建一个顺序保持映射，这允许在保持排序顺序的同时添加新的字典值。

空字典值以 0_u8 编码。

非空字典值以 1_u8 编码，后跟由顺序保持字典编码确定的空终止字节键数组。

┌──────────┐                 ┌─────┐
│  "Bar"   │ ───────────────▶│ 01  │
└──────────┘                 └─────┘
┌──────────┐                 ┌─────┬─────┐
│"Fabulous"│ ───────────────▶│ 01  │ 02  │
└──────────┘                 └─────┴─────┘
┌──────────┐                 ┌─────┐
│  "Soup"  │ ───────────────▶│ 05  │
└──────────┘                 └─────┘
┌──────────┐                 ┌─────┐
│   "ZZ"   │ ───────────────▶│ 07  │
└──────────┘                 └─────┘

Example Order Preserving Mapping

使用上面的映射，相应的行格式将是

                          ┌─────┬─────┬─────┬─────┐
   "Fabulous"             │ 01  │ 03  │ 05  │ 00  │
                          └─────┴─────┴─────┴─────┘

                          ┌─────┬─────┬─────┐
   "ZZ"                   │ 01  │ 07  │ 00  │
                          └─────┴─────┴─────┘

                          ┌─────┐
    NULL                  │ 00  │
                          └─────┘

     Input                  Row Format

结构编码

空值以 0_u8 编码。

有效值以 1_u8 编码，其后跟随每个子结构的行编码。

这种编码实际上以深度优先的方式简化了模式。

例如

┌───────┬────────────────────────┬───────┐
│ Int32 │ Struct[Int32, Float32] │ Int32 │
└───────┴────────────────────────┴───────┘

编码为

┌───────┬───────────────┬───────┬─────────┬───────┐
│ Int32 │ Null Sentinel │ Int32 │ Float32 │ Int32 │
└───────┴───────────────┴───────┴─────────┴───────┘

列表编码

通过首先将所有子元素编码为行格式来编码列表。

然后构建一个“规范字节组”，将所有元素的行编码连接成一个单一的二进制数组，后跟每个编码行的长度和元素数量，编码为大端 u32。

然后使用上述可变长度字节编码对规范字节组进行编码。

长度不是必需的，但极大地简化了解码，可能在未来的迭代中删除。.

例如，给定

[1_u8, 2_u8, 3_u8]
[1_u8, null]
[]
null

元素将被转换为

    ┌──┬──┐     ┌──┬──┐     ┌──┬──┐     ┌──┬──┐        ┌──┬──┐
 1  │01│01│  2  │01│02│  3  │01│03│  1  │01│01│  null  │00│00│
    └──┴──┘     └──┴──┘     └──┴──┘     └──┴──┘        └──┴──┘

这将分组到以下规范字节组中

                        ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
 [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│
                        └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

使用 [] 表示一个空字节数组，以及 null 表示一个空字节数组。

然后，这些字节数组将使用上述描述的可变长度字节编码进行编码。

排序

浮点数排序

浮点数在 Polars 中是全序的，与 Polars 的其余部分相同，即 -inf < neg < -0.0 = 0.0 < pos < inf < nan，所有 nan 都相等。

空值排序

上述编码将首先对空值进行排序，可以通过将空值表示为 0xFF_u8 而不是 0_u8 来反转排序。

反向列排序

可以通过对非空值的编码字节取反来反转给定列的顺序。