An introduction to the jsongrep tool, a technical explanation of its DFA-based search engine, and performance results against popular JSON query tools.

Hacker News is a community-driven platform for sharing and discussing technology news, startups, and programming-related topics. Through user submissions and comments, Hacker News offers insights into emerging technology trends, industry developments, and entrepreneurial ventures. Readers can participate in discussions, share their insights, and stay informed about the latest advancements in technology and innovation.

Hacker News

jsongrep is a new Rust-based CLI tool for querying JSON documents using a regular language query syntax compiled into a deterministic finite automaton (DFA). Unlike jq, jmespath, or jsonpath-rust which interpret path expressions at runtime, jsongrep compiles queries into a DFA upfront using Glushkov's construction and subset construction algorithms, then walks the JSON tree exactly once with O(1) state transitions and aggressive subtree pruning. The post explains the five-stage pipeline (JSON parse, query parse, NFA construction, DFA determinization, DFS traversal), walks through a concrete example, and presents benchmarks showing jsongrep significantly outperforms competing tools on end-to-end search over large (~190 MB) datasets. Trade-offs include higher query compile time and a less expressive query language compared to jq (no filters, arithmetic, or transformations).

jsongrep is faster than {jq, jmespath, jsonpath-rust, jql}