讀後筆記：為什麼 jsongrep 能快過 jq？一探 DFA 引擎背後的祕密

本篇文章更新時間：2026/03/28
如有資訊過時或語誤之處，歡迎使用 Contact 功能通知或向一介資男的 LINE 社群反應。
如果本站內容對你有幫助，歡迎贊助支持 。

jsongrep：用 DFA 搜尋 JSON 的驚人速度

一篇帶你重新理解「JSON 查詢」本質的技術深度文筆記

編輯前言：如果你經常用 jq 或 JSONPath 查資料，這篇文章會刷新你對 JSON 查詢工具的認知。作者分享了他打造的 jsongrep 為何能在搜尋速度上大幅超越 jq、jmespath、jsonpath-rust 等工具，並深入解釋背後的自動機模型（NFA / DFA）。

文章來源：jsongrep is faster than {jq, jmespath, jsonpath-rust, jql}

---

核心觀點 (Key Takeaways)

• jsongrep 把「JSON 路徑查詢」視為一種正規語言，並把查詢字串編譯成 DFA，因此搜尋時能以單一路徑、零回溯方式走完整棵 JSON 樹。
• 與一般工具不同，它不是「解讀查詢」而是「預先將查詢編譯」，因此搜尋階段幾乎是 O(n) 的線性成本，速度非常快。
• 零拷貝的 serdejsonborrow 解析方式讓 jsongrep 在大型 JSON（例如 190MB citylots.json）中展現極高效率。

---

深入解析

作者先展示了 jsongrep 的查詢語法，其概念類似正規表達式，但匹配的不是字元，而是 JSON 樹狀結構中的「邊」：

Querying a JSON document is really about describing paths through this tree.

這個洞見讓作者可以將查詢語法設計成「正規語言」，因此具備可編譯成 DFA 的特性。

1. 查詢語法是正規語言，能編譯成 NFA → DFA

jsongrep 將查詢字串 parse 成 AST，語法包含：

• Field：name
• ArrayWildcard：[*]
• Optional：?
• Kleene star：*
• Alternation：a | b

例如：roommates[*].name 會被解析成一連串序列符號。

接著透過 Glushkov’s algorithm 建立「無 epsilon 的 NFA」，這比常見的 Thompson NFA 更有效率。之後用 subset construction（powerset construction）產生最終使用的 DFA。

這段過程的重點在於：

jsongrep 在搜尋前就把所有可能的路徑明確編譯完，不需要在搜尋時做任何解讀式的判斷或回溯。

而 jq、jmespath 等工具通常會在每個節點重新解讀查詢表達式，因此成本大得多。

2. DFA 讓 jsongrep 能在單趟 DFS 中完成搜尋

搜尋時 jsongrep 只要：

• 對每個節點做一次 DFA 狀態轉移
• 若該狀態為接受狀態（accepting），就記錄路徑
• 若無轉移路徑，整個 subtree 可直接跳過

這點非常關鍵。因為跳過 subtree 的行為讓 jsongrep 在處理大 JSON 時能省下大量時間。作者用示例清楚展示：在 sample.json 裡，查詢 roommates[*].name 時，根節點的 name 與 favorite_drinks 整段 subtree 都被瞬間剪掉。

3. serdejsonborrow：零拷貝 JSON 解析

一般 JSON 庫會在解析過程中重新分配字串，但 serdejsonborrow 則能借用原始 buffer。不用大量 allocation，也為 jsongrep 帶來解碼速度優勢。

4. 基準測試：jsongrep 在大型檔案上明顯勝出

文章以 190MB 的 citylots.json 做基準測試，將工具拆分成四階段比較：

• document_parse：JSON 解析成本
• query_compile：查詢編譯成本
• query_search：搜尋成本（事先編譯 + 解析）
• endtoend：完整流程

結果顯示：

在 end-to-end 搜尋上，jsongrep 明顯快過 jq、jsonpath-rust、jmespath 等所有工具。

儘管 jsongrep 的 query_compile 成本較高，但搜尋速度的優勢完全補足了這點。

---

筆者心得與啟發

讀完文章，我最大的收穫是：JSON 查詢其實可以完全拋開「解讀式」的做法，而回到計算理論的本質，用 DFA 來解決。

這個觀點其實和 ripgrep 的理念一樣：把 pattern 變成 automaton，搜尋的時候只用最簡單、最線性的方式執行。

這也讓我反思，許多我們習慣認為「需要邏輯判斷」的查詢語言，其實可能都能重構成一種正規語言模型，先付一次編譯成本，然後用極快的方式跑全文（或全 JSON 樹）。

若你有以下需求，我會非常推薦試試 jsongrep：

• 大型 JSON 的搜尋（百 MB 以上）
• 多次重複使用相同查詢
• 嵌入 Rust 專案中需要可預期效能的 JSON 查詢邏輯

總的來說，這篇文章不只是介紹一個工具，而是重新框定了我們看待 JSON 查詢這件事的方式。

---