LLM과 PBT 기반 Rust 리라이트로 SQL 파서 성능 70~454배 향상

Context

ANTLR 기반 C++ 파서의 추상화 계층과 그래프 탐색 방식에 따른 런타임 오버헤드 발생. 특히 동적 Lookahead 처리 과정에서 발생하는 인디렉션으로 인해 p95 응답 시간 개선의 병목 지점 형성.

Technical Solution

• ANTLR의 선언적 문법을 Oracle로 정의하고 이를 기반으로 한 Rust 기반 Recursive-descent 파서 구현
• Pratt expression loop 도입을 통한 효율적인 연산자 우선순위 처리 및 파싱 속도 최적화
• LL(2) cursor와 제한적 Non-consuming look-ahead probe를 결합한 예측 파싱 구조 설계
• 특정 결정 지점에만 국한된 Ordered-choice speculative backtracking 적용으로 유연성과 성능 동시 확보
• Hypothesis 라이브러리를 활용한 Property-based Testing(PBT) 환경 구축으로 Oracle과의 AST 일치성 검증
• .g4 문법 파일을 해석하는 코드 생성기를 제작하여 PBT를 위한 고밀도 SQL 테스트 케이스 자동 생성

Impact

• 로컬 벤치마크 기준 기존 대비 약 70배 속도 향상
• 프로덕션 쿼리 로그 기준 평균 454배의 파싱 성능 개선 달성
• Shadow mode 테스트를 통해 수백만 건의 쿼리에서 Zero divergence 검증 완료

Key Takeaway

Parser Generator를 단순 도구가 아닌 '정답지(Oracle)'로 활용하고, LLM과 PBT를 결합해 고성능 맞춤형 파서를 빠르게 구현하는 새로운 엔지니어링 패러다임 제시.