一句话：提出 JPStream 编译系统，将 JSONPath 查询与 JSON 语法联合编译为有界内存的并行可执行程序。
JSON 及其衍生格式广泛使用，但现有软件难以可扩展处理：构建解析树耗内存，且数据流处理存在内在依赖，阻碍数据级并行。本文提出全自动编译系统 JPStream，将标准 JSONPath 查询编译为内存有界的并行可执行程序。它采用流式设计，将查询与解析合并为一趟，并用联合编译技术把查询和 JSON 语法编译成单一自动机。利用自动机的可枚举性打破依赖，分析转移规则剪除不可行状态；运行时从输入学习结构约束以增强剪枝。在真实 JSON 数据集和标准 JSONPath 查询上，JPStream 最多降低 95% 内存，并在多核与众核上取得近线性加速。
JSON (JavaScript Object Notation) and its derivatives are essential in the modern computing infrastructure. However, existing software often fails to process such types of data in a scalable way, mainly for two reasons: (i) the processing often requires to build a memory-consuming parse tree; (ii) there exist inherent dependences in processing the data stream, preventing any data-level parallelization. Facing the challenges, developers often have to construct ad-hoc pre-parsers to split the data stream in order to reduce the memory consumption and increase the data parallelism. However, this strategy requires more programming efforts. Moreover, the pre-parsing itself is non-trivial to parallelize, thus introducing a new serial bottleneck. To solve the dilemma, this work introduces a scalable yet fully automatic solution - a compilation system, namely JPStream, that compiles standard JSONPath queries into parallel executables with bounded memory footprints. First, JPStream adopts a stream processing design that combines the querying and parsing into one pass, without generating any in-memory parse tree. To achieve this, JPStream uses a novel joint compilation technique that compiles the queries and the JSON syntax together into a single automaton. Furthermore, JPStream leverages the "enumerability'' of automaton to break the dependences and reason about the transition rules to prune infeasible states. It also features a runtime that learns structural constraints from the input to enhance the pruning. Evaluation on real-world JSON datasets with standard JSONPath queries shows that JPStream can reduce the memory consumption significantly, by up to 95%, meanwhile achieving near-linear speedup on multicore and manycore processors.
@inproceedings{paperbot4860,
title = {Scalable Processing of Contemporary Semi-Structured Data on Commodity Parallel Processors - A Compilation-based Approach},
author = {Lin Jiang and Xiaofan Sun and Umar Farooq and Zhijia Zhao},
booktitle = {ASPLOS},
year = {2019},
doi = {10.1145/3297858.3304008}
}