jq보다 빠른 jsongrep

Context

jq, jmespath, jsonpath-rust, jql 등 기존 JSON 쿼리 도구들은 쿼리를 인터프리트하면서 재귀적으로 탐색하여 대용량 JSON 처리 시 성능 병목이 발생한다. 특히 TB 단위의 ndjson 파일이나 대규모 로그 처리 환경에서 높은 지연시간이 누적된다.

Technical Solution

• JSON을 트리 구조로 모델링하고 쿼리를 정규 언어로 표현해 DFA(Deterministic Finite Automaton)로 사전 컴파일: 루트에서 노드까지의 경로 집합을 O(n) 시간에 단일 패스로 탐색 가능
• serde_json_borrow를 이용한 zero-copy 파싱 도입: 문자열 복사 없이 원본 JSON 버퍼를 직접 참조해 메모리 할당 최소화
• Glushkov 알고리듬으로 NFA 생성 후 Subset Construction으로 DFA 변환: ε-전이 없는 결정적 자동자 구성으로 백트래킹 제거
• DFS 기반 탐색 시 불필요한 서브트리 가지치기(prune): 전이가 없는 엣지는 즉시 탐색 중단해 계산량 감소
• 점 표기, 와일드카드(*), Alternation(|), Optional(?), Kleene Star 등 단순한 검색 중심 쿼리 언어 제공: 변환이나 계산 기능 제외로 엔진 복잡도 최소화

Impact

• 문서 파싱 속도에서 serde_json_borrow가 기존 JSON 파서보다 빠름
• 검색 시간(query_search)에서 jsongrep이 모든 비교 도구(jsonpath-rust, jmespath, jaq, jql) 중 가장 빠름
• 엔드투엔드 성능: 190MB 데이터셋에서 jq, jmespath, jsonpath-rust, jql보다 압도적으로 빠름
• 쿼리 컴파일 시간에서 jsongrep은 DFA 생성으로 jmespath보다 오버헤드 발생하지만 검색 단계에서 상쇄

Key Takeaway

검색 중심의 단순한 기능 집합으로 범위를 제한하고 오토마타 이론(NFA→DFA 변환)을 적용하면 인터프리터 기반 도구보다 근본적으로 빠른 성능을 달성할 수 있다. Zero-copy 파싱과 선택적 백트래킹 제거는 대용량 데이터 처리 환경에서 누적되는 지연시간을 크게 줄 수 있다.