Apache Arrow Rust 中快速且内存高效的多列排序，第 2 部分
已发布 2022 年 11 月 7 日
作者 tustvold 和 alamb
引言
在本篇文章的第 1 部分中，我们描述了多列排序问题及其高效实现的挑战。第二部分将解释Apache Arrow 的 Rust 实现中新的行格式是如何工作和构建的。
行格式
行格式是一个可变长度的字节序列，通过连接每一列的编码形式创建。每一列的编码取决于其数据类型（和排序选项）。
┌─────┐ ┌─────┐ ┌─────┐
│ │ │ │ │ │
├─────┤ ┌ ┼─────┼ ─ ┼─────┼ ┐ ┏━━━━━━━━━━━━━┓
│ │ │ │ │ │ ─────────────▶┃ ┃
├─────┤ └ ┼─────┼ ─ ┼─────┼ ┘ ┗━━━━━━━━━━━━━┛
│ │ │ │ │ │
└─────┘ └─────┘ └─────┘
...
┌─────┐ ┌ ┬─────┬ ─ ┬─────┬ ┐ ┏━━━━━━━━┓
│ │ │ │ │ │ ─────────────▶┃ ┃
└─────┘ └ ┴─────┴ ─ ┴─────┴ ┘ ┗━━━━━━━━┛
Customer State Orders
UInt64 Utf8 F64
Input Arrays Row Format
(Columns)
编码经过精心设计，无需转义：字节是属于标记（例如 null）还是值的一部分始终是明确的。
无符号整数
要编码非空无符号整数，先写入字节 0x01，然后写入整数的字节，从最高有效位开始，即大端序。空值编码为 0x00 字节，后跟整数零值的编码字节。
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
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
有符号整数
在 Rust 和大多数现代计算机体系结构中，有符号整数使用二进制补码进行编码，其中数字通过翻转所有位并加 1 来取反。因此，翻转最高位并将结果视为无符号整数可以保持顺序。然后可以使用上一节中描述的无符号整数编码对该无符号整数进行编码。例如
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
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 totalOrder 谓词（在 Rust 中由 f32::total_cmp 实现）进行排序。此排序将浮点值的字节解释为相应大小的有符号小端整数，在负数的情况下翻转除符号位之外的所有位。
因此，通过将浮点值转换为适当大小的有符号整数表示形式，然后使用上一节中描述的有符号整数的相同编码，将浮点值编码为行格式。
字节数组（包括字符串）
与上面的基本类型不同，字节数组是可变长度的。对于短字符串，例如上面示例中的 state，可以使用某些固定值（例如 0x00）将所有值填充到最长字符串的长度，并生成固定长度的行。这是 DuckDB 博客中描述的用于编码 c_birth_country 的方法。
然而，字符串列中的值通常长度差异很大，或者在执行开始时不知道最大长度，因此建议和/或不切实际地将字符串填充到固定长度。因此，Rust Arrow 行格式使用可变长度编码。
我们需要一种能够明确终止字节数组末尾的编码。这不仅允许从行格式中恢复原始值，还可以确保在与包含较短字节数组的行进行比较时，较长字节数组的字节不会与来自不同列的字节进行比较。
空字节数组编码为单个 0x00 字节。类似地，空字节数组编码为单个 0x01 字节。
要编码非空、非空数组，首先写入单个 0x02 字节。然后以 32 字节块的形式写入数组，每个完整块后跟一个 0xFF 字节作为继续标记。最后一个块用 0x00 填充到 32 字节，然后是此最后一个块的未填充长度，作为单个字节代替继续标记。
请注意，以下示例编码使用 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'│'i'│FF │
├───┼───┼───┼───┼───┤
│'o'│'n'│00 │00 │02 │
└───┴───┴───┴───┴───┘
这种方法的灵感来自COBS 编码，并且选择它而不是更传统的字节填充，因为它更适合于向量化，特别是具有 AVX-256 的硬件可以在一条指令中复制一个 32 字节的块。
字典数组
字典编码数据（在 pandas 中称为分类）越来越重要，因为它们可以非常有效地存储和处理低基数数据。
编码字典数组的一种简单方法是使用前面描述的基本值的编码直接编码逻辑值。但是，这将失去字典编码减少内存和 CPU 消耗的优势。
为了使事情进一步复杂化，字典编码的 Arrow 实现 非常通用，我们无法对字典的内容做出任何假设。特别是，我们不能假设字典值已排序，也不能假设列中的所有数组都使用相同的字典。
以下示例显示了如何使用两个不同的字典在两个数组中编码字符串列。第一批中的字典键 0、1 和 2 对应于与第二个字典中相同键不同的值。
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
┌───────────┐ ┌─────┐ │
│ │"Fabulous" │ │ 0 │
├───────────┤ ├─────┤ │
│ │ "Bar" │ │ 2 │
├───────────┤ ├─────┤ │ ┌───────────┐
│ │ "Soup" │ │ 2 │ │"Fabulous" │
└───────────┘ ├─────┤ │ ├───────────┤
│ │ 0 │ │ "Soup" │
├─────┤ │ ├───────────┤
│ │ 1 │ │ "Soup" │
└─────┘ │ ├───────────┤
│ │"Fabulous" │
Values │ ├───────────┤
│ Dictionary (indexes in │ "Bar" │
dictionary) │ ├───────────┤
│ │ "ZZ" │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ├───────────┤
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │ "Bar" │
│ ├───────────┤
│ ┌───────────┐ ┌─────┐ │ "ZZ" │
│"Fabulous" │ │ 1 │ │ ├───────────┤
│ ├───────────┤ ├─────┤ │"Fabulous" │
│ "ZZ" │ │ 2 │ │ └───────────┘
│ ├───────────┤ ├─────┤
│ "Bar" │ │ 1 │ │
│ └───────────┘ ├─────┤
│ 0 │ │ Logical column
│ └─────┘ values
Values │
│ Dictionary (indexes in
dictionary) │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
允许我们有效地为此类数据创建行格式的关键观察结果是，给定一个字节数组，始终可以通过添加一个附加字节来创建在排序顺序中位于其之前或之后的新的字节数组。
因此，我们可以逐步构建从字典值到可变长度字节数组的保序映射，而无需事先知道所有可能的字典值，而是在遇到新字典值时引入映射。
┌──────────┐ ┌─────┐
│ "Bar" │ ───────────────▶│ 01 │
└──────────┘ └─────┘
┌──────────┐ ┌─────┬─────┐
│"Fabulous"│ ───────────────▶│ 01 │ 02 │
└──────────┘ └─────┴─────┘
┌──────────┐ ┌─────┐
│ "Soup" │ ───────────────▶│ 05 │
└──────────┘ └─────┘
┌──────────┐ ┌─────┐
│ "ZZ" │ ───────────────▶│ 07 │
└──────────┘ └─────┘
Example Order Preserving Mapping
用于生成此映射的数据结构的详细信息超出了本博客文章的范围，但可能是未来文章的主题。 你可以在这里找到代码。
数据结构还确保没有值包含 0x00，因此我们可以使用 0x00 作为结束分隔符直接对数组进行编码。
空值编码为单个 0x00 字节，非空值编码为单个 0x01 字节，后跟由保序映射确定的 0x00 终止的字节数组。
┌─────┬─────┬─────┬─────┐
"Fabulous" │ 01 │ 03 │ 05 │ 00 │
└─────┴─────┴─────┴─────┘
┌─────┬─────┬─────┐
"ZZ" │ 01 │ 07 │ 00 │
└─────┴─────┴─────┘
┌─────┐
NULL │ 00 │
└─────┘
Input Row Format
排序选项
到目前为止，我们忽略的一个细节是如何支持升序和降序排序（例如 SQL 中的 ASC 或 DESC）。Arrow Rust 行格式通过简单地反转编码表示的字节（每列为基础）来支持这些选项，但用于可空性编码的初始字节除外。
类似地，支持 SQL 兼容排序还需要一种格式，该格式可以指定 NULL 的顺序（在所有非 NULL 值之前或之后）。行格式通过可选地将 null 编码为 0xFF 而不是 0x00（每列为基础）来支持此选项。
结论
希望这两篇文章能让您了解可比较行格式的可能性及其工作原理。请随时查看文档以获取入门说明，并在我们的错误追踪器上报告任何问题。
使用这种格式进行字典排序比基于比较器的方法快3 倍以上，尤其是在字符串、字典和具有大量列的排序方面优势更为明显。
我们还使用它将DataFusion 项目中保持排序的合并性能提高了一倍以上，并且随着我们将其应用于排序、分组、连接和窗口函数运算符，我们预计性能将得到类似或更大的提升。
与往常一样，Arrow 社区非常期待看到您使用它构建的内容！