Arrow 与 Parquet 第三部分：使用结构体列表和列表结构体实现任意嵌套
已发布 2022 年 10 月 17 日
作者 tustvold 和 alamb
引言
这是三部分系列文章的第三篇，探讨了诸如 Rust Apache Arrow 之类的项目如何支持内存处理格式 Apache Arrow 和高效存储格式 Apache Parquet 之间的转换。 Apache Arrow 是一种开放的、与语言无关的列式内存格式，用于平面和分层数据，旨在实现高效的分析操作。 Apache Parquet 是一种开放的、面向列的数据文件格式，旨在实现非常高效的数据编码和检索。
Arrow 与 Parquet 第一部分：基本类型和可空性 涵盖了基本类型的基础知识。 Arrow 与 Parquet 第二部分：使用结构体和列表的嵌套和分层数据 涵盖了 Struct 和 List 类型。本文在此基础上展示了两种格式如何结合起来支持任意嵌套。
一些库，例如 Rust 的 parquet 实现，提供了对此类组合的完整支持，这些库的用户无需担心这些细节，除非是为了满足自己的好奇心。其他库可能无法处理某些极端情况，本文将说明为何如此复杂。
包含列表的结构体
考虑以下三个 JSON 文档
{ # <-- First record
"a": [1], # <-- top-level field a containing list of integers
"b": [ # <-- top-level field b containing list of structures
{ # <-- list element of b containing two field b1 and b2
"b1": 1 # <-- b1 is always provided (non nullable)
},
{
"b1": 1,
"b2": [ # <-- b2 contains list of integers
3, 4 # <-- list elements of b.b2 always provided (non nullable)
]
}
]
}
{
"b": [ # <-- b is always provided (non nullable)
{
"b1": 2
},
]
}
{
"a": [null, null], # <-- list elements of a are nullable
"b": [null] # <-- list elements of b are nullable
}
这种格式的文档可以存储在此 Arrow 模式中
Field(name: "a", nullable: true, datatype: List(
Field(name: "element", nullable: true, datatype: Int32),
)
Field(name: "b"), nullable: false, datatype: List(
Field(name: "element", nullable: true, datatype: Struct[
Field(name: "b1", nullable: false, datatype: Int32),
Field(name: "b2", nullable: true, datatype: List(
Field(name: "element", nullable: false, datatype: Int32)
))
])
))
如前所述，Arrow 选择以分层方式表示这一点。 StructArray 存储为包含结构体每个字段的子数组。 ListArray 存储为单调递增的整数列表（称为偏移量），其值存储在单个子数组中。偏移量数组中每对连续的元素标识该数组索引的子数组切片。
该示例的 Arrow 编码为
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
┌──────────────────┐
│ ┌─────┐ ┌─────┐ │ ┌─────┐ ┌─────┐│ │
│ 1 │ │ 0 │ │ │ 1 │ │ 1 ││
│ ├─────┤ ├─────┤ │ ├─────┤ ├─────┤│ │
│ 0 │ │ 1 │ │ │ 0 │ │ ?? ││
│ ├─────┤ ├─────┤ │ ├─────┤ ├─────┤│ │
│ 1 │ │ 1 │ │ │ 0 │ │ ?? ││
│ └─────┘ ├─────┤ │ └─────┘ └─────┘│ │
│ 3 │ │ Validity Values│
│ Validity └─────┘ │ │ │
│ child[0] │
│ "a" Offsets │ PrimitiveArray │ │
ListArray └──────────────────┘
└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │
│ ┌──────────┐ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
┌─────┐ │ ┌─────┐ │ ┌─────┐ │ ┌─────┐ ┌─────┐ ┌──────────┐ │ │ │
│ │ 0 │ │ 1 │ │ │ 1 │ │ │ │ 0 │ │ 0 │ │ ┌─────┐ │
├─────┤ │ ├─────┤ │ ├─────┤ │ ├─────┤ ├─────┤ │ │ 3 │ │ │ │ │
│ │ 2 │ │ 1 │ │ │ 1 │ │ │ │ 1 │ │ 0 │ │ ├─────┤ │
├─────┤ │ ├─────┤ │ ├─────┤ │ ├─────┤ ├─────┤ │ │ 4 │ │ │ │ │
│ │ 3 │ │ 1 │ │ │ 2 │ │ │ │ 0 │ │ 2 │ │ └─────┘ │
├─────┤ │ ├─────┤ │ ├─────┤ │ ├─────┤ ├─────┤ │ │ │ │ │
│ │ 4 │ │ 0 │ │ │ ?? │ │ │ │ ?? │ │ 2 │ │ Values │
└─────┘ │ └─────┘ │ └─────┘ │ └─────┘ ├─────┤ │ │ │ │ │
│ │ │ │ │ 2 │ │ │
Offsets │ Validity│ Values │ └─────┘ │ │ │ │ │
│ │ │ │Validity │ child[0] │
│ │ "b1" │ Offsets │ Primitive│ │ │ │
│ │ Primitive│ │ "b2" │ Array │
│ │ Array │ ListArray └──────────┘ │ │ │
│ └──────────┘ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ "element" │ │
│ StructArray
"b" └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │
│ ListArray
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
这种格式的文档可以存储在此 Parquet 模式中
message schema {
optional group a (LIST) {
repeated group list {
optional int32 element;
}
}
required group b (LIST) {
repeated group list {
optional group element {
required int32 b1;
optional group b2 (LIST) {
repeated group list {
required int32 element;
}
}
}
}
}
}
正如我们之前的文章所解释的，Parquet 使用重复级别和定义级别来编码嵌套结构和可空性。
定义级别和重复级别是一个非平凡的主题。有关更多详细信息，您可以阅读 Google Dremel 论文，该论文提供了该算法的学术描述。您还可以浏览此 gist 以查看生成以下示例的 Rust parquet 代码。
该示例的 Parquet 编码为
┌───────────────────────────────┐ ┌────────────────────────────────┐
│ ┌─────┐ ┌─────┐ ┌─────┐ │ │ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ 3 │ │ 0 │ │ 1 │ │ │ │ 2 │ │ 0 │ │ 1 │ │
│ ├─────┤ ├─────┤ └─────┘ │ │ ├─────┤ ├─────┤ ├─────┤ │
│ │ 0 │ │ 0 │ │ │ │ 2 │ │ 1 │ │ 1 │ │
│ ├─────┤ ├─────┤ Data │ │ ├─────┤ ├─────┤ ├─────┤ │
│ │ 2 │ │ 0 │ │ │ │ 2 │ │ 0 │ │ 2 │ │
│ ├─────┤ ├─────┤ │ │ ├─────┤ ├─────┤ └─────┘ │
│ │ 2 │ │ 1 │ │ │ │ 1 │ │ 0 │ │
│ └─────┘ └─────┘ │ │ └─────┘ └─────┘ Data │
│ │ │ │
│Definition Repetition │ │ Definition Repetition │
│ Levels Levels │ │ Levels Levels │
│ │ │ │
│ "a" │ │ "b.b1" │
└───────────────────────────────┘ └────────────────────────────────┘
┌───────────────────────────────┐
│ ┌─────┐ ┌─────┐ ┌─────┐│
│ │ 2 │ │ 0 │ │ 3 ││
│ ├─────┤ ├─────┤ ├─────┤│
│ │ 4 │ │ 1 │ │ 4 ││
│ ├─────┤ ├─────┤ └─────┘│
│ │ 4 │ │ 2 │ │
│ ├─────┤ ├─────┤ │
│ │ 2 │ │ 0 │ │
│ ├─────┤ ├─────┤ Data │
│ │ 1 │ │ 0 │ │
│ └─────┘ └─────┘ │
│Definition Repetition │
│ Levels Levels │
│ │
│ "b.b2" │
└───────────────────────────────┘
其他复杂情况
本系列文章必然会忽略一些使实际实现更加复杂的细节
ListArray可能包含一个被有效性掩码屏蔽的非空偏移量范围- 从可空字段读取给定数量的行需要读取定义级别并根据存在的空值数量确定要读取的值的数量
- 从重复字段读取给定数量的行需要读取重复级别并根据重复级别 0 检测新行
- Parquet 文件可能包含多个行组，每个行组包含多个列块
- 一个列块可能包含多个页面，并且跨列的页面之间没有关系
- Parquet 具有用于表示具有不同可空性级别的列表的替代模式
- 以及更多…
总结
Parquet 和 Arrow 都是列式格式，并支持嵌套结构体和列表，但是，它们表示这种嵌套的方式却大不相同，两种格式之间的转换很复杂。
幸运的是，使用 Rust parquet 实现，在 Parquet 中读取和写入 Arrow 中的嵌套数据或在两者之间进行转换与读取非嵌套数据一样简单。该库自动处理所有复杂的记录分解和重构。凭借此功能和其他令人兴奋的功能，例如支持从 对象存储 异步读取，它是目前最快、功能最齐全的 Rust parquet 实现。我们期待看到您使用它构建什么！