jq보다 빠른 대안 jsongrep

3 hours ago 1

JSON 문서를 경로 기반으로 탐색하는 Rust CLI 도구로, 기존 jq, jmespath, jsonpath-rust, jql보다 검색 속도가 빠름
쿼리를 정규 언어로 표현해 DFA로 컴파일하고, JSON 트리를 단일 패스로 탐색하는 구조로 O(n) 시간에 처리
zero-copy 파싱을 지원하는 serde_json_borrow를 사용해 메모리 할당을 최소화하고, ripgrep의 성능 철학을 참고해 설계됨
벤치마크 결과, 대용량 JSON에서도 엔드투엔드 성능이 가장 우수하며, 검색 중심의 단순 쿼리 언어를 제공
MIT 라이선스로 공개되어 있으며, DFA 기반 쿼리 엔진을 Rust 라이브러리로 재사용 가능함

jsongrep 개요

jsongrep은 JSON 문서에서 경로 기반으로 값을 검색하는 Rust 기반 CLI 도구로, jq, jmespath, jsonpath-rust, jql보다 빠른 성능을 목표로 함
JSON 문서를 트리로 보고, 경로(path) 를 정규 언어(regular language) 로 표현해 DFA(Deterministic Finite Automaton) 로 컴파일 후 단일 패스로 탐색 수행
쿼리 언어는 단순하며, 검색 중심으로 설계되어 변환이나 계산 기능은 없음
serde_json_borrow를 이용한 zero-copy 파싱으로 메모리 할당을 최소화
ripgrep의 설계 철학과 성능 접근 방식을 참고해 개발됨

jsongrep 사용 예시

명령어 jg는 쿼리와 JSON 입력을 받아, 경로가 쿼리와 일치하는 모든 값을 출력
점 표기(dot path) 로 중첩 필드 접근
- jg 'roommates[0].name' → "Alice"
와일드카드(*, [*])로 모든 키나 인덱스 매칭
Alternation(|)으로 여러 경로 중 하나 선택
재귀 탐색((* | [*])*)으로 임의 깊이의 필드 검색
Optional(?)로 0회 또는 1회 매칭 지원
-F 옵션으로 특정 필드명을 빠르게 검색 가능
파이프(| less, | sort) 사용 시 자동으로 경로 출력 생략, --with-path로 강제 표시 가능

jsongrep의 핵심 개념

JSON은 트리 구조이며, 객체 키와 배열 인덱스가 엣지(edge) 역할을 함
쿼리는 루트에서 특정 노드까지의 경로 집합을 정의
쿼리 언어는 정규 언어로 설계되어 DFA로 변환 가능
DFA는 입력을 한 번만 읽으며, 백트래킹 없이 O(n) 시간에 탐색 수행
기존 도구(jq, jmespath 등)는 쿼리를 인터프리트하며 재귀적으로 탐색하지만, jsongrep은 사전 컴파일된 DFA로 단일 패스 탐색 수행

DFA 기반 쿼리 엔진 구조

파이프라인은 5단계로 구성
1. serde_json_borrow로 JSON을 트리로 파싱
2. 쿼리를 AST로 파싱
3. Glushkov 알고리듬으로 NFA 생성
4. Subset Construction으로 DFA로 변환
5. DFA 전이를 따라 JSON 트리를 단일 DFS로 탐색
쿼리 파싱
- PEG 문법(pest 라이브러리 사용)으로 쿼리를 Query AST로 변환
- 주요 구문 요소: Field, Index, Range, FieldWildcard, ArrayWildcard, Optional, KleeneStar, Disjunction, Sequence
- 예: roommates[*].name → Sequence(Field("roommates"), ArrayWildcard, Field("name"))
JSON 트리 모델
- 객체 키와 배열 인덱스는 엣지, 값은 노드
- 예: roommates[*].name은 roommates → [0] → name 경로를 탐색
NFA 구성 (Glushkov 알고리듬)
- ε-전이 없는 NFA 생성
- 단계
  1. 쿼리 심볼에 위치 번호 부여
  2. First/Last/Follows 집합 계산
  3. 각 위치 간 전이 구성
- 예시 쿼리 roommates[*].name의 NFA는 4개 상태로 구성된 단순 선형 구조
DFA 변환 (Subset Construction)
- NFA의 상태 집합을 기반으로 결정적 DFA 생성
- 각 상태는 하나의 NFA 상태 집합에 대응
- Other 심볼을 추가해 불필요한 키를 효율적으로 건너뜀
- 단순 쿼리는 NFA와 동일한 구조의 DFA로 변환됨
DFS 기반 탐색
- 루트에서 시작해 각 엣지를 따라 DFA 전이 수행
- 전이가 없으면 해당 서브트리 가지치기(prune)
- DFA 상태가 accepting이면 경로와 값을 기록
- 각 노드는 최대 한 번 방문하며, 전체 탐색은 O(n)
- serde_json_borrow로 문자열 복사 없이 원본 버퍼 참조

벤치마크 방법론

Criterion.rs로 통계 기반 벤치마크 수행
데이터셋
- simple.json (106B), kubernetes-definitions.json (~992KB), kestra-0.19.0.json (~7.6MB), citylots.json (~190MB)
비교 도구
- jsongrep, jsonpath-rust, jmespath, jaq, jql
벤치마크 그룹
1. document_parse: JSON 파싱 속도
2. query_compile: 쿼리 컴파일 시간
3. query_search: 탐색만 수행
4. end_to_end: 전체 파이프라인
공정성 고려
- zero-copy 파싱 이점은 별도 측정
- DFA 컴파일 비용은 분리 측정
- 기능이 없는 도구는 해당 테스트 제외
- 데이터 복제 비용은 분리 처리