JSON 优化

• RFC PR: datafuselabs/databend#6995
• Tracking Issue: datafuselabs/databend#6994

概要

本 RFC 描述了 JSON 性能优化的设计。

动机

目前，Databend 半结构化数据以原始文本 JSON 格式存储，并使用 serde_json 进行序列化和反序列化。 它存在以下性能问题：

1. 每次使用 JSON 都必须进行解析，而文本解析非常慢，特别是对于大型复杂对象数据。
2. 查询单个键路径需要读取和解析整个 JSON 数据，这会花费更多的解析时间并占用更多的内存。

为了使半结构化数据的查询性能与其他数据类型一样快。本 RFC 引入了以下两个提案：

• 自动检测 JSON 列中经常查询的键路径，并将它们提取为虚拟列，以实现与其他列类似的查询性能。
• 使用 JSONB 而不是 JSON 作为半结构化数据类型的底层二进制编码格式，这将优化解析速度并有利于键路径访问。

指导性解释

无。

参考性解释

虚拟列

JSON 的 schema 可以任意更改。但是，在实际使用中，JSON 数据通常由机器生成，并且具有相当严格和可预测的结构。 利用此功能，我们可以检测和提取 JSON 中经常查询的键路径作为虚拟列，以加速查询处理。

收集经常访问的 JSON 键路径

提取和存储虚拟列需要额外的解析过程和存储资源，因此为所有键路径生成虚拟列是不合适的。 我们应该只为经常查询的 JSON 键路径生成虚拟列。

为了知道哪些键路径经常被查询， 我们使用 FPGrowth 算法 来统计 JSON 数据键路径的访问频率。 "FP" 代表频繁模式，通常用于计算项目频率并识别频繁项目。 每次用户查询 JSON 数据的某个键路径时，FPGrowth 算法都会记录它，最终生成一个树状的统计信息。 我们可以使用此统计信息来确定哪些键路径需要生成虚拟列。

提取虚拟列

提取虚拟列的操作是异步执行的，因此不会影响数据插入的性能。 由于 Databend 会定期压缩表块，我们可以将提取虚拟列作为一项附加操作，如果列数据类型为 JSON。 这样，可以重用为压缩而读取的数据，这将减少不必要的读取放大。

提取虚拟列的过程如下：

1. 收集访问计数超过 FPGrowth 算法生成的阈值的键路径。
2. 解析 JSON 数据，推断所有键路径的 JSON schema，包括值的类型和行号。
3. 检查所有键路径，如果值的类型相同，并且每行都有数据，则从此键路径提取数据以生成虚拟列并将其存储在单独的 parquet 文件中。

以下面的 JSON 为例。

{"id":1,"title":"a","user":{"id":1,"name":"a"},"tags":["t1","t2"]}
{"id":2,"title":"b","user":{"id":2,"name":"b"},"tags":["t3","t4"]}
{"id":3,"title":"c","user":{"id":3,"name":3}}
{"id":4,"title":"d","user":{"id":4,"name":4}}

键路径 id、title 和 user:id 具有相同的数据类型，我们可以将它们提取为虚拟列。 对于 user.name，值的类型不同。 对于 tags，它不在每一行上。我们不为它们生成虚拟列。

将键路径访问下推到存储

有两种访问 json 键路径的方式：点表示法，例如 col:level1:level2 和括号表示法，例如 col['level1'][0]。

例如：

create table test (id int8, v json);
insert into test values(1, parse_json('{"k1":{"k2":"v"},"a":[0,1,2]}'));
select v:k1:k2, v['a'][0] from test;
+---------+-----------+
| v:k1:k2 | v['a'][0] |
+---------+-----------+
| "v"     | 0         |
+---------+-----------+

目前，JSON 键路径的访问将被转换为一个 get 标量函数，并通过键遍历 JSON 以获取值。 为了使用虚拟列来提高性能，我们需要修改查询计划并将键路径的访问下推到存储层。 由于我们使用 JSONB 而不是 JSON，即使对于没有生成虚拟列的键路径，下推到存储层也会带来好处。

JSONB

JSONB 代表 JSON Binary 或 JSON better，它是由 PostgreSQL 自 v9.4 以来支持的一种优化的二进制格式数据类型。 CockroachDB 也基于 PostgreSQL 设计实现了 JSONB。

通过将数据存储为 JSONB 而不是 JSON，我们可以获得以下好处：

• JSONB 的解析和查询过程明显更快。
• 访问特定的键路径不需要读取完整的数据，这将大大提高整体性能。
• 可以添加外部索引以进一步加速查询。

二进制编码

JSONB 是一个树结构。每个节点由三个部分组成，一个 32 位标头，几个 32 位 JEntry 和可变长度的原始内容。

• 标头也称为容器标头，它包括一个 3 位类型（包括 array、object 和 scalar）和一个 28 位来指示 array 或 object 中的元素数量。
• JEntry 具有一个 3 位值类型（包括 true、false、null、string、number、array 和 object），一个 28 位提供原始内容的长度或偏移量，以及一个 1 位标志来指示是使用长度还是偏移量。
• 最后一部分是原始内容值，可以通过 JEntry 中的长度或偏移量来定位。

以下面的 JSON 为例，我们可以看到 JSONB 的编码格式如下。

{ "a": 1, "b": [true, 2, "v"] }

  .--------------.    .-----------------------------------.
  |    header    | -> |    type(object) | item nums(2)    |
  .--------------.    .-----------------------------------.
  | key1 JEntry  | -> | flag | val type(string) | len/off | -+
  .--------------.    .-----------------------------------.  |
  | key2 JEntry  | -> | flag | val type(string) | len/off | -+-+
  .--------------.    .-----------------------------------.  | |
  | val1 JEntry  | -> | flag | val type(number) | len/off | -+-+-+
  .--------------.    .-----------------------------------.  | | |
  | val2 JEntry  | -> | flag | val type(string) | len/off | -+-+-+-+
  .--------------.    .-----------------------------------.  | | | |
  |     "a"      | <-----------------------------------------+ | | |
  .--------------.                                             | | |
  |     "b"      | <-------------------------------------------+ | |
  .--------------.                                               | |
  |      1       | <---------------------------------------------+ |
  .--------------.                                                 |
  | [true,2,"v"] | <-----------------------------------------------+
  .--------------.
        |           .--------------+    .-----------------------------------.
        +---------> |    header    | -> |    type(array) | item nums(3)     |
                    .--------------+    .-----------------------------------.
                    | item1 JEntry | -> | flag | val type(bool true)        |
                    .--------------+    .-----------------------------------.
                    | item2 JEntry | -> | flag | val type(number) | len/off | -+
                    .--------------+    .-----------------------------------.  |
                    | item3 JEntry | -> | flag | val type(string) | len/off | -+-+
                    .--------------+    .-----------------------------------.  | |
                    |      2       | <-----------------------------------------+ |
                    .--------------.                                             |
                    |     "v"      | <-------------------------------------------+
                    .--------------.

有关更多详细信息，请参见 PostgreSQL 和 CockroachDB 的设计

受益于 JSONB 的树结构，搜索键路径只需要解析部分完整数据。 在每个节点中，对象键可以以 O(𝑙𝑜𝑔(𝑛)) 的时间复杂度访问，因为键已排序并且可以使用二分查找，并且数组元素可以以 O(1) 的时间复杂度访问，因为 JEntry 的长度是固定的。

缺点

• 提取虚拟列需要额外的异步任务。
• JSONB 可能比 JSON 占用更多的磁盘空间。

理由和替代方案

BSON 是 MongoDB 中使用的一种二进制 JSON 格式。 它的主要设计目标是存储文档，因此它在标头中没有键路径的索引。

ION 也是由亚马逊开发的二进制 JSON 格式。 它针对读取进行了优化，并具有符号表作为索引以加速键路径访问。 它的主要问题是 Rust 版本的开发仍处于早期阶段，并且缺少一些重要的 trait 支持，例如 serde。

还有一些针对纯文本 json 的优化，例如 simd-json 使用 SIMD 指令来加速解析， Pison 通过添加位图索引来加速解析。 但是它们针对完整数据的解析进行了优化，这无助于通过键路径加速访问。

先前技术

本 RFC 的主要思想来自 JSON Tiles 论文。 该论文中的实验评估表明，这些优化可以有效地提高 JSON 数据的读取性能。

PostgreSQL 和 CockroachDB 都使用 JSONB 作为优化的 JSON 格式，我们可以基于它们的设计实现 Rust 版本的 JSONB。

未解决的问题

无。

未来可能性

• 提取具有不同数据类型值的键路径的虚拟列
• 为 JSONB 添加额外的索引