SQLite로 의미 기반 검색 구현, 벡터 데이터베이스 없이!
SQLite FTS5 확장 기능을 활용하여 텍스트 검색(Text Search)과 의미 기반 검색(Semantic Search)을 결합하는 하이브리드 검색 구현
이진 임베딩(Binary Embeddings)과 해밍 거리(Hamming Distance)를 사용하여 벡터 데이터베이스 없이 유사성 검색 수행
SQLite 확장 기능을 통해 해밍 거리 계산 함수를 구현하고, BM25 랭킹(BM25 Ranking)과 상호 순위 융합(RRF)을 결합하여 하이브리드 검색 구현
100만 행 데이터셋에서 35ms의 성능을 보이며, O(n) 검색 방식(O(n) Search)의 효율성을 입증
이진 임베딩(Binary Embeddings)과 해밍 거리(Hamming Distance)의 활용
저자는 텍스트를 의미를 포착하는 수치 벡터(임베딩)로 변환하여 의미 기반 검색을 구현했다. 특히, 1024차원 임베딩을 128바이트의 이진 임베딩으로 양자화하여 저장 공간을 획기적으로 줄였다. 해밍 거리(Hamming Distance)를 유사성 측정 지표로 활용하여, 빠른 비트 연산(Bit Operations)을 통해 계산 속도를 높였다. 이는 정확도 감소라는 트레이드오프(Trade-off)를 감수하는 대신, 저장 공간과 속도 측면에서 이점을 얻기 위한 전략이다.
SQLite 확장 기능을 이용한 해밍 거리 계산 함수 구현
저자는 SQLite 확장 기능을 사용하여 해밍 거리를 계산하는 `hamming_distance` 함수를 구현했다. 이 함수는 두 개의 BLOB(Binary Large Object)를 입력받아 해밍 거리를 정수로 반환한다. __builtin_popcountll() 함수를 활용하여 효율적인 비트 카운팅을 수행하고, x86_64 및 ARMv8-A+ 아키텍처에서 최적의 성능을 낼 수 있도록 설계했다. SQLite 확장(SQLite Extension)을 통해 데이터베이스 내에서 직접 해밍 거리를 계산함으로써, 외부 도구 없이 하이브리드 검색을 가능하게 했다.
성능 분석 및 O(n) 검색 방식의 효율성
저자는 100만 행의 128바이트 이진 벡터 데이터셋에서 해밍 거리 계산 및 정렬을 포함하여 35ms의 검색 시간을 기록했다. 정렬 오버헤드를 제거한 경우, 28ms로 성능이 향상되었다. O(n) 검색 방식(O(n) Search)은 인덱싱(Indexing)을 사용하지 않지만, 데이터셋 크기가 작거나 쿼리 빈도가 낮을 경우 충분히 실용적임을 입증했다. HNSW 또는 IVF 인덱싱(Indexing)과 같은 복잡한 기법 대신, 단순함을 선택하여 구현 복잡도와 메모리 사용량을 줄였다.
하이브리드 검색 구현: BM25와 RRF의 결합
저자는 FTS5의 BM25 랭킹과 해밍 거리 기반의 의미 검색 결과를 결합하기 위해 상호 순위 융합(Reciprocal Rank Fusion, RRF) 방식을 사용했다. 각 검색 방법의 상위 k개 결과를 RRF를 통해 융합하여 최종 순위를 결정한다. RRF(Reciprocal Rank Fusion)는 서로 다른 검색 시스템의 점수를 정규화하지 않고도 결과를 병합할 수 있는 장점이 있다. 이 방식을 통해 키워드 기반 검색과 의미 기반 검색을 모두 만족하는 하이브리드 검색을 구현했다.
하이브리드 검색의 활용 사례 및 한계
저자는 'Apple founder', 'Python snake habitat', 'Python programming tutorial'과 같은 쿼리 예시를 통해 하이브리드 검색의 장점을 설명했다. 특히, 의미 기반 검색은 'Apple'과 같은 모호한 단어를 맥락에 맞게 해석하고, BM25는 키워드 기반 필터링을 수행하여 검색 정확도를 높인다. 이 방식은 데이터셋 크기가 작고, 외부 벡터 데이터베이스 의존성을 피하고 싶은 경우에 적합하다. 하지만, O(n) 검색 방식(O(n) Search)의 한계로 인해 대규모 데이터셋에는 적합하지 않을 수 있다.
