HNSW 알고리즘 기반 Vector DB의 Trade-off 분석 및 워크로드별 최적 선택 기준

Context

방대한 벡터 데이터셋에서 모든 요소와 거리를 계산하는 Linear Search의 시간 복잡도 한계로 인한 타임아웃 발생. 정확도를 일부 희생하고 검색 속도를 로그 시간 복잡도로 개선하는 Approximate Nearest Neighbor(ANN) 접근 방식의 필요성 증대.

Technical Solution

• Skip List와 Small-world Graph를 결합한 HNSW(Hierarchical Navigable Small World) 구조를 통한 계층적 탐색 구현
• 최상위 계층의 Long-range link로 광범위하게 이동 후 하위 계층으로 진입하여 정밀도를 높이는 'Fly-Drive-Walk' 패턴 적용
• M(링크 수), ef_construction(빌드 시 후보군), ef_search(쿼리 시 후보군) 파라미터 조절을 통한 Recall과 Latency의 정밀한 Trade-off 제어
• 데이터 규모 1,000만 건 이하 및 기존 인프라 활용 극대화를 위해 Postgres 확장 모듈인 pgvector를 통한 Ops 비용 최소화
• 복잡한 Metadata 필터링 요구사항 해결을 위해 필터링 최적화 HNSW를 구현한 Qdrant 채택
• 키워드 검색과 시맨틱 검색의 결합이 필요한 경우를 위한 Weaviate의 Hybrid Search 아키텍처 활용