안녕하세요. 자바파커입니다.

RAG나 추천 시스템을 만들다 보면 이런 SQL을 사용합니다.

SELECT id, content
FROM document_chunks
ORDER BY embedding <=> :query_embedding
LIMIT 5;

의미는 단순합니다. 질문 벡터와 가장 가까운 문서 벡터 5개를 찾는 것입니다.

문서가 1,000개라면 전부 비교해도 큰 문제가 없습니다. 하지만 벡터가 수백만 개라면 매 요청마다 모든 벡터의 거리를 계산하는 완전탐색(Exact Search) 은 부담이 커집니다.

여기서 HNSW가 등장합니다.

HNSW는 비슷한 벡터끼리 연결한 계층형 그래프를 만들고, 위층에서 멀리 이동한 뒤 아래층에서 후보를 좁혀 모든 벡터를 비교하지 않고 가까운 이웃을 찾습니다.

대신 중요한 대가가 있습니다. HNSW는 일반적으로 근사 최근접 이웃 검색(ANN) 입니다. 더 빠른 검색을 얻는 대신 항상 정확한 이웃을 찾는다고 보장하지 않습니다.

이번 글에서는 그림으로 이해하는 원리에서 끝나지 않고 pgvector 인덱스 생성, 세 가지 핵심 파라미터, 필터가 붙을 때 결과가 줄어드는 이유, recall과 지연 시간을 함께 측정하는 방법까지 정리합니다.

HNSW란? — Hierarchical Navigable Small World

HNSW는 Hierarchical Navigable Small World의 약자입니다.

단어를 나누면 구조가 보입니다.

각 벡터는 그래프의 노드가 됩니다. 비슷한 벡터끼리 간선으로 연결합니다.

q ── A ── B ── C
          │  ╱
          D ── E ── F

한 층짜리 근접 그래프만 있어도 이웃을 따라 검색할 수 있습니다. 하지만 멀리 떨어진 영역으로 이동하려면 많은 노드를 거쳐야 합니다.

HNSW는 이를 여러 층으로 쌓습니다.

Layer 2        A ─────────────── H
               │                │
Layer 1        A ─── D ─── F ─── H
               │     │     │    │
Layer 0        A─B─C─D─E─F─G─H─I─J

• 위층: 노드가 적고 연결 거리가 깁니다. 목적지 근처까지 빠르게 이동합니다.
• 아래층: 노드가 많고 연결이 촘촘합니다. 가까운 후보를 정밀하게 찾습니다.

고속도로에서 목적지 도시까지 이동한 뒤, 일반도로와 골목으로 내려오는 것과 비슷합니다.

HNSW 원 논문에서는 노드가 올라갈 최대 층을 지수적으로 감소하는 확률 분포로 정합니다. 그래서 대부분의 노드는 0층에만 있고, 소수의 노드만 위층까지 올라가 긴 거리 이동의 이정표가 됩니다.

완전탐색과 HNSW의 차이

완전탐색

질문 벡터 q와 모든 벡터의 거리를 계산하고 정렬합니다.

distance(q, v1)
distance(q, v2)
distance(q, v3)
...
distance(q, vn)

장점은 명확합니다.

• 데이터가 같고 거리 함수가 같다면 정확한 최근접 이웃을 찾습니다
• 별도 그래프 인덱스가 필요 없습니다
• 데이터가 작거나 필터 결과가 매우 작으면 오히려 단순하고 빠를 수 있습니다

단점은 데이터가 증가할수록 비교량도 함께 증가한다는 점입니다.

HNSW

HNSW는 현재 노드의 이웃 중 질문 벡터에 더 가까운 노드로 이동합니다. 더 가까워지는 이웃이 없으면 한 층 아래로 내려갑니다.

상위 Entry Point
  → 긴 점프
  → 더 가까운 노드
  → 아래층 이동
  → 후보 목록 확장
  → Top-K 반환

비교하지 않은 벡터가 남아 있으므로 검색 결과는 근사값입니다. 그래프 품질과 탐색 후보 수가 충분하지 않으면 실제 최근접 이웃을 놓칠 수 있습니다.

따라서 HNSW를 도입했다는 사실만으로 성공이 아닙니다. 정확 검색 결과를 기준으로 recall을 측정해야 합니다.

검색은 어떻게 진행될까

HNSW 검색은 크게 두 단계입니다.

1단계 — 위층에서 Greedy Search

가장 높은 층의 진입점에서 시작합니다.

현재 노드보다 질문에 가까운 이웃이 있으면 이동합니다. 더 가까운 이웃이 없을 때까지 반복한 뒤 한 층 아래로 내려갑니다.

현재 노드 A: distance = 0.82
이웃 D:      distance = 0.61  → 이동
이웃 H:      distance = 0.34  → 이동
다른 이웃:   distance > 0.34 → 멈춤, 아래층으로

상위 층의 목적은 정답을 확정하는 것이 아니라 검색할 지역을 빠르게 좁히는 것입니다.

2단계 — 0층에서 후보를 넓혀 탐색

가장 아래층에서는 후보 목록을 유지하며 여러 경로를 확인합니다.

이 후보 목록의 크기를 제어하는 대표 값이 ef_search입니다.

• 작은 ef_search: 적은 노드만 확인, 빠르지만 정답을 놓칠 가능성 증가
• 큰 ef_search: 더 많은 노드 확인, recall 증가 가능, 지연 시간 증가

검색이 끝나면 후보 중 거리가 가까운 Top-K를 반환합니다.

그래프는 어떻게 만들어질까

새 벡터가 들어오면 다음 과정을 거칩니다.

1. 새 노드가 올라갈 최대 층을 무작위로 결정합니다
2. 기존 그래프의 가장 높은 진입점에서 검색을 시작합니다
3. 각 층에서 새 노드와 가까운 후보를 찾습니다
4. 후보 중 일부를 선택해 양방향 간선을 연결합니다
5. 0층까지 내려가며 반복합니다

여기서 무조건 가장 가까운 노드만 연결하면 밀집된 한 영역에 간선이 몰릴 수 있습니다. HNSW는 탐색에 도움이 되는 다양한 방향의 이웃을 남기는 휴리스틱을 사용합니다.

이 때문에 HNSW 인덱스는 단순한 정렬 배열보다 다음 비용이 큽니다.

• 그래프를 만드는 CPU 시간
• 간선을 저장하는 메모리
• 삽입 시 이웃을 탐색하고 연결하는 비용

pgvector 문서도 HNSW가 IVFFlat보다 일반적으로 더 나은 speed-recall trade-off를 제공하지만, 빌드가 느리고 메모리를 더 사용한다고 설명합니다.

세 가지 파라미터 — M, ef_construction, ef_search

HNSW 튜닝은 우선 세 값만 구분하면 됩니다.

pgvector의 기본 예시는 다음과 같습니다.

CREATE INDEX document_chunks_embedding_hnsw_idx
ON document_chunks
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);

검색 시점에는 세션 또는 트랜잭션 범위로 설정할 수 있습니다.

BEGIN;

SET LOCAL hnsw.ef_search = 100;

SELECT id,
       content,
       1 - (embedding <=> :query_embedding) AS similarity
FROM document_chunks
ORDER BY embedding <=> :query_embedding
LIMIT 5;

COMMIT;

처음부터 값을 크게 올리지 마세요. 기본값에서 recall·p95 latency·메모리를 측정하고 병목에 맞춰 하나씩 조정하는 편이 안전합니다.

pgvector로 HNSW 구성하기

1. 확장과 테이블

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE document_chunks (
    id          bigserial PRIMARY KEY,
    document_id bigint NOT NULL,
    tenant_id   bigint NOT NULL,
    category_id bigint,
    content     text NOT NULL,
    embedding   vector(1536) NOT NULL,
    created_at  timestamptz NOT NULL DEFAULT now()
);

차원 1536은 예시입니다. 실제 임베딩 모델의 출력 차원과 반드시 일치해야 합니다.

2. 거리 함수에 맞는 인덱스

-- cosine distance
CREATE INDEX document_chunks_embedding_cosine_hnsw_idx
ON document_chunks
USING hnsw (embedding vector_cosine_ops);

-- L2 distance가 필요하면 별도 인덱스
CREATE INDEX document_chunks_embedding_l2_hnsw_idx
ON document_chunks
USING hnsw (embedding vector_l2_ops);

거리 연산자도 맞춰야 합니다.

인덱스는 만들었는데 쿼리의 거리 함수가 다르면 기대한 인덱스를 사용하지 못할 수 있습니다. EXPLAIN (ANALYZE, BUFFERS)로 실행 계획을 확인하세요.

3. 초기 대량 적재 후 인덱스 생성

초기 데이터가 크다면 먼저 데이터를 적재하고 인덱스를 만드는 편이 일반적으로 빠릅니다.

SET maintenance_work_mem = '4GB';

CREATE INDEX CONCURRENTLY document_chunks_embedding_hnsw_idx
ON document_chunks
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);

maintenance_work_mem을 무작정 크게 설정하면 서버 전체 메모리를 고갈시킬 수 있습니다. 같은 서버에서 동시에 실행되는 작업과 실제 여유 메모리를 확인해야 합니다.

실전 함정 — WHERE 필터를 붙이면 결과가 줄어든다

멀티테넌트 RAG라면 보통 벡터 검색에 필터가 붙습니다.

SELECT id, content
FROM document_chunks
WHERE tenant_id = 42
  AND category_id = 7
ORDER BY embedding <=> :query_embedding
LIMIT 10;

여기서 흔한 오해가 있습니다.

먼저 tenant_id = 42만 모은 뒤 그 안에서 HNSW를 검색하겠지?

항상 그렇지는 않습니다. pgvector의 근사 인덱스는 인덱스를 탐색한 뒤 필터가 적용될 수 있습니다. 예를 들어 탐색 후보 40개 중 필터를 통과하는 비율이 10%라면 평균적으로 4개 정도만 남을 수 있습니다. LIMIT 10인데 10개보다 적게 반환되는 이유입니다.

대응 1 — 필터 컬럼 인덱스

필터 결과가 작다면 B-tree로 후보를 좁힌 뒤 정확 벡터 검색을 하는 편이 나을 수 있습니다.

CREATE INDEX document_chunks_tenant_category_idx
ON document_chunks (tenant_id, category_id);

대응 2 — ef_search 증가

SET LOCAL hnsw.ef_search = 200;

후보를 더 많이 탐색해 필터 통과 결과를 확보합니다. 대신 느려집니다.

대응 3 — Iterative Scan

pgvector 0.8부터는 충분한 결과를 얻을 때까지 자동으로 더 탐색하는 iterative scan을 사용할 수 있습니다.

SET LOCAL hnsw.iterative_scan = strict_order;
SET LOCAL hnsw.max_scan_tuples = 20000;

strict_order는 거리 순서를 엄격하게 유지합니다. relaxed_order는 약간 느슨한 순서를 허용해 recall과 성능을 조정할 수 있습니다.

대응 4 — Partial Index 또는 Partitioning

테넌트나 카테고리 종류가 제한적이고 쿼리 패턴이 고정돼 있다면 부분 인덱스를 검토할 수 있습니다.

CREATE INDEX document_chunks_category_7_hnsw_idx
ON document_chunks
USING hnsw (embedding vector_cosine_ops)
WHERE category_id = 7;

값의 종류가 많으면 파티셔닝도 후보입니다. 다만 인덱스 개수가 폭증하지 않도록 운영 복잡도와 함께 판단해야 합니다.

Recall을 반드시 측정해야 하는 이유

ANN 검색에서 “빨라졌다”만 측정하면 부족합니다. 빠른 대신 정답을 얼마나 놓쳤는지 확인해야 합니다.

대표 지표는 Recall@K입니다.

Recall@K = ANN 결과와 Exact Top-K의 교집합 수 / K

정확 검색의 Top-10 중 HNSW가 9개를 찾았다면 Recall@10은 0.9입니다.

평가 절차

1. 실제 질의를 대표하는 query embedding 표본을 준비합니다
2. HNSW 인덱스를 끄고 Exact Top-K를 구합니다
3. 같은 질의를 HNSW로 실행합니다
4. Recall@K, p50·p95·p99 latency를 함께 기록합니다
5. ef_search를 바꿔 속도-recall 곡선을 만듭니다

pgvector에서는 비교용 세션에서 인덱스 스캔을 꺼 정확 검색 결과를 만들 수 있습니다.

BEGIN;
SET LOCAL enable_indexscan = off;

SELECT id
FROM document_chunks
ORDER BY embedding <=> :query_embedding
LIMIT 10;

COMMIT;

평가 데이터는 임의의 벡터보다 실제 사용자 질문 분포를 반영해야 합니다. 짧은 키워드, 긴 질문, 고유명사, 최신 문서, 테넌트 필터 같은 운영 쿼리를 섞으세요.

M과 ef를 어떻게 튜닝할까

검색 recall만 부족하다

먼저 ef_search를 올립니다. 인덱스를 다시 만들지 않고 쿼리 시점에 실험할 수 있기 때문입니다.

SET LOCAL hnsw.ef_search = 40;
-- benchmark

SET LOCAL hnsw.ef_search = 100;
-- benchmark

SET LOCAL hnsw.ef_search = 200;
-- benchmark

ef_search를 올려도 recall이 충분하지 않다

그래프 자체의 품질이 부족할 수 있습니다. ef_construction을 높여 인덱스를 다시 만들어 비교합니다.

데이터가 매우 복잡하고 군집이 많다

M을 높이면 노드당 연결이 늘어 탐색 경로가 풍부해질 수 있습니다. 대신 인덱스 메모리와 빌드 비용이 증가합니다.

메모리가 부족하다

• 무조건 M을 높이지 않습니다
• 인덱스가 메모리에 상주하는지 확인합니다
• 지원 범위에서 halfvec 또는 양자화를 검토합니다
• 검색 품질을 유지할 수 있는 최소 파라미터를 실험합니다

파라미터에는 모든 서비스에 통하는 정답이 없습니다. 데이터 분포, 차원, 거리 함수, 필터 선택도, 목표 recall과 지연 시간이 다르기 때문입니다.

Exact, HNSW, IVFFlat 중 무엇을 선택할까

데이터가 작을 때는 인덱스를 붙이지 않은 Exact Search가 더 낫기도 합니다. “벡터 DB니까 HNSW”가 아니라 실제 실행 계획과 벤치마크로 결정해야 합니다.

RAG에서 HNSW를 사용할 때의 전체 흐름

HNSW는 RAG 전체가 아니라 후보 검색 단계의 인덱스입니다.

사용자 질문
  ↓ embedding
query vector
  ↓ metadata filter + HNSW
candidate chunks
  ↓ reranker
top evidence
  ↓ LLM
answer + citation

검색 품질이 좋지 않을 때 HNSW 파라미터만 만지면 안 됩니다.

• 청크가 의미 단위로 잘렸는가
• 질문과 문서가 같은 임베딩 모델을 사용하는가
• 거리 함수가 모델 사용법과 맞는가
• 메타데이터 필터가 후보를 과도하게 제거하는가
• reranker가 필요한가
• 정답 문서가 실제 인덱스에 들어 있는가

HNSW는 없는 근거를 만들어 내지 못하고, 잘못된 청킹을 복구하지도 못합니다.

운영에서 자주 만나는 실패 8가지

1. 인덱스를 만들기만 하고 recall을 측정하지 않는다

지연 시간만 좋아지고 중요한 문서를 놓칠 수 있습니다. Exact 결과를 정답 집합으로 비교하세요.

2. ef_search를 무조건 크게 올린다

recall은 좋아질 수 있지만 p95 latency와 CPU가 악화됩니다. 곡선을 측정해 필요한 지점까지만 올립니다.

3. WHERE 필터를 Exact pre-filter처럼 생각한다

근사 후보를 찾은 뒤 필터링되면 결과가 부족할 수 있습니다. 선택도별로 실행 계획과 반환 개수를 확인하세요.

4. 거리 함수와 인덱스 opclass가 다르다

Cosine 쿼리에 L2 인덱스를 만들어 놓는 식의 불일치를 피해야 합니다.

5. 임베딩 모델을 바꾸고 기존 벡터와 섞는다

서로 다른 임베딩 공간의 벡터는 거리를 직접 비교할 수 없습니다. 모델 버전을 메타데이터로 관리하고 재색인 전략을 세우세요.

6. 메모리 사용량을 무시한다

벡터 원본뿐 아니라 그래프 간선과 인덱스 구조도 메모리를 사용합니다. 데이터 증가율까지 포함해 추정하세요.

7. 삭제와 갱신이 많은데 유지보수 계획이 없다

대량 변경 워크로드에서는 인덱스 팽창과 빌드 시간을 관찰하고 재색인·배치 적재 전략을 준비해야 합니다.

8. 애플리케이션 품질을 ANN recall 하나로 판단한다

검색 recall이 좋아도 최종 답변이 틀릴 수 있습니다. 검색 평가와 답변 평가를 분리하세요.

실전 도입 체크리스트

• Exact Search 기준 결과를 저장했다
• 실제 질문 표본으로 Recall@K를 측정한다
• p50·p95·p99 latency를 함께 기록한다
• Cosine·L2·Inner Product 중 거리 함수를 확정했다
• 쿼리 연산자와 HNSW opclass가 일치한다
• M, ef_construction, ef_search를 구분한다
• 필터 선택도별 반환 개수와 실행 계획을 확인한다
• 인덱스 메모리와 빌드 시간을 측정한다
• 임베딩 모델 버전과 재색인 절차가 있다
• HNSW 뒤에 reranker가 필요한지 평가한다

자주 묻는 질문

HNSW는 항상 완전탐색보다 빠른가요?

아닙니다. 데이터가 작거나 필터로 후보가 매우 적어지면 Exact Search가 더 단순하고 빠를 수 있습니다. 인덱스 탐색 오버헤드도 있기 때문에 실제 데이터로 측정해야 합니다.

HNSW 결과는 매번 정확히 같은가요?

근사 인덱스의 그래프 구성과 검색 후보 제한 때문에 Exact Top-K와 다를 수 있습니다. 동일 환경의 반복 쿼리는 보통 안정적이지만, 인덱스를 다시 만들거나 데이터 삽입 순서·설정이 바뀌면 근접한 후보들의 순서가 달라질 수 있습니다.

ef_search를 높이면 정확 검색이 되나요?

recall이 높아질 가능성은 크지만 완전한 정확성을 자동으로 보장하지는 않습니다. 정확성이 필수인 단계에서는 HNSW로 후보를 넓게 찾은 뒤 Exact distance로 재정렬하거나 Exact Search를 사용하세요.

Cosine similarity를 쓰려면 벡터를 정규화해야 하나요?

사용하는 임베딩 모델과 데이터베이스 연산자의 정의를 확인해야 합니다. 일부 모델은 정규화된 벡터를 반환하고, 일부는 애플리케이션에서 정규화해야 합니다. 모델 문서와 저장 파이프라인을 한 쌍으로 관리하세요.

HNSW와 reranker는 같은 역할인가요?

아닙니다. HNSW는 큰 후보 집합에서 가까운 벡터를 빠르게 찾습니다. reranker는 이렇게 찾은 소수 후보를 더 비싼 모델로 정밀하게 재정렬합니다.

마치며

HNSW의 핵심은 복잡한 수식이 아닙니다.

위층에서 멀리 이동하고, 아래층에서 후보를 넓혀 가까운 이웃을 찾는다.

이 구조 덕분에 모든 벡터를 비교하지 않고도 빠른 검색이 가능합니다. 대신 근사 검색이므로 recall과 지연 시간의 교환 관계를 직접 측정해야 합니다.

실무에서는 다음 순서로 시작하면 됩니다.

1. Exact Search로 정답 집합을 만든다
2. 기본 HNSW 설정으로 속도와 recall을 측정한다
3. 먼저 ef_search를 조정한다
4. 부족하면 ef_construction과 M을 검토한다
5. 필터가 붙으면 반환 개수와 iterative scan을 확인한다

HNSW는 “벡터 DB를 빠르게 해 주는 마법”이 아니라 탐색 범위를 줄이는 그래프 인덱스입니다. 이 경계를 이해하면 RAG 검색 품질 문제를 청킹·임베딩·필터·인덱스·재정렬 단계로 나눠 진단할 수 있습니다.

참고 자료

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• pgvector — HNSW indexing and query options
• pgvector — Filtering and iterative index scans
• 하이브리드 Markdown으로 비정형 문서를 보존하는 방법
• 정형 데이터를 Semantic Layer와 TAG로 질의하는 방법