jsongrep：比 jq 更快的 JSON 查询工具

Micah Kepe 在博客上写了一篇题为"jsongrep is faster than {jq, jmespath, jsonpath-rust, jql}"的文章，在 Hacker News 上获得 376 分和 237 条评论。

他说："这篇文章既是介绍我一直在工作的一个叫做 jsongrep 的工具，也是对其使用的内部搜索引擎的技术解释。我还讨论了用于比较 jsongrep 与其他 JSON 路径类查询工具和实现的性能的基准测试策略。"

"这篇文章很大程度上受到 Andrew Gallant 的 amazing ripgrep 工具及其相关博客的启发。"

什么是 jsongrep

jsongrep 是一个 JSON 查询工具，用 Rust 编写，跨平台。

你可以从 crates.io 安装：

cargo install jsongrep

或者通过 Homebrew：

brew install jsongrep

jsongrep（jg 二进制文件）接受一个查询和一个 JSON 输入，并打印每个路径通过文档匹配查询的值。

查询语言

让我们用这个示例文档逐步构建查询语言：

{
  "name": "Micah",
  "favorite_drinks": ["coffee", "Dr. Pepper", "Monster Energy"],
  "roommates": [
    {
      "name": "Alice",
      "favorite_food": "pizza"
    }
  ]
}

点路径通过名称选择嵌套字段。点（.）在字段名称之间表示连接：

$ cat sample.json | jg 'roommates[0].name'
roommates.[0].name:
"Alice"

通配符匹配任何单个键（）或任何数组索引（[]）：

$ cat sample.json | jg 'favorite_drinks[*]'
favorite_drinks.[0]:
"coffee"
favorite_drinks.[1]:
"Dr. Pepper"
favorite_drinks.[2]:
"Monster Energy"

**交替（|）**匹配任一支路，像正则表达式交替：

$ cat sample.json | jg 'name | roommates'
name:
"Micah"
roommates:
[
  {
    "name": "Alice",
    "favorite_food": "pizza"
  }
]

递归下降在 Kleene 星中使用 * 和 [*] 任意深度地遍历树。例如，找到任意深度的每个 name 字段：

$ cat sample.json | jg '(* | [*])*.name'
name:
"Micah"
roommates.[0].name:
"Alice"

模式 (* | [*])* 意思是"跟随任何键或任何索引，零次或多次"，例如，通过每个可能的路径下降。尾随的 .name 然后过滤只那些以叫做 name 的字段结束的路径。

等价地，jg 暴露 -F（"固定字符串"）标志作为这些递归下降查询的简写：

$ cat sample.json | jg -F name
name:
"Micah"
roommates.[0].name:
"Alice"

**可选（?）**匹配零次或一次：

$ cat sample.json | jg 'roommates[0].favorite_food?'
roommates.[0]:
{
  "name": "Alice",
  "favorite_food": "pizza"
}
roommates.[0].favorite_food:
"pizza"

注意内部字符串"pizza"与 ? 匹配，除了父零次出现情况。

为什么快

JSON 文档是树：对象和数组分支，标量是叶子，键和索引标记边。查询 JSON 文档真的是关于描述通过这个树的路径。

jsongrep 字面上采用这个观察：它的查询语言是键和索引字母表上的正则语言。想正则表达式，但不是匹配字符串中的字符，你匹配树中的边。

为什么"正则"重要？因为正则语言有一个众所周知的强大属性：它们可以被编译成确定性有限自动机（DFA）。DFA 在单次传递中处理输入，每个输入符号做 O(1) 工作——没有回溯，没有递归栈，没有指数爆炸在病态查询上。查询在编译时支付一次，然后搜索本质上免费。

这是与 jq、jmespath 或 jsonpath-rust 等工具的关键区别。那些工具解释路径表达式：在 JSON 树的每个节点，它们评估查询，检查谓词，并递归下降到匹配分支。如果查询涉及递归下降（.. 或 $..），这些工具可能重访子树或维护工作列表。

jsongrep 做一些根本不同的事情——它在查看 JSON 之前把查询编译成 DFA，然后正好一次遍历文档树，在每个边上做单个 O(1) 状态转换。没有解释，没有回溯，一次传递。

搜索引擎内部

搜索引擎的核心是一个五阶段管道：

通过 serde_json_borrow（零拷贝）解析 JSON 文档成树
解析用户的查询成 Query AST
通过 Glushkov 构造算法从查询构造 NFA
通过子集构造把 NFA 确定化成 DFA
遍历 JSON 树，在每个边上做 DFA 转换并收集匹配

基准测试

端到端搜索性能比较在 xlarge（~190 MB）数据集上。

jsongrep 比 jq 快得多。

反推销

再次借用 ripgrep 博客，这里是 jsongrep 的"反推销"：

jsongrep 还不像 jq 那样普遍。jq 是 JSON 查询、过滤和转换的首选工具。
查询语言故意不如 jq 表达。jsongrep 是一个搜索工具，不是一个转换工具——它找到值但不计算新值。没有过滤器，没有算术，没有字符串插值。
jsongrep 是新的，还没有在野外经过战斗测试。

实际应用

这个工具对开发者有几个实际应用：

快速 JSON 查询

如果你需要快速查询 JSON，jsongrep 是一个选择。

大数据集

如果你处理大数据集，jsongrep 的性能可能重要。

管道工具

jsongrep 可以嵌入管道。像其他 CLI 工具一样。

Rust 库

jsongrep 还暴露它的基于 DFA 的查询引擎作为库 crate，所以你可以直接在你的 Rust 项目中嵌入快速 JSON 搜索。

结语

Micah 说："这篇文章既介绍工具，也解释内部。"

jsongrep 是一个有趣的工具。它快。它用 Rust 编写。它有基于 DFA 的查询引擎。

但更重要的是，它展示了工具可以是快的。性能不是魔法。它是设计。

在这个时代，我们需要更多关于设计，少关于魔法。