SmithDB의 전체 텍스트 검색을 위한 역색인(Inverted Index) 구축 방식

SmithDB는 객체 스토리지(Object Storage)를 백엔드로 사용하는 **역색인(Inverted Index)**을 설계하여 전체 텍스트 검색을 지원한다. 데이터 수집(Ingestion) 단계에서 인덱스 생성이 실시간으로 이루어지며, 최신 데이터는 로컬 스토리지에서 직접 읽어 처리 속도를 높인다.

대규모 JSON 페이로드를 효율적으로 처리하기 위해 JSON Tape 형식을 도입했다. 이는 Apache Arrow의 arrow-json과 simdjson에서 영감을 얻은 방식으로, 별도의 필드 할당이나 숫자 변환 없이 단일 패스(Single-pass) 반복자를 통해 데이터를 (path, leaf_value) 쌍으로 평탄화한다.

인덱스 구축 성능을 극대화하기 위해 다음과 같은 최적화 기술을 적용했다.

• String Interning: 중복되는 JSON 경로와 토큰 값을 고유한 정수 ID로 매핑하여, 문자열 비교 비용을 줄이고 구축 시간을 약 2.2배 단축했다.
• Radix Sort: 정렬된 런(Run)을 FST(Finite State Transducers) 작성기에 전달하기 전, $O(n)$ 복잡도로 포스팅을 그룹화한다.
• Flush Thresholds: 특정 빈도의 토큰이 무한히 커지는 것을 방지하기 위해 Row Group(32MB), Aligned Chunk(2MB), Mid-term Position Spill(8MB)의 세 가지 임계값을 기준으로 데이터를 플러시(Flush)한다.

이러한 구조를 통해 SmithDB는 메모리 사용량을 제어하면서도 객체 스토리지 환경에서 효율적인 쿼리 성능을 보장한다.