빠른 Regex 검색을 위한 Cursor Trigram Indexes

# Cursor의 로컬 트리그램 인덱스가 대형 리포지토리에서 정규식 검색을 가속화합니다

Cursor가 IDE 바로에서 정규식 검색을 위한 로컬 인덱스를 구현했습니다. 이는 대형 모노레포에서 발생하는 느린 스캔 문제를 해결합니다. 기존 ripgrep은 호출당 15초 이상 걸리고, AI 에이전트는 그런 쿼리를 수십 개씩 생성하죠.

이 기술은 1993년의 트리그램 역인덱스를 기반으로 합니다. 텍스트를 모든 3문자 시퀀스(트리그램)로 분해해 딕셔너리의 키로 사용합니다. 각 키는 해당 시퀀스를 포함하는 파일 목록에 대응하죠. 정규식 쿼리를 트리그램 집합으로 분해한 뒤 posting list를 교집합해 후보를 선별합니다. 그러면 수천 개 파일 대신 수십 개 파일에만 grep을 적용합니다.

정확한 범위 지정のための 희소 n-gram

기본 인덱스 위에 희소 n-gram을 추가합니다. 각 n-gram의 길이는 crc32 기반 문자 쌍 가중치나 테라바이트 규모의 오픈소스 코드에서 구축된 빈도표를 사용해 결정적으로 계산됩니다.

인덱싱 시에는 모든 가능한 n-gram을 생성하고, 검색 시에는 최소 커버링 세트를 사용합니다. 이는 조회 횟수를 줄이고 필터링 정확도를 높여줍니다.

// Example dekompozitsii regex in n-grams
regex: \w+@\w+\.com
n-grams: ['@', 'w+', '.c', 'com', ...]  // sparse pokryodkrycie
candidates = intersect(postings(ngrams))

로컬 저장소와 커밋 바인딩

인덱스는 사용자의 로컬 머신에 mmap 파일 두 개로 저장됩니다. 이유는 다음과 같습니다:

• AI 에이전트는 최종 검증을 위해 어차피 로컬 파일을 읽습니다.
• 네트워크 왕복은 속도 향상 효과를 상쇄합니다.

인덱스는 특정 git 커밋에 연결되어 있습니다. 커밋되지 않은 변경사항은 재빌드 없이 오버레이됩니다.

• mmap 장점: 로딩 시 오버헤드 제로, posting list 빠른 탐색.
• 업데이트: git pull/push 또는 수동 재빌드 시 트리거.
• 크기: 코드베이스에 비례; 10M LoC — ~500MB.

성능 비교

| 접근 방식 | 쿼리당 시간 (10k 파일) | grep 후보 |

|----------|----------------------------|-----------|

| ripgrep | 15–20초 | 10k |

| Cursor index | 50–200ms | 10–50 |

AI 에이전트의 100개 이상 쿼리가 발생하는 실제 시나리오에서 전체 속도 향상은 100배에 달합니다.

트리그램은 정확한 부분 문자열에 대해 완전성을 보장(재현율=1)하고, 희소 n-gram은 거짓 양성을 내지 않으면서 정밀도를 높입니다.

주요 포인트

• 트리그램 인덱스가 후보 파일을 수천 개에서 수십 개로 줄입니다.
• 희소 n-gram이 최소 커버링 세트로 조회를 최소화합니다.
• 로컬 mmap 저장소가 네트워크 지연을 제거합니다.
• 커밋되지 않은 변경을 오버레이하는 git 커밋 바인딩.
• 대형 모노레포에서 AI 에이전트의 정규식 검색 100배 가속.

— Editorial Team