列式存储的 Repetition Level 与 Definition Level

Parquet 的 Repetition Level（重复层级和 Definition Level（定义层级） 是处理嵌套数据结构的关键机制，尤其在列式存储中高效编码和重建复杂数据。

我们结合 Dremel 论文的例子，用通俗的方式解释它们。

1. 核心概念

Repetition Level（重复层级）

• • 作用：标记当前值在嵌套结构的哪个层级开始重复。
• • 通俗理解：当遇到一个数组或列表时，它告诉我们“当前值属于哪个层级的重复结构”。例如，一个用户有多个联系人，每个联系人有多个电话，Repetition Level 会标记电话属于哪个联系人。

Definition Level（定义层级）

• • 作用：标记当前值在嵌套结构中的存在深度。
• • 通俗理解：如果某个字段是可选的（比如 null），Definition Level 会告诉我们“这个字段的父级路径存在到哪里”。例如，如果字段 a.b.c 存在，而路径 a.b 是必需的，但 c 是可选的，Definition Level 会表示 c 是否存在。

2. Dremel 论文的例子

假设有一个嵌套的 Schema（简化版）：

message Document {
optionalint64 doc_id;
repeatedgroup Links {
optionalstring backward;
optionalstring forward;
  }
repeatedgroup Name {
repeatedgroup Language {
requiredstring code;
optionalstring country;
    }
optionalstring url;
  }
}

数据示例

假设一条数据：

{
  doc_id:10,
  Links:[
{ backward:"d1", forward:"d2"},
{ backward:"d3", forward:"d4"}
],
  Name:[
{
      Language:[
{ code:"en", country:"us"},
{ code:"zh"}
],
      url:"http://example.com"
},
{
      Language:[
{ code:"fr", country:null}// country 显式设为 null
]
}
]
}

3. 具体场景分析：字段：Name.Language.code

• • 路径层级：Document > Name (repeated) > Language (repeated) > code (required)。
• • 可能的取值："en", "zh", "fr"。

（1）Repetition Level

• • 规则：当某个层级发生重复时，标记重复的起始层级。
• • 示例：
• • 第一个 Name 的第一个 Language 的 code="en"：
  Repetition Level = 0（新文档开始）。
• • 第一个 Name 的第二个 Language 的 code="zh"：
  Repetition Level = 2（在 Language 层级重复）。
• • 第二个 Name 的第一个 Language 的 code="fr"：
  Repetition Level = 1（在 Name 层级重复）。

（2）Definition Level

• • 规则：路径中存在多少可选字段被定义（即非 null）。
• • 路径深度：Document(0) > Name(1) > Language(2) > code(3)，其中 Name 和 Language 是重复的，但 code 是必选的。
• • 示例：
• • code="en"：Definition Level = 3（所有父级都存在）。
• • 如果某个 Language 的 code 缺失（但 Schema 中 code 是必选的，这种情况不会发生）。

Name.Language.code 数据存储与重建

假设字段 Name.Language.code 的列存储如下：

• • 解析过程：

1. 1. en（Rep=0）：从文档根开始，创建第一个 Name，第一个 Language，写入 code="en"。
2. 2. zh（Rep=2）：在最近的 Language 层级重复，写入第二个 Language，code="zh"。
3. 3. fr（Rep=1）：在最近的 Name 层级重复，创建第二个 Name，第一个 Language，写入 code="fr"。

4. 具体场景分析：字段：Name.Language.country

• • 路径层级：Document > Name (repeated) > Language (repeated) > country (optional)。
• • 路径深度：Document(0) > Name(1) > Language(2) > country(3)。
• • Name 和 Language 是重复的（不影响 Definition Level）。
• • country 是可选字段（影响 Definition Level）。

(1) Repetition Level

• • 规则：当某个层级发生重复时，标记重复的起始层级。
• • 示例：
• • 第一个 Name 的第一个 Language 的 country="us"：
  Repetition Level = 0（新文档开始）。
• • 第一个 Name 的第二个 Language 的 country 缺失：
  Repetition Level = 2（在 Language 层级重复）。
• • 第二个 Name 的第一个 Language 的 country=null：
  Repetition Level = 1（在 Name 层级重复）。

(2)Definition Level 规则

• • Definition Level = 路径中已存在的可选字段数量（从根到当前字段）。
• • 当字段为 null 时，Definition Level 表示“路径中存在到哪个层级”。

Name.Language.country 数据存储与重建

假设 Name.Language.country 的存储如下：

解析过程

1. 1. "us"（Rep=0, Def=3）：

• • 从根开始，创建第一个 Name 和第一个 Language，写入 country="us"。

• • 在 Language 层级重复，创建第二个 Language，但 country 未定义（路径仅到 Language）。

• • 在 Name 层级重复，创建第二个 Name 和第一个 Language，写入 country=null。

5. 总结

• • Repetition Level：回答“当前值从哪个层级开始重复”，用于重建数组的嵌套结构。
• • Definition Level：回答“当前值的父级路径存在到哪里”，用于处理可选字段（如 null）。

通过这两个层级，Parquet可以在列式存储中高效编码嵌套数据，并在读取时准确重建原始结构。