本文是对 SIGMOD 2021 上《JSON Tiles: Fast Analytics on Semi-Structured Data》的学习总结，有错误之处欢迎交流。
原文及视频下载地址。
背景
JSON 在半结构化数据表达上有很大的优势，可以在一条数据中支持任意个 key，支持 key 的灵活变更，被广泛采用：
- 关系数据库：JSON 列类型。
- Document DB：JSON 作为一行。
- 日志系统：例如 Loki、Splunk、Elasticsearch 在日志存储协议上用到 JSON。
因此 JSON 处理是高频场景，已经有较多的研究成果：
现有系统不能完全满足上图的三角。例如，SIMD-JSON 是编码大神 lemire 的作品，做到单核 GB/s 吞吐的解析，但不解决：
- 查询时需读取整个 JSON 再解析取出需要的字段。
- 存储上压缩效率一般，不如列式存储。
JSON Tiles 希望提出一个方法：在不损失 JSON 灵活性的前提下，让关系型数据库能高效处理 JSON。
方法
整体设计
主要思路是：
- 在一组 JSON 文档集合上，自动探测出公共字段。
- 在 JSON 文档集合上统计信息，将高频出现的字段物化作为关系数据库的列。
- 收集一些统计信息，和 query optimizer 结合，支持一定程度的快速过滤能力（类似列存上做 meta skip）。
- 没有单独物化的字段（低频、稀疏）存储为一个支持快速访问的 binary 格式。
鉴于要解决的问题是传统数据库没有优化的稀疏 key、弱 schema 场景，论文分别做了安排：
- 高频 key 独立物化存储，添加统计信息到 header，但只覆盖少量 key（避免爆炸）。
- 剩下的 key 合并存储，在不牺牲存储成本的情况下尽量提高查询效率。
具体来说，是将所有的 JSON 文档集合切分为块，每个块包括一组文档即为 tiles：
- 在这个 tile 内寻找 pattern（允许在小比例的行上缺失），这部分读取效率可以做高。
- 维持较小粒度的 tile，使得在大规模数据查询上并行 scan 得更高效（排除线程、锁影响）。
Extraction
将每一行定义为 tuple，右侧每一列定义为 key_path。
tile 抽取 key_path 算法：
- 遍历每一个tuple，收集所有的 key_path。
- 在 tuple 集合上，挖掘 key_path 高频集合（根据比例设定数目上限）。
- 在多个候选 key_path 上取 union 获得最大集合。
tile 创建是在数据写入时决定，可以看出：数据写入的顺序、字段分布对于 key_path 抽取质量有很大影响。由此引出 tile 分区与 tuple 重排，在更大的候选集合上寻找共性。
将一组相邻 tile 叫做 partition，重排将在 partition 以内发生。
tile 粒度在几百到几千行左右，实验结果表明 partition size 为 8 时综合效果最好。
tuple 重排算法：
- 先对每一个独立 JSON tile 做频繁集抽取（抽取结果作为重排阶段输入），此时阈值为
threshold/partition_size。 - 同一个 partitinon 内的 tile 交换，命中 tuple 数满足
threshold*tile_size的集合可以保留下来。 - 频繁集算法选择 FPGrowth（不需要产生候选集，可在一个 FP-Tree 上迭代），过程中的 key 词典编码到 tile 上作为 database 辅助挖掘过程。从小集合开始逐步扩大，计算达到一个 budget （有一个公式定义，具体参加论文）阈值后则停止。
- 在匹配 tuple 的过程中，用 hash table 统计匹配次数，匹配用贪心算法。
- 计算 swap 位置：算法遍历所有的 tuple，如果不满足条件（满足公共 key_path 的 tuple 数目达低于比例阈值），则根据 hash table 统计信息选取 swap 后位置。
- 根据
threshold参数，在重排之后的 tile 上抽取公共 key_path 集合。
重排过程按 partition 进行，在多线程下不需要线程间信息共享，有利于并发实现。
重排之后的文档，有利于压缩率的提升（例如用 RLE 编码）。
另外要考虑到类型，不同的 JSON 文档中，相同的 key 可能出现不同类型的数据，因此只有 key_path 和 type 都相同是才会被归为一个列处理。算法会选择相同 key_path 下出现次数最大的 type 来物化。那么，在查询时如果指定 key_path 的数据是 null 则会继续查找 binary 列（未被物化的列）。
对于嵌套类型：
- json object：收集一些查询表达式统计信息来指导优化，决定是否单独物化某个子对象的 key。
- json array：是公共前缀思路，例如选取前面 x 个array 的元素持久化，剩下长度不等的元素存储到 binary 列。
从写入过程看，重排是仅次于 binary 列构建之后第二费时的步骤。
Intergration
讨论将 JSON tile 具体应用到 DBMS 中。
访问变量的表达式采用一种 PG-sytle 定义：
->：按 JSON type 访问。->>：按 text 类型访问。
例如文档{"id":0, "name":"JSON"} ，object->'id'返回 0，object->'id'::Int 返回 0，object->>'id' 返回 "0"。
一些查询计算的优化手段：
- 表达式下推：对独立物化的字段过滤，tile 不需要解压全文。在 table scan operator 里用占位符表示该列，优先访问物化的字段，如果不存在再退化访问 binary 列。
- 类型转换：将 cast 类型也下推到 scan operator，避免有些情况下无谓的转换开销（例如 float 转为text 返回之后又在其它算子转换成 float 计算）。
- tile header：对于很多列（可能是稀疏导致）的情况，由于物化字段数目的限制，将 key_path 全集用 bloom filter 编码，方便后续做过滤（例如：is null）。data/time 类型值会先尝试转为 SQL timestamp（同理，为了计算阶段减少 cast 开销），转换出错的放入 binary json 列。
- query optimizer：通过 HyperLogLog 算法，可以提供关于 cardinality、key 是否存在等信息。例如基于 cardinality 预估（列值计数）可以实现有更好的 join 策略选择。
关于数据更新，如果 JSON 文档在多次修改后出现大量稀疏 key 不能匹配原有 key_path 情况，JSON tile 需要重建才能保持效率，重建是高代价的。
Binary Format
对于没有独立物化的字段，使用 JSONB 格式存储二进制数据。
效果：
- 查找时间复杂度：key 存在的情况
O(log(N))，key 是有序排列的，做二分查找。 - 连续内存访问：数据是连续存储的，访问不需要内存地址跳转，减少了 CPU cache miss。
- 注意：JOSNB 会将一些不重要的字符去除（例如空格），其它情况下可保证 round-trip safe。
- 节省存储空间：例如数字类型（整形、浮点型），可以用更小的位数类型来存储小区间或低精度数据（位数在 header 存储）。
- 嵌套类型处理：符合条件时将嵌套 object 摊平到父 object（两阶段处理：先检查一遍错误并预估数据大小；基于第一遍的结果申请固定内存大小再扫描一次写入数据）。
从论文截取了两部分 JSONB 性能表现：
- TPC-H 查询性能比 JSON 高几倍。
- 数据序列化、反序列化性能和存储效率还行。
实验结果
写入性能：
查询性能（TPC-H ）：
总结
以日志为代表的大数据偏好用 JSON 处理或兜底：
- 不同类别日志 key 不同。
- 同类别日志 key 可能发生修改。
个人看到比较多的工作总结为两方面：
- 数据模型
- 关系型：强 schema 表上支持 JSON column 来适应，解决存储问题。
- Not Only SQL：例如 MongoDB 用 JSON 来存储单条文档，系统适配业务。
- 列存型：例如 ClickHouse，遇到半结构化数据也是逃不开 JSON text、nullable column。
- Object Store：JSON 原生存储加压缩，配合 Select 下推技术。
- 计算性能
- 高性能 parser：SIMD-JSON 等。
- 字段物化存储支持高效读取：Sinew、ClickHouse（JSONEachRow）等。
- scan 性能： PG、Hologress、CockroachDB、ADB 等使用 JSONB（牺牲一些写入性能，重新编码存储支持下推读取）。
在优化半结构化 JSON 数据的存、算上，本文提出 JSON Tiles 方法，是一种 Schema on Write 思路：
- 部分高频字段是可以写入阶段来物化的，存储高效、读取高效。
- 稀疏的长尾字段退化处理，消耗少量计算成本构建 JSONB，支持将来的中低频 scan。
在实际应用中，Schema on Write 消耗一定计算资源，且 batch 构建应对流式写入不够友好。
不同的场景下存在不同的选择：例如一些程序日志写多查少，只要求存储有效率，查询计算是低频行为。这时候，Schema on Read 是合理选择，可以用弹性的云资源把计算池子做大，大力出效果。这个方案下，JSON raw/compressed text 上实现 in-place 查询性能提升更有收益。
