ClickHouse, 칼럼 기반 데이터베이스에서 텍스트 검색 성능 혁신!
ClickHouse 25.9 버전부터 새로운 전문 텍스트 검색(Full-text Search) 기능이 베타 버전으로 출시됨
기존 Bloom filter 기반 방식에서 Inverted Index 기반 아키텍처(Inverted Index Architecture)로 전면 개편
FST(Finite State Transducer)와 Roaring Bitmaps를 활용하여 인덱싱 성능 및 공간 효율성 향상
Row-level filtering을 통해 잦은 검색어에 대한 쿼리 성능을 획기적으로 개선
Inverted Index 기반 아키텍처의 핵심
ClickHouse의 새로운 텍스트 검색은 Inverted Index(역색인)를 기반으로 설계되었다. 이는 기존의 Bloom filter 기반 방식의 한계를 극복하기 위함이다. Inverted Index는 토큰(Token) → 문서(Document) 매핑을 통해 대용량 데이터셋에서도 빠른 검색을 가능하게 한다. 특히, FST(Finite State Transducer)를 활용하여 토큰 사전(Dictionary)을 압축하고, Roaring Bitmaps를 사용하여 Posting List를 효율적으로 관리한다.
FST(Finite State Transducer)를 활용한 토큰 사전 관리
ClickHouse는 FST(Finite State Transducer)를 사용하여 토큰 사전을 압축하고 검색 성능을 향상시켰다. FST는 접두사 공유(Prefix Sharing)를 통해 공간 효율성을 높이고, 각 토큰을 그래프의 경로로 표현한다. 토큰의 존재 여부를 빠르게 확인하고, Posting List의 위치를 계산하는 데 사용된다. 이러한 구조는 대용량 토큰 사전을 효율적으로 관리하고 검색 속도를 높이는 데 기여한다.
Roaring Bitmaps를 활용한 Posting List 압축
ClickHouse는 Roaring Bitmaps를 사용하여 Posting List를 압축하고, 빠른 Set 연산을 지원한다. Roaring Bitmaps는 데이터를 Array, Bitmap, Run-length encoding 세 가지 컨테이너로 분할하여 저장한다. 이를 통해 데이터의 희소성(Sparsity)에 따라 최적의 압축 방식을 선택하고, AND, OR, NOT 연산을 고속으로 수행할 수 있다. 특히, SIMD(Single Instruction, Multiple Data)를 활용하여 연산 속도를 극대화한다.
Row-level filtering을 통한 쿼리 성능 향상
새로운 텍스트 검색 기능은 Row-level filtering을 통해 쿼리 성능을 획기적으로 개선했다. 기존에는 텍스트 컬럼을 읽어 각 행을 필터링했지만, 이제는 인덱스만을 사용하여 매칭되는 Row ID를 추출한다. 이로 인해 잦은 검색어에 대한 쿼리 속도가 90% 이상 향상되었다고 보고된다. 이러한 최적화는 텍스트 컬럼을 읽는 오버헤드를 줄여 전반적인 검색 성능을 향상시킨다.
새로운 토크나이저(Tokenizer) 및 검색 함수
ClickHouse는 새로운 토크나이저(Tokenizer)와 검색 함수를 도입하여 유연성을 높였다. 특히, split 토크나이저는 CSV 스타일 데이터와 같이 특정 구분자를 기준으로 토큰을 분리하는 데 적합하다. 또한, searchAny 및 searchAll 함수를 통해 기존 hasToken 함수의 제한 사항을 개선했다. 이러한 변화는 사용자 정의 토큰화 및 다중 토큰 검색을 더욱 직관적으로 지원한다.
