JSON 优化
- RFC PR: datafuselabs/databend#6995
- 跟踪问题: datafuselabs/databend#6994
概述
本 RFC 描述了 JSON 性能优化的设计。
动机
目前，Databend 半结构化数据以原始文本 JSON 格式存储，并使用 serde_json 进行序列化和反序列化。
它存在以下性能问题：
- JSON 每次使用时都必须解析，而文本解析非常慢，尤其是对于大型复杂对象数据。
- 查询单个键路径需要读取和解析整个 JSON 数据，这需要更多的解析时间和占用更多的内存。
为了使半结构化数据的查询性能与其他数据类型一样快。本 RFC 提出了以下两个建议：
- 自动检测 JSON 列的频繁查询键路径，并将其提取为虚拟列，以实现与其他列类似的查询性能。
- 使用 JSONB 代替 JSON 作为半结构化数据类型的底层二进制编码格式，这将优化解析速度并有利于键路径访问。
指南级解释
无。
参考级解释
虚 拟列
JSON 的模式可以任意更改。然而，在实际使用中，JSON 数据通常由机器生成，具有相当刚性和可预测的结构。 利用这一特性，我们可以检测并提取频繁查询的 JSON 键路径作为虚拟列，以加快查询处理。
收集频繁访问的 JSON 键路径
提取和存储虚拟列需要额外的解析过程和存储资源，因此不适合为所有键路径生成虚拟列。 我们只应为频繁查询的 JSON 键路径生成虚拟列。
为了知道哪些键路径是频繁查询的， 我们使用 FPGrowth 算法 来统计 JSON 数据键路径的访问频率。 “FP”代表频繁模式，通常用于计算项目频率并识别频繁项目。 每次用户查询 JSON 数据的一个键路径时，它都会被 FPGrowth 算法记录下来，最终生成树状统计信息。 我们可以使用这些统计信息来确定哪些键路径需要生成虚拟列。
提取虚拟列
提取虚拟列的操作是异步执行的，因此不会影响数据插入的性能。 由于 Databend 会定期压缩表块，我们可以在列数据类型为 JSON 时将其作为附加操作进行虚拟列提取。 这样，用于压缩的数据可以重复使用，从而减少不必要的读取放大。
提取虚拟列的过程如下：
- 收集由 FPGrowth 算法生成的访问次数超过阈值的键路径。
- 解析 JSON 数据，推断所有键路径的 JSON 模式，包括值的数据类型和行数。
- 检查所有键路径，如果值的数据类型相同，并且每行都有数据，则从该键路径提取数据以生成虚拟列，并将其存储在单独的 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 二进制 或 JSON 更好，这是自 v9.4 以来 PostgreSQL 支持的优化二进制格式数据类型。
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 添加额外索引
