Arrow 和 Parquet 第 3 部分：使用结构体列表和列表结构体实现任意嵌套
发布 2022 年 10 月 17 日
作者： tustvold 和 alamb
简介
这是由三部分组成的系列文章中的第三部分，探讨了 Rust Apache Arrow 等项目如何支持在用于内存处理的 Apache Arrow 和用于高效存储的 Apache Parquet 之间进行转换。Apache Arrow 是一种开放、独立于语言的列式内存格式，用于平面和分层数据，旨在实现高效的分析操作。Apache Parquet 是一种开放的列式数据文件格式，旨在实现非常高效的数据编码和检索。
Arrow 和 Parquet 第 1 部分：基本类型和可为空性 介绍了基本类型。Arrow 和 Parquet 第 2 部分：使用结构体和列表的嵌套和分层数据 介绍了 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 实现，在 Arrow 或 Parquet 中读取和写入嵌套数据，或在两者之间进行转换，就像读取非嵌套数据一样简单。该库会自动处理所有复杂的记录分解和重建。凭借此功能和其他激动人心的功能，例如支持从对象存储异步读取，它是最快且功能最完整的 Rust Parquet 实现。我们期待看到您用它构建什么！