[딥러닝, 검색엔진] HNSW, IVFFlat 바닥부터 탐색하기 (Vector Search)

RAG를 위해서 벡터 스토어를 사용하신건 알겠어요, 그런데.. 인덱스를 위한 옵션을 어떤 것을 사용하셨나요?

 

 

필자가 면접에서 굉장히 당황스러워했던 질문 중에 하나였습니다. 

 

인덱스...? 데이터베이스에서 쿼리 반환을 위해 사용하는 옵티마이저 중 하나인 인덱스를 말하는 것 같은데.. 여러 프로젝트를 진행하면서 벡터 검색을 하는데에 있어서는 옵션이 있는지도 몰랐었습니다 

 

기껏 해봐야 임베딩 차원? 아니면 거리 유사도 계산법이 다른건가? 등 여러가지로 복합적인 생각이 많이 들었습니다. 

 

벡터 검색에서의 인덱스 

 

오늘의 포스팅에서는 Postgres와 Pgvector의 맥락에서 벡터 인덱스와 그 장단점을 살펴보겠습니다. 특히 빌드 시간, 크기, 속도를 비교하고 이를 바탕으로 특정 애플리케이션에 어떤 것을 선택할지 결정하기 위한 몇 가지 가이드라인을 도출해 보겠습니다.

 

PGVector란? Postgre의 벡터 기능을 확장한 모듈로 이러한 벡터 데이터를 효율적으로 저장하고, 유사도 검색, 최근접 이웃 검색(k-NN)등 다양한 검색 기능을 지원하며 RAG 시스템 구현시 최적의 벡터 검색을 제공주는 솔루션 입니다.  

 

PGVector의 주요 인덱스 알고리즘

PGVector는 벡터 검색 성능을 최적화하기 위해 두 가지 주요 인덱스 알고리즘을 제공합니다.

IVFFlat (Inverted File with Flat compression)
IVFFlat은 벡터 공간을 여러 클러스터로 나누어 검색 범위를 제한하는 방식입니다. 대용량 데이터에서 메모리 효율적이며, 클러스터 수를 조정하여 정확도와 속도 사이의 균형을 맞출 수 있습니다.

HNSW (Hierarchical Navigable Small World)
HNSW는 다층 그래프 구조를 사용하여 매우 빠른 검색 속도를 제공합니다. 높은 정확도를 유지하면서도 뛰어난 성능을 보이지만, 상대적으로 많은 메모리를 사용하고 인덱스 구축 시간이 길다는 특징이 있습니다.

IVFFlat(Inverted File with Flat compression)

IVFFlat 인덱스는 테이블의 벡터를 여러 개의 클러스터로 분할하는 방식으로 동작합니다.

 

이 알고리즘은 먼저 k-means 클러스터링을 통해 여러 개의 중심점을 계산하고, 각 벡터를 가장 가까운 중심점에 할당하여 클러스터를 형성합니다.

 

결과적으로 각 중심점에 대한 inverted list가 생성되며, 이 리스트에는 해당 클러스터에 속하는 벡터들이 저장됩니다.

 

가장 가까운 K개의 벡터를 검색할 때는 모든 벡터와의 거리를 계산하는 대신, 쿼리 벡터와 가장 가까운 몇 개의 클러스터만 선택하여 검색 공간을 제한합니다.

 

이렇게 선택된 클러스터 내의 벡터들과만 거리를 계산함으로써 전체 계산량을 크게 줄일 수 있습니다.

 

이러한 방식을 통해 IVFFlat은 대용량 벡터 데이터에서도 효율적인 유사도 검색을 가능하게 합니다.

 

 

 

IVFFlat이 생성하는 클러스터 내 invested lists

 

핵심 동작법 

1. 인덱스 구축 단계

• 클러스터링 : k-means 알고리즘을 통해 벡터 공간을 여러 클러스터로 분할 
• 중심점(Centroid)계산 : 각 클러스터의 중심점을 계산 
• 벡터 할당 : 모든 벡터를 가장 가까운 중심점에 할당 
• Invested list 생성: 각 중심점에 대해 해당 클러스터에 속하는 벡터들의 ID와 값을 저장하는 리스트 생성

2. 검색 

• 쿼리 벡터 : 검색하고자 하는 벡터 입력 
• 가까운 클러스터 선택 : 쿼리 벡터와 가장 가까운 몇 개의 중심점 선택 (probes 파라미터로 개수 조절)
• 제한된 검색 : 선택된 클러스터 내의 벡터들과 거리 계산 

핵심 장점

계산량 감소: 전체 벡터 대신 일부 클러스터만 검색하여 계산 횟수 대폭 감소

메모리 효율성: 대용량 데이터에서도 효율적인 메모리 사용

조절 가능한 성능: probes 파라미터로 정확도와 속도 간의 트레이드오프 조절 가능

주요 파라미터

• lists: 클러스터 개수 (일반적으로 행 수 / 1000)
• probes: 검색 시 탐색할 클러스터 개수 (기본값: 1)

probes 값이 클수록 정확도는 높아지지만 검색 시간은 길어집니다.

 

examples 

1. 인덱스를 생성

-- 100만 개 벡터가 있다면 lists = 1000 정도로 설정
CREATE INDEX ON items USING ivfflat (embedding vector_cosine_ops) WITH (lists = 1000)

 

2. probes를 통해 탐색시킬 클러스터 개수를 지정 

-- 검색 정확도를 높이려면 probes 값을 증가
SET ivfflat.probes = 32;  -- 32개 클러스터를 탐색

 

PGVector 문서에서는 다음과 같이 제안합니다. 

 

적절한 목록 수 선택 : 최대 1M 행의 경우 (행 수 / 1000), 1M 행 이상의 경우는 행의 수만큼 제곱해서 시작하는 것이 좋다고 합니다.

 

쿼리를 날리기 전, 적절한 probes 수를 지정합니다. (높을 수록 정확도는 높아지나 검색에 의한 레이턴시가 발생, 속도 <-> 정확도 트레이드 오프 관계) 

 

HNSW (Hierarchical Navigable Small World)

HNSW 인덱스는 여러개의 레이어로 이루어진 다층 그래프 구조를 사용하여 벡터 검색을 수행하는 알고리즘 입니다. "작은세상" 네트워크 이론에 기반해서, 각 노드가 멀리 떨어진 노드들과도 연결되어 있어서 빠른 탐색이 가능합니다. 

 

 

 

핵심 동작법 

다층구조 

• 여러 개의 레이어로 구성 된 그래프 
• 상위 층 : 적은 수의 노드, 긴 거리 연결 (고속도로 역할)
• 하위 층 : 많은 노드, 세밀한 연결 (동네 길 역할)

검색 과정

1. 최상위층에서 시작해서 목표에 가까운 방향으로 빠르게 이동 
2. 점진적으로 하위층으로 내려가며 더 정밀한 검색 수행 
3. 최하위 층에서 최종적으로 가장 유사한 벡터들 찾기 

핵심 장점

 

• 빠른 검색 속도: 계층적 구조로 인한 효율적인 탐색
• 높은 정확도: 밀집된 하위층에서의 정밀한 검색
• 확장성: 대용량 데이터에서도 안정적인 성능

주요 파라미터

• m: 각 노드의 최대 연결 수 (기본값: 16)
• ef_construction: 인덱스 구축 시 탐색할 후보 수 (기본값: 64)
• ef: 검색 시 탐색할 후보 수

examples

-- HNSW 인덱스 생성
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);

 

 

-- 검색 품질 조정
SET hnsw.ef_search = 40;