jq से तेज़ jsongrep

• JSON दस्तावेज़ों को path-based तरीके से खोजने वाला Rust CLI टूल, जिसकी search speed मौजूदा jq, jmespath, jsonpath-rust, jql से तेज़ है
• query को regular language में व्यक्त करके DFA में compile किया जाता है, और JSON tree को single pass में traverse करने वाली संरचना के कारण O(n) समय में प्रोसेस करता है
• zero-copy parsing को support करने वाले serde_json_borrow का उपयोग कर memory allocation को न्यूनतम रखता है, और इसे ripgrep की performance philosophy से प्रेरित होकर डिज़ाइन किया गया है
• benchmark नतीजों के अनुसार, बड़े JSON पर भी end-to-end performance सबसे बेहतर है, और यह search-focused सरल query language प्रदान करता है
• MIT license के तहत उपलब्ध है, और DFA-आधारित query engine को Rust library के रूप में दोबारा उपयोग किया जा सकता है

---

jsongrep का अवलोकन

• jsongrep JSON दस्तावेज़ों में path-based तरीके से values खोजने वाला Rust-आधारित CLI टूल है, जिसका लक्ष्य jq, jmespath, jsonpath-rust, jql से तेज़ प्रदर्शन देना है
• यह JSON दस्तावेज़ को एक tree की तरह देखता है, और path को regular language के रूप में व्यक्त करके DFA (Deterministic Finite Automaton) में compile करने के बाद single pass में traversal करता है
• query language सरल है और search-focused तरीके से डिज़ाइन की गई है, इसलिए इसमें transformation या calculation features नहीं हैं
• serde_json_borrow का उपयोग कर zero-copy parsing से memory allocation को न्यूनतम किया जाता है
• इसका विकास ripgrep की design philosophy और performance approach को संदर्भ में रखकर किया गया है

jsongrep के उपयोग के उदाहरण

• jg कमांड query और JSON input लेती है, और उन सभी values को output करती है जिनका path query से match करता है
• dot notation (dot path) से nested fields तक पहुँचा जा सकता है
  • jg 'roommates[0].name' → "Alice"
• wildcard (*, [*]) से सभी keys या indexes match किए जा सकते हैं
• Alternation (|) से कई paths में से एक चुना जा सकता है
• recursive search ((* | [*])*) से किसी भी depth पर fields खोजे जा सकते हैं
• Optional (?) से 0 या 1 बार match को support किया जाता है
• -F option से किसी खास field name को तेज़ी से खोजा जा सकता है
• pipe (| less, | sort) का उपयोग करने पर path output अपने-आप छिप जाता है, और --with-path से इसे मजबूरी में दिखाया जा सकता है

jsongrep की मुख्य अवधारणाएँ

• JSON एक tree structure है, और object keys तथा array indexes edge की भूमिका निभाते हैं
• query root से किसी खास node तक पहुँचने वाले paths के set को परिभाषित करती है
• query language को regular language के रूप में डिज़ाइन किया गया है, इसलिए इसे DFA में बदला जा सकता है
• DFA input को सिर्फ एक बार पढ़ता है और backtracking के बिना O(n) समय में traversal करता है
• मौजूदा tools (jq, jmespath आदि) query को interpret करते हुए recursive traversal करते हैं, जबकि jsongrep precompiled DFA से single-pass traversal करता है

DFA-आधारित query engine की संरचना

• pipeline 5 चरणों से बनी है
  1. serde_json_borrow से JSON को tree में parse करना
  2. query को AST में parse करना
  3. Glushkov algorithm से NFA बनाना
  4. Subset Construction से DFA में बदलना
  5. DFA transitions का पालन करते हुए JSON tree को single DFS में traverse करना

• query parsing

  • PEG grammar (pest library का उपयोग) से query को Query AST में बदला जाता है
  • मुख्य syntax elements: Field, Index, Range, FieldWildcard, ArrayWildcard, Optional, KleeneStar, Disjunction, Sequence
  • उदाहरण: roommates[*].name → Sequence(Field("roommates"), ArrayWildcard, Field("name"))

• JSON tree model

  • object keys और array indexes edges हैं, values nodes हैं
  • उदाहरण: roommates[*].name roommates → [0] → name path को traverse करता है

• NFA निर्माण (Glushkov algorithm)

  • ε-transitions के बिना NFA बनाया जाता है
  • चरण
    1. query symbols को position numbers देना
    2. First/Last/Follows sets की गणना करना
    3. हर position के बीच transitions बनाना
  • उदाहरण query roommates[*].name का NFA 4 states वाली सरल linear structure रखता है

• DFA conversion (Subset Construction)

  • NFA के state sets के आधार पर deterministic DFA बनाया जाता है
  • हर state एक NFA state set से मेल खाती है
  • Other symbol जोड़कर अनावश्यक keys को कुशलता से skip किया जाता है
  • सरल query को NFA जैसी ही structure वाले DFA में बदला जाता है

• DFS-आधारित traversal

  • root से शुरू करके हर edge के साथ DFA transition किया जाता है
  • transition न होने पर उस subtree को prune कर दिया जाता है
  • DFA state accepting होने पर path और value को रिकॉर्ड किया जाता है
  • हर node अधिकतम एक बार visit होता है, इसलिए पूरा traversal O(n) है
  • serde_json_borrow के कारण string copy किए बिना मूल buffer को reference किया जाता है

benchmark methodology

• Criterion.rs के साथ statistics-based benchmark किया गया

• datasets

  • simple.json (106B), kubernetes-definitions.json (~992KB), kestra-0.19.0.json (~7.6MB), citylots.json (~190MB)

• comparison tools

  • jsongrep, jsonpath-rust, jmespath, jaq, jql

• benchmark groups

  1. document_parse: JSON parsing speed
  2. query_compile: query compile time
  3. query_search: सिर्फ search
  4. end_to_end: पूरा pipeline

• fairness considerations

  • zero-copy parsing के फ़ायदे को अलग से मापा गया
  • DFA compile cost को अलग से मापा गया
  • जिन tools में feature नहीं था, उन्हें उस test से बाहर रखा गया
  • data duplication cost को अलग से संभाला गया

benchmark परिणाम

• document parsing time: serde_json_borrow सबसे तेज़ है
• query compile time: jsongrep में DFA generation के कारण सबसे अधिक cost आती है, जबकि jmespath काफी तेज़ है
• search time: jsongrep सभी tools में सबसे तेज़ है
• end-to-end performance: 190MB dataset पर भी jq, jmespath, jsonpath-rust, jql की तुलना में काफ़ी ज़्यादा तेज़
• पूरे परिणाम live benchmark site पर देखे जा सकते हैं

license और उपयोग

• MIT license के तहत उपलब्ध open source software
• GitHub, Crates.io, Docs.rs पर उपलब्ध
• DFA-आधारित query engine को library form में दोबारा उपयोग किया जा सकता है, और इसे सीधे Rust projects में integrate किया जा सकता है

संदर्भ साहित्य

• Glushkov, V. M. (1961), The Abstract Theory of Automata
• Rabin, M. O., & Scott, D. (1959), Finite Automata and Their Decision Problems