pgvector와 HNSW를 밑바닥부터 이해하기

RAG 검색 SQL에 권한, 공장, 버전, 유효기간 조건을 넣는 방향을 정리하다가 다음 설명에서 멈췄다.

pgvector HNSW에서는 필터와 ANN 실행 순서 때문에 recall이 줄 수 있다.

내가 궁금했던 것은 사용법이 아니었다.

WHERE를 먼저 썼는데 왜 필터가 나중에 적용된다는 것인가? pgvector는 정확히 무엇이고, HNSW와 ANN은 무엇이며, 그 실행 순서가 왜 정답 문서를 놓치게 만드는가?

이 글은 이 질문 하나를 끝까지 내려간 기록이다. 결론부터 쓰면 다음과 같다.

SQL에 WHERE가 먼저 적혀 있어도 HNSW 검색기가 그 조건을 먼저 처리한다는 뜻은 아니다. pgvector의 HNSW 인덱스는 기본적으로 전체 그래프에서 벡터상 가까워 보이는 후보를 제한된 탐색 예산으로 먼저 만든다. PostgreSQL executor가 그 후보에 일반 WHERE 조건을 적용한다. 후보 대부분이 다른 권한·공장·버전의 문서라면 허용 문서가 거의 남지 않는다. 더 나쁜 경우, 허용 집합 안의 진짜 top-k는 전체 그래프의 초기 ANN 후보에 들지 못해 사라진다. 이것이 filtered ANN에서 recall이 낮아지는 근원이다.

이 문장을 이해하려면 pgvector, nearest neighbor, ANN, HNSW, PostgreSQL index scan, filter selectivity, recall을 따로 이해한 뒤 다시 연결해야 한다.

조사 기준일은 2026년 7월 22일이다. 구현 세부사항은 당시 최신 release인 **pgvector 0.8.5, commit 159b79aaad5983fb7459c1e3df2897fbb2d11788**와 PostgreSQL 18을 기준으로 직접 확인했다. Docker 재현 환경은 PostgreSQL 18.4와 pgvector 0.8.5다. 버전이 달라지면 기본값과 내부 구현을 다시 확인해야 한다.

이 글에서 얻을 답과 범위

이 글은 다음 질문을 한 흐름 안에서 닫는다.

pgvector가 PostgreSQL에 추가하는 type, operator, index access method는 무엇인가
exact nearest neighbor와 ANN은 무엇을 교환하는가
HNSW graph는 어떻게 만들고 어떤 상태를 유지하며 어떻게 탐색하는가
PostgreSQL planner와 executor는 HNSW ORDER BY, 일반 WHERE, LIMIT을 어떻게 연결하는가
post-filter가 결과 수와 Recall@k를 왜 줄이는가
iterative scan은 무엇을 재개하며 strict와 relaxed가 왜 다른가
insert, update, delete, vacuum, MVCC, WAL, replica에서 HNSW가 어떻게 유지되는가
exact prefilter, partial index, partitioning, adaptive routing 중 무엇을 언제 고를 것인가

embedding model 학습, chunking 전략 전체, lexical ranking 수식, reranker, LLM generation 품질은 이 글의 범위 밖이다. 이 글에서 필요한 연결점만 설명한다. 실제 RAG table의 schema, 데이터 분포, 기존 index를 받지 않았으므로 특정 production index DDL을 확정하지도 않는다. 대신 그 결정을 내릴 수 있는 원리와 검증 절차를 끝까지 제공한다.

왜 필요한가와 해결할 문제

질문의 SQL은 다음과 같았다.

SELECT id, content
FROM document_chunks
WHERE realm_id = :realm_id
  AND module_id = :module_id
  AND approval_status = 'APPROVED'
  AND :plant_id = ANY(plant_scope)
  AND valid_from <= :today
  AND (valid_to IS NULL OR valid_to >= :today)
  AND acl_allows(:role)
ORDER BY embedding <=> :query_vector
LIMIT 20;

논리적 요구는 맞다.

전체 문서 D
  → realm/module/승인/공장/유효기간/ACL을 통과한 허용 집합 F
  → F 안에서 query와 가장 가까운 20개

수식으로 쓰면 원하는 답은 다음이다.

T_k(q, F) = \operatorname{topk}_{x \in F}\ d(q, x)

$D$ — 전체 청크 집합
$F \subseteq D$ — 모든 업무·보안 필터를 통과한 청크 집합
$q$ — 질문 임베딩
$d(q,x)$ — 질문과 청크 사이 거리
$k=20$ — 원하는 결과 수

이것은 허용 집합 안에서의 nearest neighbor 문제다.

하지만 하나의 전역 HNSW 인덱스를 쓰는 실제 실행은 개념적으로 다음에 가까울 수 있다.

A_B(q,D) = \operatorname{ANNCandidates}_B(q,D)

R = \operatorname{topk}(A_B(q,D) \cap F)

먼저 전체 집합 $D$ 에서 탐색 예산 $B$ 만큼 ANN 후보 $A_B$ 를 만들고, 그 뒤 허용 집합 $F$ 와 교집합을 취한다.

이 둘은 일반적으로 같지 않다.

\operatorname{topk}(F(D)) \neq F(\operatorname{topB}(D))

정렬과 필터는 교환법칙이 성립하지 않는다. 이 비가환성이 질문의 핵심이다.

먼저 알아야 할 선행 개념

Nearest Neighbor와 k-NN

Nearest Neighbor Search는 query point와 가장 가까운 data point를 찾는 문제다. 가장 가까운 하나가 아니라 $k$ 개를 찾으면 k-Nearest Neighbors, k-NN이다.

RAG에서는 보통 다음이 점이다.

문서 청크 x  → embedding(x) → d차원 점
사용자 질문 q → embedding(q) → 같은 d차원 점

질문 벡터와 거리가 작은 청크 벡터를 찾고, 그 청크에 연결된 원문을 LLM에 전달한다. pgvector는 원문을 이해하거나 답을 생성하지 않는다. 숫자 벡터를 저장하고 거리 계산과 검색 경로를 PostgreSQL 안에 제공한다.

Exact Nearest Neighbor

Exact search는 검색 대상의 거리를 빠짐없이 비교해 진짜 top-k를 찾는다. 필터를 통과한 행 수가 $N_F$ , 벡터 차원이 $d$ 라면 단순 거리 계산 비용은 대략 다음에 비례한다.

O(N_F \cdot d)

그 뒤 top-k를 고르는 비용도 든다. 모든 후보를 확인했으므로 거리 함수와 데이터가 같다면 정답 집합에 대한 recall은 1이다.

ANN

ANN은 Approximate Nearest Neighbor Search다. 모든 벡터를 보지 않고도 가까운 벡터를 빨리 찾기 위해 탐색 공간을 줄인다.

Exact: 느릴 수 있지만 진짜 top-k 보장
ANN:   빠르지만 진짜 top-k 일부를 놓칠 수 있음

Approximate는 벡터 값이 대충 저장된다는 뜻이 아니다. HNSW의 경우 핵심 근사는 전체 점을 다 평가하지 않고 그래프의 일부 경로만 탐색한다는 데 있다. 같은 원본 벡터와 같은 거리 함수를 쓰더라도 방문하지 않은 점은 결과가 될 수 없다.

Recall@k

검색기의 recall은 생성 LLM의 회상 능력이 아니다. exact search가 찾은 정답 집합과 ANN 결과의 겹침을 측정한다.

Recall@k = \frac{|ANN_k(q) \cap Exact_k(q)|}{k}

exact top-20 중 ANN이 16개를 찾았다면 Recall@20 = 16 / 20 = 0.8이다.

filtered ANN을 평가할 때 exact 정답도 반드시 같은 권한·공장·유효기간 필터를 적용한 집합에서 만들어야 한다. 전체 corpus의 exact top-k와 비교하면 다른 문제를 측정하게 된다.

또 하나 분리할 지표가 있다.

FillRate@k = \frac{\min(|R|,k)}{k}

LIMIT 20인데 4행만 반환했다면 fill rate는 0.2다. 20행을 채웠어도 정답 top-20을 많이 놓칠 수 있으므로 fill rate와 recall은 별개다.

pgvector는 무엇인가와 하지 않는 일

pgvector는 별도 서버인 벡터 데이터베이스가 아니다. PostgreSQL에 설치하는 C extension이다. 패키지와 프로젝트 이름은 pgvector지만 SQL에서 만드는 extension 이름은 vector다.

CREATE EXTENSION vector;

pgvector는 PostgreSQL에 다음을 추가한다.

벡터를 담는 data type
벡터 연산자와 거리 함수
exact nearest-neighbor SQL 표현
HNSW와 IVFFlat이라는 ANN index access method
벡터 집계, 변환, 양자화 관련 함수

반대로 다음 일은 하지 않는다.

문서를 청킹하지 않는다.
임베딩을 생성하지 않는다.
embedding model의 버전 호환성을 관리하지 않는다.
ACL의 의미를 알지 못한다.
lexical search와 dense search를 자동 결합하지 않는다.
reranker나 생성 LLM을 실행하지 않는다.

RAG pipeline에서 경계를 그리면 다음과 같다.

[애플리케이션/파이프라인]
문서 → 파싱 → 청킹 → embedding model
                         ↓
[PostgreSQL + pgvector]
원문/metadata/embedding 저장 → 거리 계산 → exact 또는 ANN 후보 반환
                                                    ↓
[애플리케이션/파이프라인]
lexical 결합 → reranking → context 조립 → LLM

pgvector가 PostgreSQL 안에 있다는 점은 중요하다. 벡터와 일반 관계형 열을 같은 row, transaction, WAL, backup, replica, SQL query 안에서 다룰 수 있다. 동시에 HNSW가 일반 B-tree처럼 모든 WHERE 조건을 자연스럽게 흡수한다고 가정하면 안 된다. PostgreSQL 안에 들어왔다는 사실과 HNSW 알고리즘이 metadata-aware search가 됐다는 주장은 서로 다르다.

vector 한 행은 메모리에서 어떻게 생겼나

pgvector 0.8.5의 Vector 구조체는 다음 정보를 가진다.

typedef struct Vector
{
    int32       vl_len_;
    int16       dim;
    int16       unused;
    float       x[FLEXIBLE_ARRAY_MEMBER];
} Vector;

핵심은 dim과 이어지는 float 배열이다. vector의 각 원소는 PostgreSQL real과 같은 single-precision floating point다. 공식 reference의 저장량은 다음이다.

vector storage = 4 * dimensions + 8 bytes

예를 들어 1,024차원 vector 자체는 계산상 4 * 1024 + 8 = 4,104 bytes다. 여기에 heap tuple header, alignment, 다른 열, index graph link, page overhead가 따로 붙는다. 따라서 이 숫자를 테이블 전체 row size나 HNSW index size로 오해하면 안 된다.

pgvector 0.8.5는 다음 표현을 지원한다.

타입	한 원소의 성격	타입 저장 한도	HNSW 인덱스 한도	주 용도
`vector`	float32 dense	16,000차원	2,000차원	일반 dense embedding
`halfvec`	float16 dense	16,000차원	4,000차원	index·storage 절감
`bit`	binary bit	PostgreSQL bit 범위	64,000차원	binary quantization, hash
`sparsevec`	`index:value` 쌍	10억 차원·non-zero 16,000개	non-zero 1,000개	sparse vector

여기서 타입에 저장 가능한 차원과 특정 인덱스가 처리 가능한 차원은 다르다. vector 열에 3,072차원 값을 저장할 수 있어도 같은 값을 그대로 vector HNSW에 넣을 수는 없다. half precision indexing, binary quantization, subvector, dimensionality reduction 같은 별도 선택이 필요하다. pgvector HNSW 문서는 이 한도를 따로 명시한다.

거리 함수가 검색 공간을 정의한다

벡터를 저장하는 것만으로 nearest neighbor의 의미는 정해지지 않는다. 어떤 distance 또는 similarity를 쓸지 정해야 한다.

L2 distance

embedding <-> :query_vector

d_{L2}(x,y)=\sqrt{\sum_{i=1}^{d}(x_i-y_i)^2}

유클리드 공간의 직선거리다. 작은 값이 가깝다.

Inner product

embedding <#> :query_vector

x \cdot y = \sum_{i=1}^{d} x_i y_i

inner product는 클수록 유사하다. PostgreSQL의 operator ordering index 경로는 작은 값을 앞에 두는 ascending distance 형태를 사용하므로 pgvector의 <#>는 negative inner product를 반환한다.

SELECT (embedding <#> :query_vector) * -1 AS inner_product;

Cosine distance

embedding <=> :query_vector

cosine\_similarity(x,y)=\frac{x \cdot y}{\|x\|_2\|y\|_2}

cosine\_distance(x,y)=1-cosine\_similarity(x,y)

pgvector 소스도 dot product와 두 norm을 계산한 뒤 1.0 - similarity를 반환한다. 실제 구현은 src/vector.c의 cosine_distance에서 확인했다.

cosine은 방향을 보고 magnitude를 제거한다. 모델이 unit-normalized vector를 반환한다면 다음 관계가 성립한다.

\|x-y\|_2^2 = 2 - 2(x\cdot y)

따라서 unit vector에서는 L2, cosine, inner product의 ranking이 단조 관계를 가질 수 있다. 그래도 실제 index opclass와 query operator는 반드시 맞춰야 한다.

L1, Hamming, Jaccard

<+>  L1 또는 taxicab distance
<~>  Hamming distance for bit
<%>  Jaccard distance for bit

pgvector의 operator 정의와 HNSW operator class 연결은 sql/vector.sql 172~332행에 있다.

왜 metric별 인덱스를 따로 만드는가

CREATE INDEX chunks_embedding_hnsw_cosine
ON document_chunks
USING hnsw (embedding vector_cosine_ops);

HNSW graph의 edge는 해당 distance function에서 가까운 이웃을 기준으로 만들어진다. L2로 만든 graph가 cosine ordering도 보장하는 범용 graph가 아니다. pgvector가 metric별 operator class와 index를 나누는 이유다.

ORDER BY embedding <=> :query_vector를 썼는데 index가 vector_l2_ops라면 그 index는 cosine query를 위한 index가 아니다.

cosine HNSW 내부에서는 왜 inner product를 쓰는가

여기서 소스를 읽지 않으면 놓치기 쉬운 최적화가 하나 있다. HNSW용 vector_cosine_ops는 ordering operator로 <=>를 등록하지만 내부 distance support function은 vector_negative_inner_product, norm support function은 vector_norm으로 등록한다.

index build와 insert에서는 HnswFormIndexValue가 norm이 0보다 큰지 확인하고 vector를 L2 normalize한다. query vector도 GetScanValue에서 같은 방식으로 normalize한다.

unit vector끼리는 다음 관계다.

cosine\_distance(x,y)=1-(x\cdot y)

-(x·y)와 1-(x·y)는 모든 값에 같은 상수 1 차이만 있으므로 ordering이 같다. graph traversal에서는 norm과 square root를 반복 계산하지 않고 negative inner product로 같은 순위를 얻을 수 있다. SQL의 <=> 의미가 inner product로 바뀐 것이 아니라 HNSW 내부 ordering에 단조 동치인 더 싼 함수를 쓴 것이다.

zero vector가 cosine HNSW에 들어가지 않는 원인도 여기서 보인다. norm이 0이면 normalize할 수 없고 cosine 방향도 정의되지 않으므로 HnswFormIndexValue가 index value 생성을 중단한다.

인덱스가 없을 때 pgvector는 exact search를 한다

pgvector 공식 README는 기본 검색이 exact nearest neighbor이며 perfect recall을 제공한다고 명시한다. HNSW나 IVFFlat index를 만들기 전에도 다음 SQL은 동작한다.

SELECT id, content
FROM document_chunks
WHERE realm_id = :realm_id
  AND approval_status = 'APPROVED'
ORDER BY embedding <=> :query_vector
LIMIT 20;

가능한 물리 계획을 단순화하면 다음과 같다.

metadata 조건으로 row를 찾음
  → 각 surviving row의 exact distance 계산
  → top-N heapsort 또는 sort
  → 20개 반환

metadata B-tree/GIN index가 유리하면 PostgreSQL planner가 그것으로 허용 행을 먼저 찾은 뒤 거리를 정렬할 수 있다. 조건이 넓으면 sequential scan과 sort를 택할 수 있다. SQL 텍스트 순서가 아니라 통계와 cost를 바탕으로 planner가 경로를 선택한다.

필터 후 집합이 작다면 이 exact path가 오히려 빠르고 정확할 수 있다. pgvector 문서도 낮은 비율의 행만 일치하는 조건에서는 filter column에 일반 index를 만들고 exact search를 하는 것을 첫 선택지로 제시한다.

왜 ANN이 필요한가

1,024차원 청크가 1,000만 개 있고 filter도 넓다고 하자. 질문마다 모든 vector와 cosine을 계산하면 최소한 수십억 단위의 multiply/add와 대량 memory access가 필요하다. CPU vectorization과 parallel scan을 써도 query latency와 동시성 비용이 커진다.

ANN index는 다음 교환을 한다.

모든 점을 확인하는 비용 일부를 버림
  ↔ 진짜 nearest neighbor 일부를 놓칠 가능성을 받음

pgvector가 제공하는 ANN index는 HNSW와 IVFFlat이다.

구분	HNSW	IVFFlat
구조	multi-layer proximity graph	centroid별 inverted list
사전 training	없음	centroid training 필요
query 핵심 knob	`ef_search`	`probes`
build	느리고 memory 사용 큼	상대적으로 빠르고 작음
일반적 특징	speed-recall trade-off가 좋음	lists/probes와 학습 데이터에 민감

IVFFlat도 원리만큼은 분리해 두기

IVFFlat의 IVF는 inverted file, Flat은 선택한 list 안에서 원본 vector distance를 직접 비교한다는 뜻이다.

index build
  → representative vector로 k-means 수행
  → list centroid 생성
  → 각 vector를 가장 가까운 centroid의 list에 배치

query
  → query와 가까운 centroid를 찾음
  → probes개 list만 열음
  → 그 list 안의 vector distance를 비교
  → top-k 반환

근사는 보지 않은 list에서 생긴다. 진짜 neighbor가 선택되지 않은 list에 있으면 결과에 들어올 수 없다. ivfflat.probes를 높이면 더 많은 list를 열어 recall과 비용이 함께 증가한다. probes=lists면 모든 list를 보므로 exact 방향으로 가지만 pgvector 문서는 그 지점에서 planner가 IVFFlat index를 사용하지 않을 수 있다고 설명한다.

DDL은 다음처럼 list 수를 build parameter로 고정한다.

CREATE INDEX chunks_embedding_ivfflat_cosine
ON document_chunks
USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 100);

IVFFlat build는 실제로 무엇을 만드는가

pgvector 0.8.5 build source는 initializing → performing k-means → assigning tuples → loading tuples 단계로 진행한다. 내부를 더 풀면 다음과 같다.

table row를 표본 추출한다. ComputeCenters는 list당 50개, 최소 10,000개를 목표 표본 수로 잡되 실제 table보다 많이 뽑지는 않는다.
표본에서 k-means++ 방식으로 초기 centroid를 고른다.
Elkan k-means로 각 표본을 가장 가까운 centroid에 할당하고 cluster 평균으로 centroid를 갱신한다. 할당이 더 바뀌지 않거나 최대 iteration에 닿을 때까지 반복한다. 구현은 ivfkmeans.c와 Elkan loop에 있다.
table 전체를 다시 읽어 각 vector를 가장 가까운 centroid의 list에 배정하고, list 번호 순으로 sort한 뒤 entry page에 적재한다. BuildIndex가 이 assign, sort, load 흐름을 연결한다.

가장 작은 1차원 예를 보자.

data     1, 2, 3, 98, 99, 100
lists    2
centroid 약 2와 99
list A   1, 2, 3
list B   98, 99, 100

query가 4이고 probes=1이면 centroid 2의 list A만 열고 세 vector를 flat distance 비교한다. query가 50처럼 cluster 경계에 있으면 한 list만 보는 선택이 진짜 이웃을 놓치기 쉬워진다. probes=2면 양쪽 list를 모두 보지만 이 작은 예에서는 전체 scan과 같은 일을 한다.

IVFFlat의 disk 구조

pgvector source의 IvfflatMetaPageData와 IvfflatListData를 보면 세 층으로 나뉜다.

metapage
  magic, version, dimensions, lists

list pages
  centroid, 첫 entry page, 현재 insert page

entry pages
  원본 index vector value, heap TID

여기서 inverted list는 검색 엔진의 token posting list와 역할이 비슷하다. centroid가 coarse routing key이고 entry page chain이 그 centroid에 속한 vector 모음이다. Flat이라는 이름대로 product quantization 같은 압축 거리만 보는 것이 아니라 선택한 entry의 vector distance를 계산한다.

IVFFlat query의 정확한 순서

pgvector의 GetScanLists는 query와 모든 list centroid의 거리를 계산해 가까운 list page를 고른다. GetScanItems는 선택된 probes개 list의 모든 entry page를 읽고 각 vector의 실제 거리를 계산한 뒤 정렬한다.

list가 균등하다는 이상적 가정 아래 list 수를 $L$ , probe 수를 $P$ 라고 하면 방문 vector 기대량은 대략 $PN/L$ 이다. centroid routing과 vector distance를 합친 거친 계산량은 다음과 같다.

O(Ld) + O\left(\frac{PN}{L}d\right)

하지만 cluster 크기가 치우치면 $N/L$ 가정은 깨진다. list 수를 늘리면 한 list는 작아지지만 centroid 비교, training, 빈 list와 경계 오류가 늘어난다. probes를 늘리면 recall은 좋아지지만 entry page I/O와 distance 계산이 늘어난다. 그래서 lists와 probes도 실제 corpus의 recall-latency curve로 정해야 한다.

insert, update, delete에서 centroid는 어떻게 되는가

새 row를 insert할 때 k-means를 다시 학습하지 않는다. FindInsertPage가 저장된 centroid를 모두 비교해 가장 가까운 기존 list를 고르고, InsertTuple이 vector와 heap TID를 그 list의 entry page chain에 추가한다.

PostgreSQL update가 embedding index key를 바꾸면 기존 index tuple은 MVCC상 old row를 가리키고 새 값은 insert 경로로 새 list에 들어간다. delete와 dead old version은 VACUUM 때 정리된다. IVFFlat의 ivfflatbulkdelete는 각 list entry page를 순회하며 dead heap TID의 index tuple을 지운다. VACUUM은 centroid를 재학습하지 않는다.

따라서 생성 후 데이터 분포가 크게 이동하면 새 vector는 낡은 centroid 중 하나에 계속 들어가고 list가 불균형해질 수 있다. 이 상태는 VACUUM만으로 고쳐지지 않는다. 실제 분포로 REINDEX CONCURRENTLY 또는 새 index를 만들고 교체하는 운영 판단이 필요하다.

IVFFlat은 centroid가 데이터 분포를 대표해야 하므로 데이터가 거의 없을 때 먼저 만들면 낮은 recall이 생길 수 있다. 실제 source도 sample 수가 list 수보다 작으면 ivfflat index created with little data와 This will cause low recall notice를 낸다. HNSW는 centroid training이 없어 빈 table에도 만들 수 있지만 insert마다 graph construction을 수행한다.

IVFFlat도 일반 scalar filter를 list routing에 넣지 않는다. candidate에 filter를 적용해 행이 부족하면 0.8.0 이후 ivfflat.iterative_scan = relaxed_order가 더 많은 list를 열 수 있고, ivfflat.max_probes가 상한을 정한다. strict order mode는 HNSW에만 있다. 이 기능도 filter-aware centroid를 만드는 것이 아니라 기존 list를 더 많이 읽는 보상이다.

이 글의 핵심 질문은 HNSW filtered search이므로 이후에는 HNSW graph를 집중해서 내려간다.

HNSW 밑바닥 원리와 알고리즘

HNSW는 Hierarchical Navigable Small World graph다.

Graph

각 vector가 node이고, 가까운 vector끼리 edge로 연결된다.

node A ─ node B ─ node C
   │         ╲       │
 node D ───── node E

query는 graph에 저장된 node가 아니어도 된다. 현재 node의 이웃 vector들과 query distance를 비교하며 가까운 방향으로 이동한다.

Small World

small-world network는 가까운 지역 연결과 먼 지역을 잇는 shortcut이 함께 있어 적은 hop으로 멀리 갈 수 있는 구조다.

동네 골목만 있으면 부산에서 서울까지 수많은 교차로를 지나야 한다. 고속도로가 있으면 먼저 먼 거리 scale을 줄인 뒤 목적지 근처 골목으로 내려온다.

HNSW에서 위 layer의 드문 node와 긴 edge가 고속도로 역할을 하고, layer 0의 조밀한 edge가 골목 역할을 한다.

Navigable

graph가 단순히 연결돼 있다는 뜻을 넘는다. 현재 위치의 neighbor distance를 비교하는 greedy navigation으로 query 근처까지 갈 수 있도록 proximity link를 고른다는 뜻이다.

Hierarchical

모든 node는 layer 0에 있다. 일부 node만 layer 1, 그보다 더 적은 node만 layer 2 이상에도 존재한다.

Layer 3:                 A
                         │
Layer 2:          A ───────────── H
                   ╲              │
Layer 1:      A ── C ── E ─────── H ── K
              │    │    │          │    │
Layer 0:      A-B--C-D--E-F-G------H-I--J-K-L-M

이 그림의 같은 문자 node는 여러 layer에 나타난 같은 data point다. 검색은 가장 높은 entry point에서 시작해 coarse navigation을 하고, 그 위치를 다음 layer의 시작점으로 사용한다.

HNSW 원 논문은 이를 1차원 skip list를 proximity graph로 일반화한 것으로 설명한다. level이 높아질 확률을 지수적으로 낮추면 위로 갈수록 node가 희소해진다. HNSW 원 논문의 핵심 아이디어다.

HNSW graph는 어떻게 만들어지는가

HNSW는 vector를 순서대로 삽입하면서 graph를 만든다. pgvector에는 IVFFlat 같은 training phase가 없다는 말이 이 뜻이다. training-free이지 construction-free가 아니다. 삽입마다 이웃 탐색과 양방향 edge 갱신이 필요하다.

1. 새 node의 최고 layer를 무작위로 정한다

논문의 level 선택은 다음이다.

l = \lfloor -\ln(U) \cdot m_L \rfloor, \quad U \sim Uniform(0,1)

pgvector 0.8.5도 HnswInitElement에서 같은 형태를 사용한다.

int level = (int) (-log(RandomDouble()) * ml);

그리고 ml = 1 / log(m)을 사용한다. level 0 node는 많고 높은 level node는 지수적으로 드물다. 특정 vector의 내용이 중요해서 위 layer로 올라가는 것이 아니다. level은 확률적으로 정한다.

2. 현재 entry point에서 새 vector 근처로 내려간다

현재 graph의 최고 entry point에서 시작한다. 새 node의 level보다 높은 layer에서는 ef=1 greedy search로 가장 가까운 방향을 찾으며 내려온다.

top layer entry
  → neighbor 중 query에 더 가까운 node
  → 더 가까워지는 neighbor가 없으면 한 layer 하강

3. 연결할 layer에서는 넓은 후보를 본다

새 node가 실제로 참여할 layer부터 layer 0까지는 ef_construction 크기의 dynamic candidate list로 주변을 더 넓게 탐색한다.

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

m — layer당 연결 수의 기준. pgvector 기본 16
ef_construction — 삽입 시 이웃 후보 탐색 폭. 기본 64

pgvector는 layer 0에서 2 * m, 그 위 layer에서 m을 연결 한도로 사용한다. 이 규칙은 HnswGetLayerM에 명시돼 있다.

4. 단순히 가장 가까운 M개만 연결하지 않는다

가까운 node만 고르면 한 cluster 내부 edge로 가득 차고 다른 cluster로 넘어가는 길이 약해질 수 있다. HNSW는 neighbor selection heuristic으로 방향과 지역이 겹치는 후보를 일부 제거해 연결 다양성을 남긴다.

새 node q에 가까운 후보를 순서대로 보면서, 이미 선택한 이웃보다 q에 더 직접적인 연결 가치가 있는 후보를 고른다. 원 논문의 의도는 relative neighborhood graph와 비슷한 구조를 근사해 cluster 사이 global connectivity를 보존하는 것이다.

이것이 m을 단순히 “nearest M개”라고 번역하면 안 되는 이유다.

5. 양방향 edge를 갱신하고 넘친 이웃을 가지치기한다

새 node에서 이웃으로만 edge를 긋지 않는다. 선택한 기존 이웃에서도 새 node로 edge를 추가한다. 기존 node의 연결 수가 한도를 넘으면 neighbor selection을 다시 적용해 prune한다.

m을 키우면 경로가 풍부해져 recall이 오를 가능성이 있지만 다음 비용도 증가한다.

index size
build time
insert/update cost
한 node 방문 시 확인할 neighbor 수
cache pressure

그래서 m은 query knob가 아니라 graph topology를 바꾸는 build-time knob다.

HNSW query는 어떻게 동작하는가

검색도 두 구간으로 나뉜다.

위 layer에서는 `ef=1`로 빠르게 내려간다

pgvector의 GetScanItems는 entry point의 최고 layer부터 layer 1까지 HnswSearchLayer(..., ef=1, ...)를 호출한다.

entry point
  → 현재 layer에서 greedy local minimum
  → 그 node를 다음 layer entry로 사용
  → layer 1까지 반복

위 layer의 역할은 exact 결과를 고르는 것이 아니다. layer 0 search를 시작할 좋은 지역을 빠르게 찾는 것이다.

layer 0에서는 `ef_search`만큼 후보 폭을 유지한다

layer 0에서는 기본값 40인 hnsw.ef_search를 사용한다.

SET hnsw.ef_search = 100;

ef_search는 LIMIT와 같은 값이 아니다.

LIMIT k — executor가 사용자에게 반환하려는 행 수
ef_search — HNSW layer 0 search의 dynamic candidate/result queue 폭

보통 ef_search가 클수록 graph를 더 넓게 탐색해 local minimum에서 벗어나고 진짜 neighbor를 찾을 가능성이 커진다. 대신 distance computation, page read, memory, latency가 증가한다.

내부에는 visited set과 두 우선순위 queue가 있다

원 논문의 SEARCH-LAYER와 pgvector의 HnswSearchLayer는 같은 핵심 구조를 가진다.

v: 이미 방문한 node set
C: 아직 확장할 candidate 중 query에 가장 가까운 node를 먼저 꺼내는 queue
W: 지금까지 찾은 좋은 후보 ef개를 유지하는 queue

단순화한 알고리즘은 다음과 같다.

C와 W에 entry point를 넣는다.

while C가 비어 있지 않다:
    c = C에서 query에 가장 가까운 미확장 후보
    f = W에서 query와 가장 먼 후보

    if distance(c, query) > distance(f, query):
        break

    for e in neighbors(c):
        if e를 아직 방문하지 않았다:
            visited에 e 추가
            if W가 ef보다 작거나 e가 f보다 가깝다:
                C와 W에 e 추가
                W가 ef보다 커지면 가장 먼 후보 제거

return W

종료 조건이 근사 지점이다. 현재 확장할 최선의 candidate조차 W의 최악 후보보다 멀면 더 가도 이득이 없다고 보고 멈춘다. graph edge가 완전하지 않고 모든 node를 방문하지 않았으므로, 실제로는 다른 경로 뒤에 더 가까운 node가 숨어 있을 수 있다.

ef_search를 키우면 W가 더 많은 후보를 유지해 더 오래 backtracking할 수 있다. recall과 latency가 함께 오르는 이유다.

pgvector HNSW 내부 구조와 실행 흐름

추상적인 graph가 PostgreSQL index page에 어떻게 들어가는지도 확인했다.

pgvector 0.8.5의 hnsw.h에는 세 핵심 구조가 있다.

Meta page

magic number / version
dimensions
m / ef_construction
entry point의 block / offset / level
다음 insert page

index block 0은 meta page다. 검색은 여기서 현재 entry point와 m을 읽는다.

Element tuple

tuple type
level / deleted / version
heap TID 목록
neighbor tuple 위치
vector data

HNSW index가 단순히 heap row ID만 저장하는 것은 아니다. graph traversal 중 distance를 계산해야 하므로 element tuple 안에 vector data도 둔다. heap TID는 최종적으로 PostgreSQL table row를 찾는 연결점이다.

Neighbor tuple

tuple type / version / count
neighbor element들의 index TID 배열

element와 neighbor 목록을 분리하고, block/offset으로 index 안의 다른 element를 가리킨다. layer별 neighbor 영역은 높은 layer부터 이어진다.

이 때문에 HNSW index size는 4 * dimensions + 8인 vector column 크기만 계산해서 나오지 않는다. vector 복사, element tuple, neighbor tuple, page overhead, dead entry와 vacuum 상태가 모두 붙는다.

INSERT, UPDATE, DELETE, VACUUM

새 row insert는 HnswInsertTupleOnDisk로 들어간다.

meta page에서 m과 entry point 읽기
  → 새 element와 random level 생성
  → HnswFindElementNeighbors로 layer별 이웃 탐색
  → element tuple과 neighbor tuple 기록
  → 기존 이웃의 reverse edge 갱신
  → 새 node level이 더 높으면 entry point 갱신

일반 insert는 update page lock을 shared로 잡는다. 새 node가 현재 entry point보다 높은 level일 가능성이 있으면 exclusive lock으로 다시 잡고 최신 entry point를 읽는다. 이 잠금은 모든 graph 작업을 한 줄로 직렬화하려는 table lock이 아니라 insert와 vacuum repair가 깨진 edge를 보지 않게 조정하는 HNSW index page lock이다.

vector column update는 새 embedding에 대한 새 index entry를 만들고 old heap tuple과 연결된 TID는 나중 정리 대상이 된다. PostgreSQL의 MVCC update는 row를 제자리 덮어쓰는 단순 수정이 아니기 때문이다. vector가 바뀌면 indexed column update라 HOT update로 HNSW index 변경을 피할 수도 없다.

delete 직후 graph의 모든 edge를 즉시 재작성하지 않는다. heap tuple은 transaction visibility 규칙에 따라 dead가 되고, VACUUM이 HNSW graph를 정리한다. 0.8.5의 hnswbulkdelete는 다음 pass를 명시한다.

Pass 1  dead heap TID 제거와 삭제 예정 element 수집
Pass 2  삭제 예정 element를 가리키는 graph edge repair
Pass 3  repair 완료 검증
Pass 4  element를 deleted로 표시하고 vector와 neighbor link 비움

순서가 중요한 이유는 node를 먼저 지우면 그 node를 경유하던 graph connectivity가 끊길 수 있기 때문이다. vacuum은 먼저 살아 있는 node의 neighbor를 다시 구성하고, insert와 scan의 경계가 지나간 것을 lock으로 확인한 뒤 삭제 표시를 한다. element version을 올리는 것은 iterative scan이 이전 iteration에서 읽은 neighbor tuple을 새 tuple로 오인하지 않게 하기 위해서다.

pgvector 문서는 HNSW vacuum이 오래 걸릴 수 있어 필요 시 REINDEX INDEX CONCURRENTLY 뒤 VACUUM하는 경로를 안내한다. 이것을 모든 시스템에 자동 적용할 규칙으로 받아들이기보다 실제 index bloat, maintenance window, write load를 측정해야 한다.

MVCC snapshot과 index candidate

HNSW element tuple의 heap TID는 table row의 물리 위치를 가리킨다. graph search가 TID를 찾았다고 그 row가 현재 transaction에 보인다는 뜻은 아니다. PostgreSQL executor는 heap tuple을 읽고 현재 MVCC snapshot에서 visible한지 확인한다.

pgvector의 hnswgettuple은 MVCC-compliant snapshot이 아니면 non-MVCC snapshots are not supported with hnsw 오류를 낸다. scan 중에는 vacuum이 방문 중인 element를 지우지 못하도록 scan lock을 shared로 잡고 initial candidate를 만든다. iterative resume에서도 같은 lock을 다시 잡는다.

dead 또는 현재 snapshot에서 invisible한 tuple은 최종 결과가 되지 않는다. 하지만 initial ANN budget 일부를 소모할 수 있다. pgvector 문서가 filtering뿐 아니라 dead tuple도 HNSW 결과 수를 줄일 수 있다고 설명하는 이유다.

WAL, crash recovery, replica

pgvector는 HNSW page 변경에 PostgreSQL Generic WAL record를 사용한다. regular insert와 vacuum의 page 변경은 GenericXLogStart, GenericXLogRegisterBuffer, GenericXLogFinish 경로로 기록된다.

initial build는 element마다 WAL을 남기지 않는다. hnswbuild.c는 graph build가 끝난 뒤 index page 전체를 WAL에 기록한다고 설명하고, BuildIndex는 logged relation이면 log_newpage_range를 호출한다. build 중의 WAL 양을 줄이되 완성된 index가 crash recovery와 physical replica에 재생되게 하는 경로다.

그래서 pgvector row와 index도 PostgreSQL transaction, crash recovery, physical replication, point-in-time recovery 체계 안에 들어간다. pgvector 공식 FAQ도 WAL을 사용하므로 replication과 PITR을 지원한다고 명시한다. 이것은 backup과 replica가 저절로 검증된다는 뜻은 아니다. extension binary/version 호환, base backup, WAL 보존, restore drill, replica query를 별도로 점검해야 한다.

patch version도 운영 정확성의 일부다

작성일 기준 최신 0.8.5를 택한 이유가 있다. 0.8.5 CHANGELOG를 보면 0.8.3은 HNSW vacuum 중 possible index corruption을, 0.8.4는 hnsw graph not repaired와 concurrent insert 관련 오류를 수정했다.

HNSW를 단순 read-only 계산 library처럼 보면 이런 patch를 놓친다. 실제로는 write, vacuum, concurrent scan, WAL이 얽힌 PostgreSQL index다. 도입 전에는 extension version만 기록하지 말고 해당 version의 vacuum·corruption fix와 upgrade rehearsal까지 확인해야 한다.

PostgreSQL은 HNSW를 어떻게 호출하는가

pgvector는 PostgreSQL index access method API를 구현한다.

CREATE ACCESS METHOD hnsw TYPE INDEX HANDLER hnswhandler;

0.8.5의 hnswhandler를 읽으면 filtered search의 제약이 드러난다.

amcanorderbyop = true   distance operator ORDER BY 지원
amcanmulticol = false   multi-column HNSW 아님
amcaninclude = false    INCLUDE column 지원 안 함
amgetbitmap = NULL      bitmap index scan 결과를 제공하지 않음

즉 다음과 같은 상상을 하면 안 된다.

-- 이런 복합 HNSW가 scalar metadata까지 graph traversal에 넣어 줄 것이라는 상상
USING hnsw (realm_id, module_id, embedding)

pgvector HNSW는 vector ordering용 단일-column access method다. 별도 B-tree metadata index와 HNSW 결과를 PostgreSQL이 BitmapAnd로 합치는 경로도 HNSW가 bitmap scan을 제공하지 않으므로 사용할 수 없다.

일반 B-tree 두 개는 bitmap으로 교집합을 만들 수 있지만, HNSW scan은 distance order와 조기 종료가 핵심이라 단순 bitmap 집합과 성질이 다르다.

SQL의 작성 순서와 실행 순서는 다르다

다시 원래 SQL을 보자.

WHERE realm_id = :realm_id
  AND module_id = :module_id
ORDER BY embedding <=> :query_vector
LIMIT 20;

SQL은 선언형이다. “이 결과를 달라”고 쓰지 “첫 줄을 먼저 실행하고 다음 줄을 실행하라”고 쓰지 않는다. PostgreSQL planner는 같은 결과를 낼 것으로 판단한 여러 physical plan 중 cost가 낮은 경로를 고른다.

exact plan이라면 metadata index 또는 seq scan으로 filter한 뒤 distance sort를 할 수 있다.

Limit
  └─ Sort by cosine distance
       └─ Bitmap/Index/Seq Scan
            Index Cond or Filter: metadata predicates

HNSW plan은 보통 개념적으로 다음과 같다.

Limit
  └─ HNSW Index Scan ordered by embedding <=> query
       Filter: realm/module/approval/plant/date/ACL
       Rows Removed by Filter: ...

Filter가 Index Scan node 아래에 출력돼도 graph가 그 조건으로 사전에 잘렸다는 뜻은 아니다. index access method가 vector order로 heap TID를 내놓고, executor가 row를 가져와 일반 qual을 검사한 것이다. PostgreSQL의 EXPLAIN 문서는 Index Cond와 Filter를 구분하고, filter는 scan한 row 중 조건을 통과한 것만 내보낸다고 설명한다.

pgvector 공식 문서가 “approximate index에서는 filtering이 index scan 뒤 적용된다”고 쓰는 이유가 이것이다.

왜 filter 뒤 ANN이 recall을 떨어뜨리는가

이제 숫자로 보자.

예시 1. 결과 수가 모자란다

전체 100만 청크 중 현재 사용자가 볼 수 있는 청크가 10%, 즉 selectivity $s=0.1$ 이라고 하자.

HNSW가 초기 후보 40개를 내고 metadata가 vector distance와 독립적이라고 아주 단순하게 가정하면 surviving row의 기대값은 다음이다.

E[|A \cap F|] = 40 \times 0.1 = 4

그래서 LIMIT 20이어도 평균 4행 정도만 남는다. pgvector 문서도 default hnsw.ef_search=40과 10% filter에서 같은 예를 든다.

20행을 채우기 위한 1차 candidate budget은 대략 다음처럼 생각할 수 있다.

B \approx \frac{k}{s}

k = 20, s = 10%   → B ≈ 200
k = 20, s = 1%    → B ≈ 2,000
k = 20, s = 0.1%  → B ≈ 20,000

하지만 이 식은 출발점일 뿐 보장이 아니다.

metadata와 vector neighborhood는 독립이 아닐 수 있다.
HNSW의 ef_search는 그대로 반환 후보 수나 방문 tuple 수와 같지 않다.
dead tuple과 NULL/zero vector가 있다.
HNSW 자체의 ANN miss가 있다.
여러 filter의 결합 selectivity 추정이 틀릴 수 있다.

예시 2. 20개를 채워도 진짜 filtered top-20을 놓친다

더 중요한 문제다.

query 근처의 전체 순위가 다음과 같다고 하자.

global distance rank 1~180  : 다른 realm 또는 권한 없음
global distance rank 181   : 허용 문서 A, filtered rank 1
global distance rank 195   : 허용 문서 B, filtered rank 2
global distance rank 240   : 허용 문서 C, filtered rank 3
...

전체 graph에서 40개만 후보로 만들면 허용 문서 A조차 후보에 없다. 그 뒤 WHERE를 아무리 정확히 적용해도 A를 복구할 수 없다.

먼저 잃어버린 row는 나중 filter가 되살릴 수 없다.

candidate를 400개로 늘려 20행을 채웠더라도 HNSW가 graph traversal 중 허용 문서 몇 개로 가는 경로를 탐색하지 않았다면 filtered exact top-20과 다를 수 있다. 결과 cardinality를 채운 것과 recall이 높은 것은 다르다.

두 종류의 손실을 분리해야 한다

filtered HNSW의 손실은 최소 두 층이다.

1. ANN loss
   graph 일부만 탐색해 전체 candidate 자체가 exact global neighbor와 다름

2. post-filter loss
   찾은 candidate 중 권한·공장·버전 조건 불일치 row가 제거됨

두 손실이 결합되면 다음 현상이 나온다.

LIMIT 20보다 적은 행 반환
20행은 채웠지만 eligible exact top-20과 overlap이 낮음
filter가 좁은 tenant/role에서만 품질 급락
ef_search를 고정했는데 corpus 성장과 함께 품질 하락
권한이 넓은 관리자와 좁은 현장 작업자의 검색 품질이 다름

이 문제는 보안 누출과 같은 말은 아니다

SQL WHERE 또는 RLS가 DB 안에서 올바르게 적용됐다면 권한 없는 row는 최종 result로 반환되지 않는다. 이 문제의 직접 효과는 주로 검색 누락과 부족한 결과 수다.

다만 권한 검사를 DB 밖에서, 이미 검색한 원문을 애플리케이션으로 가져온 뒤 수행하면 그 시점에는 원문이 신뢰 경계를 넘었으므로 별도 보안 문제다. mandatory authorization은 SQL WHERE나 PostgreSQL RLS처럼 DB result 전에 적용해야 한다.

PostgreSQL Row-Level Security 문서는 policy expression이 허용한 row만 일반 query가 처리하게 한다. table owner와 BYPASSRLS role은 예외가 있으므로 애플리케이션 connection role도 함께 검증해야 한다.

ACL 함수 placeholder는 아직 실제 설계가 아니다

질문의 acl_allows(:role)은 설명용 placeholder로는 괜찮지만 구현 계약이 빠져 있다.

최소한 다음을 답해야 한다.

함수가 현재 row의 ACL column을 읽는가?
사용자 ID, group, role, document ACL 중 무엇을 검사하는가?
함수 안에서 다른 table을 조회하는가?
RLS와 중복되는가, 대체하는가?
NULL일 때 deny인가?
function volatility와 privilege는 어떻게 설정했는가?
SECURITY DEFINER라면 search_path와 owner privilege가 안전한가?
권한 변경과 query snapshot 사이 일관성은 무엇인가?

성능 관점에서도 row마다 복잡한 ACL function을 호출하면 filter cost가 커지고 planner가 selectivity를 잘 추정하기 어렵다. 보안과 indexability를 위해 가능한 경우 현재 row column과 session identity로 표현되는 단순 RLS predicate가 유리하다. 실제 ACL model을 보지 않고 function이나 index를 단정해서는 안 된다.

pgvector 0.8.0 이후 iterative scan이 하는 일

pgvector는 post-filter로 결과가 부족해지는 문제를 줄이기 위해 0.8.0부터 iterative index scan을 제공한다.

BEGIN;
SET LOCAL hnsw.iterative_scan = strict_order;
SET LOCAL hnsw.ef_search = 100;

SELECT id, content, embedding <=> :query_vector AS distance
FROM document_chunks
WHERE realm_id = :realm_id
  AND module_id = :module_id
  AND approval_status = 'APPROVED'
  AND :plant_id = ANY(plant_scope)
  AND valid_from <= :today
  AND (valid_to IS NULL OR valid_to >= :today)
  AND acl_allows(:role)
ORDER BY embedding <=> :query_vector
LIMIT 20;

COMMIT;

iterative scan은 executor가 filter를 통과한 row를 충분히 받지 못해 HNSW index에 다음 tuple을 요구하면, initial search에서 버렸던 candidate를 시작점으로 layer 0 search를 재개한다.

소스에서 확인한 흐름은 다음과 같다.

initial layer 0 search가 ef_search 폭으로 결과를 만든다.
iterative mode가 켜져 있으면 탈락 후보를 discarded priority queue에 보관한다.
현재 result list가 비면 ResumeScanItems가 ef_search 크기의 다음 batch를 꺼낸다.
그 후보들에서 graph search를 이어 간다.
hnsw.max_scan_tuples 또는 memory limit에 닿으면 더 넓은 탐색을 중단한다.

직접 확인한 코드는 hnswscan.c 58~87행과 249~326행에 있다.

strict_order

SET hnsw.iterative_scan = strict_order;

반환 distance 순서를 엄격히 유지한다. 다음 batch에서 이전에 반환한 distance보다 더 가까운 candidate가 뒤늦게 나오면 strict ordering을 깨므로 그대로 반환할 수 없다. ordering 보장 때문에 더 좋은 candidate를 활용하지 못하는 경우가 생겨 relaxed mode보다 recall이 낮을 수 있다.

relaxed_order

SET hnsw.iterative_scan = relaxed_order;

조금 어긋난 distance order를 허용해 더 많은 결과와 recall을 얻는다. 최종 strict order가 필요하면 공식 문서의 materialized CTE pattern을 쓴다.

WITH relaxed_results AS MATERIALIZED (
    SELECT
        id,
        content,
        embedding <=> :query_vector AS distance
    FROM document_chunks
    WHERE realm_id = :realm_id
      AND module_id = :module_id
      AND approval_status = 'APPROVED'
    ORDER BY embedding <=> :query_vector
    LIMIT 100
)
SELECT *
FROM relaxed_results
ORDER BY distance + 0
LIMIT 20;

PostgreSQL 17 이상에서는 이 pattern에 + 0이 필요하다고 pgvector 0.8.5 문서가 명시한다.

iterative scan의 중단 조건

SET hnsw.max_scan_tuples = 20000;
SET hnsw.scan_mem_multiplier = 2;

hnsw.max_scan_tuples — iterative phase에서 방문할 tuple의 근사 상한. 기본 20,000. initial scan에는 적용되지 않는다.
hnsw.scan_mem_multiplier — iterative scan memory limit을 work_mem의 몇 배로 둘지 정한다. 기본 1.

max_scan_tuples만 올려도 recall이 늘지 않는다면 memory limit에 먼저 닿았을 수 있다. 그렇다고 둘을 무조건 크게 두면 동시 query 수만큼 memory와 CPU 비용이 커진다.

iterative scan은 filter-aware HNSW graph로 바꾸는 기능이 아니다. 같은 전역 graph를 더 오래 탐색해 post-filter 생존자를 더 찾는 기능이다. filter selectivity가 극단적으로 낮다면 exact prefilter나 physical partitioning보다 비쌀 수 있다.

성능과 트레이드오프를 결정하는 HNSW parameter

설정	적용 시점	바꾸는 것	올렸을 때 주 비용
`m`	index build	node당 graph 연결 수	index size, build, insert, traversal fan-out
`ef_construction`	index build·insert	좋은 이웃을 찾는 후보 폭	build time, insert time
`ef_search`	query	initial layer 0 탐색 폭	query latency, CPU, I/O, memory
`max_scan_tuples`	iterative query	추가 탐색 상한	worst-case query work
`scan_mem_multiplier`	iterative query	추가 탐색 memory 상한	per-query memory

중요한 관계는 다음이다.

낮은 ef_construction으로 graph 자체의 좋은 edge가 빠지면 query의 ef_search만 올려도 한계가 있다.
m을 올리면 경로는 풍부해지지만 모든 query의 neighbor expansion 비용이 커진다.
ef_search는 session GUC라 query 유형별 조정이 쉽다.
m, ef_construction은 index reloption이라 바꾸려면 새 index build가 필요하다.

기본값을 출발점으로 두고 실제 corpus에서 recall-latency curve를 그려야 한다. parameter 이름만 보고 큰 값을 정하는 것은 tuning이 아니다.

Big-O 한 줄로 HNSW를 설명하면 틀리는 이유

먼저 기호를 고정한다.

$N$ 은 index에 들어간 vector 개수다.
$d$ 는 vector 차원 수다.
$M$ 은 HNSW node의 목표 연결 수다. pgvector 설정 이름은 m이다.
$ef$ 는 한 번의 search에서 유지하고 확장하는 후보 폭이다. build에서는 ef_construction, query에서는 ef_search가 이 역할을 한다.
$V$ 는 한 query에서 실제로 distance를 계산한 서로 다른 node 수다.

두 dense vector의 L2, inner product, cosine distance를 계산하려면 일반적으로 $d$ 개 좌표를 읽어야 한다. 거리 계산 한 번의 시간은 $O(d)$ 이고, index 없는 exact search는 모든 row를 비교하므로 $O(Nd)$ 다. 이 식은 정렬 비용을 별도로 뺀 거리 계산 하한에 가깝다. top-k heap 관리와 heap tuple fetch 같은 PostgreSQL 비용도 추가된다.

HNSW는 $N$ 대신 **실제로 방문한 node 수 $V$ **만큼 거리를 계산한다. 따라서 query 비용을 가장 정직하게 보는 식은 다음과 같다.

T_{query} \approx O(Vd) + \text{graph page I/O} + \text{heap tuple fetch}

원 논문은 skip-list와 navigable small-world graph의 성질을 이용해 적절한 분포와 graph 품질 아래 평균 search가 로그 수준으로 확장될 수 있음을 설명한다. 그러나 이것은 모든 dataset에 대한 엄격한 최악 시간 $O(\log N)$ 보장이 아니다. 실제 $V$ 는 다음 항목에 따라 크게 달라진다.

데이터의 intrinsic dimension — 좌표 차원 $d$ 가 같아도 점들이 사실상 몇 개 독립 방향에 퍼졌는지가 다르다. 가까운 점과 먼 점의 구분이 약해지는 high-dimensional corpus는 더 많은 방문을 요구할 수 있다.
graph 품질 — 작은 m과 ef_construction, 편향된 삽입 순서, 변경과 삭제가 누적된 graph는 좋은 shortcut이 부족할 수 있다.
query 폭 — ef_search와 iterative scan 상한이 커질수록 $V$ 가 증가한다.
cache와 page locality — vector와 edge가 여러 index page에 흩어지면 동일한 $V$ 라도 cold cache random I/O가 latency를 지배한다.
filter selectivity — 생존 비율이 $s$ 라면 단순 독립 가정 아래 $k$ 개 생존자를 얻기 위해 대략 $k/s$ 개 후보가 필요하다. 권한과 embedding 위치가 상관되면 이 근사도 깨진다.

예를 들어 $k=20$ , $s=0.01$ 이면 단순 기대값만 2,000 candidates다. initial ef_search=40으로 충분할 수 없다. iterative scan은 부족한 후보를 더 찾으므로 recall을 복구할 수 있지만, 선택도가 낮은 query의 $V$ 와 tail latency가 커진다. 이것이 filtered ANN에서 recall과 latency가 직접 교환되는 근원이다.

build도 무조건적인 $O(N \log N)$ 이라고 외우면 안 된다. 원 논문은 고정된 construction parameter와 navigability 가정 아래 logarithmic scaling을 설명하지만, 새 node 하나마다 여러 layer에서 후보를 탐색하고 최대 $M$ 또는 $2M$ 개 이웃을 고르고 상호 edge를 갱신한다. 실제 비용은 $N$ , $d$ , m, ef_construction, WAL, cache와 graph 분포의 함수다. ef_construction을 두 배로 했다고 build가 정확히 두 배가 된다는 보장도 없다.

공간은 vector payload와 graph를 함께 계산해야 한다.

S_{index} = O(Nd) + O(NM) + \text{tuple, TID, page overhead}

pgvector HNSW가 원본 vector value를 element tuple에 보관하고 neighbor tuple에 edge 정보를 보관하기 때문에 vector payload $O(Nd)$ 가 사라지지 않는다. layer 0의 연결 한도는 2 * m, 위 layer는 m이고, 높은 layer에 속하는 node 수는 지수적으로 줄어든다. 그래서 $O(NM)$ 은 방향을 이해하기 위한 근사이지 실제 byte 수 공식이 아니다. 실제 크기는 pg_relation_size로 측정하고 build 전후 table·index 크기와 cache hit ratio를 함께 봐야 한다.

결론적으로 HNSW의 장점은 이론 표기 하나가 아니라 좋은 graph에서 $V \ll N$ 을 만들 가능성이다. graph나 데이터가 나쁘고 높은 recall, 강한 filter까지 요구하면 $V$ 가 $N$ 에 가까워질 수 있으며, 이때 exact scan과 비슷한 일을 더 복잡한 I/O pattern으로 수행할 수도 있다. 그러므로 production 판단은 $O(\log N)$ 문구가 아니라 실제 corpus의 distance-computation 수, index page read, recall@k, p95·p99 latency로 해야 한다. 원 논문의 복잡도 논의와 알고리즘은 HNSW 논문 4절과 Algorithm 1~5에서, pgvector의 실제 page 구조와 search loop는 hnsw.h와 HnswSearchLayer에서 다시 확인할 수 있다.

대안 비교와 선택 기준

한 전략을 모든 filter selectivity에 적용하면 비효율이 생긴다. 아래는 선택 가능한 설계다. 실제 table definition, row count, 분포, 기존 index를 확인하지 않았으므로 특정 index를 채택하라는 결론은 아니다.

전략 A. 좁은 허용 집합은 metadata prefilter 후 exact search

filter를 통과한 row가 수백~수천 개라면 HNSW로 전체 graph를 헤매는 것보다 정확히 거리 계산하는 편이 나을 수 있다.

WITH eligible AS MATERIALIZED (
    SELECT id, content, embedding
    FROM document_chunks
    WHERE realm_id = :realm_id
      AND module_id = :module_id
      AND approval_status = 'APPROVED'
      AND :plant_id = ANY(plant_scope)
      AND valid_from <= :today
      AND (valid_to IS NULL OR valid_to >= :today)
      AND acl_allows(:role)
)
SELECT id, content, embedding <=> :query_vector AS distance
FROM eligible
ORDER BY embedding <=> :query_vector
LIMIT 20;

여기서 MATERIALIZED는 eligible 결과를 별도 단계로 만들겠다는 의도를 분명히 한다. 그래도 실제 plan과 비용은 반드시 확인해야 한다. CTE materialization 자체의 write/read overhead도 있다.

metadata index 후보는 실제 \d, pg_indexes, column 통계, query 빈도, EXPLAIN을 본 뒤 정해야 한다. 특히 :plant_id = ANY(plant_scope)는 array membership이고, 날짜 범위와 ACL은 단순 equality가 아니므로 “복합 B-tree 하나면 끝”이라고 말할 수 없다.

전략 B. filter가 넓으면 HNSW + iterative scan

허용 비율이 높고 eligible row도 매우 많다면 전역 HNSW가 유리할 수 있다.

BEGIN;
SET LOCAL hnsw.ef_search = 200;
SET LOCAL hnsw.iterative_scan = relaxed_order;
SET LOCAL hnsw.max_scan_tuples = 50000;

WITH candidates AS MATERIALIZED (
    SELECT
        id,
        content,
        embedding <=> :query_vector AS distance
    FROM document_chunks
    WHERE realm_id = :realm_id
      AND module_id = :module_id
      AND approval_status = 'APPROVED'
      AND :plant_id = ANY(plant_scope)
      AND valid_from <= :today
      AND (valid_to IS NULL OR valid_to >= :today)
      AND acl_allows(:role)
    ORDER BY embedding <=> :query_vector
    LIMIT 100
)
SELECT *
FROM candidates
ORDER BY distance + 0
LIMIT 20;

COMMIT;

100, 200, 50000은 예시일 뿐 권장값이 아니다. query selectivity bucket별 recall과 p95 latency로 정해야 한다.

전략 C. 항상 같은 작은 subset이면 partial HNSW

예를 들어 거의 모든 검색이 approval_status='APPROVED'만 대상으로 하고 이 predicate가 안정적이라면 partial index가 graph 자체에서 비승인 row를 제외한다.

CREATE INDEX CONCURRENTLY chunks_approved_embedding_hnsw_cosine
ON document_chunks
USING hnsw (embedding vector_cosine_ops)
WHERE approval_status = 'APPROVED';

그러면 이 index의 $D$ 자체가 approved subset이다. post-filter 경쟁자가 줄어든다.

하지만 partial index는 query의 WHERE가 index predicate를 함의한다는 것을 planning time에 PostgreSQL이 증명할 수 있어야 한다. PostgreSQL partial index 문서는 일반적인 parameterized clause가 partial predicate를 모든 값에 대해 함의하지 않으므로 작동하지 않는다고 명시한다.

WHERE approval_status = 'APPROVED'  → 고정 predicate partial index에 적합할 수 있음
WHERE realm_id = :realm_id          → realm마다 partial index를 늘리는 방식은 부적합할 수 있음

서로 겹치지 않는 partial index를 realm 수만큼 만드는 것은 partitioning 대용이 아니다. PostgreSQL 문서도 많은 partial index 집합 대신 partitioning을 검토하라고 경고한다.

전략 D. 검색 경계가 명확하면 partitioning

tenant 또는 realm이 query마다 항상 equality로 주어지고 각 partition이 충분히 크다면 list/hash partitioning을 검토할 수 있다.

CREATE TABLE document_chunks (
    realm_id bigint NOT NULL,
    id bigint NOT NULL,
    embedding vector(1024) NOT NULL,
    content text NOT NULL
) PARTITION BY LIST (realm_id);

각 child partition에 HNSW index가 생기면 partition pruning으로 다른 realm graph를 검색 대상에서 제외할 수 있다.

전역 graph D
  → realm partition의 local graph D_realm
  → 그 안에서 HNSW

이것은 filter를 graph traversal 전에 물리적으로 줄이는 방식이다. 하지만 partition 수, 작은 partition, cross-realm query, DDL 운영, autovacuum, index build, connection concurrency 비용이 생긴다. PostgreSQL partitioning 문서의 pruning 조건과 운영 비용을 같이 봐야 한다.

전략 E. 애플리케이션 adaptive routing

query마다 예상 eligible cardinality가 크게 다르면 search path를 나눌 수 있다.

eligible count가 작음
  → metadata prefilter + exact

eligible count가 큼, selectivity 높음
  → HNSW 기본/중간 ef_search

eligible count가 큼, selectivity 낮음
  → HNSW iterative + 큰 candidate budget
     또는 partition/local index 재검토

여기서 count query를 매번 먼저 실행하면 그 자체가 latency가 된다. PostgreSQL statistics, cached policy group size, coarse routing table 등으로 추정할 수 있지만 오차를 관측해야 한다.

권한 filter와 relevance filter를 같은 것으로 보지 않기

검색 조건에는 성격이 다른 두 종류가 있다.

Mandatory filter

tenant/realm isolation
ACL/RLS
승인 상태
법적 유효기간
삭제 여부

틀리면 보안 또는 업무 정합성 문제다. reranker가 고칠 문제가 아니다.

Relevance preference

같은 공장 문서를 우선
최신 문서를 가산
특정 문서 유형 boost

후보에 포함한 뒤 score나 reranker로 조정할 수 있다.

예를 들어 plant_id가 반드시 접근 가능한 공장 경계라면 WHERE다. 여러 공장 문서를 볼 수 있지만 현재 공장을 우선하고 싶다는 뜻이면 hard filter가 아니라 ranking feature일 수 있다. 이 요구를 구분하지 않으면 filter selectivity를 불필요하게 낮추고 recall도 떨어뜨린다.

Lexical/Dense 검색 순서도 같은 원리다

처음 설명은 다음이었다.

전체 문서
→ 권한·공장·버전·유효기간으로 검색 공간 제한
→ 제한된 공간에서 Lexical/Dense 검색

이것은 보장해야 할 논리 의미다. 각 retrieval engine의 물리 실행이 자동으로 그 순서라는 뜻은 아니다.

PostgreSQL full-text search는 GIN/GiST, filter index, bitmap plan을 조합할 수 있다.
pgvector HNSW는 vector order를 따라 graph를 탐색하고 scalar filter를 post-filter할 수 있다.
별도 search engine의 filtered ANN은 engine마다 pre-filter, post-filter, in-traversal filter 구현이 다르다.

따라서 hybrid search에서는 두 candidate source를 각각 평가해야 한다.

Lexical candidate recall under ACL
Dense candidate recall under ACL
Union recall
Reranker nDCG/MRR
최종 answer citation correctness

Dense에서 filter 때문에 정답이 candidate에 없는데 lexical과 reranker만 조정해서는 근본 문제가 해결되지 않는다.

HNSW index가 실제로 사용되려면 SQL 모양도 맞아야 한다

pgvector 0.8.5 문서는 ORDER BY가 distance operator 결과 자체이고 ascending이며 LIMIT이 있어야 HNSW index 경로를 사용할 수 있다고 설명한다.

-- index 사용 가능한 모양
ORDER BY embedding <=> :query_vector
LIMIT 20;

다음은 cosine similarity를 계산했지만 HNSW distance ordering 모양과 다르다.

-- 이 형태는 같은 HNSW index ordering으로 인식되지 않음
ORDER BY 1 - (embedding <=> :query_vector) DESC
LIMIT 20;

select list에서 similarity로 보여 주고 싶다면 ordering expression은 index가 인식할 수 있는 distance operator로 유지한다.

SELECT
    id,
    1 - (embedding <=> :query_vector) AS cosine_similarity
FROM document_chunks
WHERE ...
ORDER BY embedding <=> :query_vector
LIMIT 20;

직접 검증과 재현 실험

문서의 10%만 filter를 통과할 때 default ef_search=40이 정말 4행만 남기는지 로컬 Docker에서 재현했다.

실행 환경

Apple Silicon macOS
Docker 29.4.0
image pgvector/pgvector:0.8.5-pg18
PostgreSQL 18.4
pgvector 0.8.5

실험용 container는 host port를 열지 않았다. 다른 PostgreSQL이나 회사 DB는 사용하지 않았다.

docker run -d \
  --name techlog-pgvector-hnsw-repro \
  -e POSTGRES_PASSWORD=local-repro-only \
  pgvector/pgvector:0.8.5-pg18

데이터와 통제 조건

10,000개의 3차원 vector를 직선 위에 놓았다.

id 1     → [1, 0, 0]
id 2     → [2, 0, 0]
...
id 10000 → [10000, 0, 0]

query는 [0,0,0]이다. L2 distance는 정확히 id와 같아 정답 순서를 눈으로 검산할 수 있다. id % 10 = 0인 행만 allowed=true로 두었으므로 filter selectivity는 정확히 10%다.

아래 전체 SQL을 실행했다.

cat <<'SQL' | docker exec -i techlog-pgvector-hnsw-repro \
  psql -U postgres -v ON_ERROR_STOP=1
\pset pager off

SELECT current_setting('server_version') AS postgres_version;
CREATE EXTENSION vector;
SELECT extversion AS pgvector_version
FROM pg_extension
WHERE extname = 'vector';

CREATE TABLE filtered_items (
    id integer PRIMARY KEY,
    allowed boolean NOT NULL,
    embedding vector(3) NOT NULL
);

INSERT INTO filtered_items (id, allowed, embedding)
SELECT
    g,
    g % 10 = 0,
    format('[%s,0,0]', g)::vector
FROM generate_series(1, 10000) AS g;

CREATE INDEX filtered_items_embedding_hnsw
ON filtered_items
USING hnsw (embedding vector_l2_ops)
WITH (m = 16, ef_construction = 64);

ANALYZE filtered_items;

-- 같은 filter 안의 exact ground truth
BEGIN;
SET LOCAL enable_indexscan = off;
SET LOCAL enable_bitmapscan = off;

SELECT array_agg(id ORDER BY distance) AS exact_ids
FROM (
    SELECT id, embedding <-> '[0,0,0]'::vector AS distance
    FROM filtered_items
    WHERE allowed
    ORDER BY embedding <-> '[0,0,0]'::vector
    LIMIT 20
) AS exact;
COMMIT;

-- HNSW initial scan 뒤 post-filter
-- enable_seqscan=off는 재현에서 HNSW plan을 고정하려는 용도다.
BEGIN;
SET LOCAL enable_seqscan = off;
SET LOCAL hnsw.ef_search = 40;
SET LOCAL hnsw.iterative_scan = off;

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, SUMMARY OFF)
SELECT id, embedding <-> '[0,0,0]'::vector AS distance
FROM filtered_items
WHERE allowed
ORDER BY embedding <-> '[0,0,0]'::vector
LIMIT 20;

SELECT count(*) AS result_count,
       array_agg(id ORDER BY distance) AS ann_ids
FROM (
    SELECT id, embedding <-> '[0,0,0]'::vector AS distance
    FROM filtered_items
    WHERE allowed
    ORDER BY embedding <-> '[0,0,0]'::vector
    LIMIT 20
) AS ann;
COMMIT;

-- 같은 ef_search에서 iterative scan만 활성화
BEGIN;
SET LOCAL enable_seqscan = off;
SET LOCAL hnsw.ef_search = 40;
SET LOCAL hnsw.iterative_scan = strict_order;

SELECT count(*) AS result_count,
       array_agg(id ORDER BY distance) AS iterative_ids
FROM (
    SELECT id, embedding <-> '[0,0,0]'::vector AS distance
    FROM filtered_items
    WHERE allowed
    ORDER BY embedding <-> '[0,0,0]'::vector
    LIMIT 20
) AS iterative;
COMMIT;
SQL

실제 관찰 결과

version query는 PostgreSQL 18.4와 pgvector 0.8.5를 반환했다. exact 결과는 예상대로 다음 20개였다.

{10,20,30,40,50,60,70,80,90,100,
 110,120,130,140,150,160,170,180,190,200}

iterative scan을 끈 HNSW plan은 다음이었다. 이 출력은 만든 예시가 아니라 위 명령의 실제 EXPLAIN ANALYZE 결과에서 cost와 planning detail만 줄인 것이다.

Limit (actual rows=4 loops=1)
  -> Index Scan using filtered_items_embedding_hnsw on filtered_items
       Order By: (embedding <-> '[0,0,0]'::vector)
       Filter: allowed
       Rows Removed by Filter: 36
       Index Searches: 1

결과도 4행뿐이었다.

result_count = 4
ann_ids      = {10,20,30,40}

HNSW가 initial result 40개를 냈고 executor filter가 allowed=false인 36개를 제거했다. LIMIT 20은 index가 더 줄 row가 없어 4행만 받고 끝났다.

FillRate@20 = 4 / 20 = 0.20
Recall@20   = 4 / 20 = 0.20

같은 ef_search=40에서 strict_order iterative scan을 켜자 20행이 채워졌고, 이 통제 데이터에서는 exact ID 20개와 모두 일치했다.

result_count  = 20
iterative_ids = {10,20,30,40,50,60,70,80,90,100,
                 110,120,130,140,150,160,170,180,190,200}

이 작은 실험은 일반적인 HNSW 성능 benchmark가 아니다. vector가 사실상 1차원이고 cache가 warm이며 동시 부하도 없다. 다만 Index Scan → Filter, Rows Removed by Filter=36, 4행 반환이라는 관찰로 post-filter가 LIMIT 결과를 비우는 실행 순서는 분리해서 확인했다.

실험 뒤에는 container를 중지했다.

docker stop techlog-pgvector-hnsw-repro

# 다시 쓰지 않을 때만 명시적으로 삭제
docker rm techlog-pgvector-hnsw-repro

실제 corpus에서 ground truth 만들기

parameter를 정하기 전에 실제 업무 filter로 ground truth를 만든다.

같은 filter로 exact top-k를 구한다

pgvector 공식 문서는 transaction 안에서 index scan을 꺼 exact 결과와 비교하는 방법을 제시한다.

BEGIN;
SET LOCAL enable_indexscan = off;

SELECT id, embedding <=> :query_vector AS distance
FROM document_chunks
WHERE realm_id = :realm_id
  AND module_id = :module_id
  AND approval_status = 'APPROVED'
  AND :plant_id = ANY(plant_scope)
  AND valid_from <= :today
  AND (valid_to IS NULL OR valid_to >= :today)
  AND acl_allows(:role)
ORDER BY embedding <=> :query_vector
LIMIT 20;

COMMIT;

운영 query에서 planner GUC를 영구 변경하면 안 된다. 실험 transaction의 SET LOCAL로 제한한다.

ANN 조건을 단계별로 바꾼다

ef_search:       40, 80, 160, 320, 640
iterative_scan:  off, strict_order, relaxed_order
filter bucket:   50%+, 10~50%, 1~10%, <1%
LIMIT:           10, 20, 50

최소 지표를 같이 기록한다

지표	이유
`Recall@20`	eligible exact top-20을 얼마나 찾았나
`FillRate@20`	20개를 채웠나
p50/p95/p99 latency	평균이 숨기는 tail cost 확인
rows removed by filter	post-filter waste 확인
buffers hit/read	cache와 disk 영향 확인
candidate count	oversampling 비용 확인
timeout/error rate	큰 iterative scan의 운영 위험 확인

EXPLAIN으로 physical plan을 본다

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT id, content
FROM document_chunks
WHERE ...
ORDER BY embedding <=> :query_vector
LIMIT 20;

확인할 것은 다음이다.

HNSW Index Scan인가, exact Seq/Bitmap/Index Scan + Sort인가
Filter와 Index Cond가 어디에 붙었나
Rows Removed by Filter가 얼마인가
actual rows가 LIMIT을 채웠나
planner estimated rows와 actual rows가 얼마나 다른가
buffer hit/read가 얼마인가

planner가 HNSW를 선택했다는 사실은 recall이 충분하다는 증거가 아니다. PostgreSQL cost model은 business relevance ground truth를 알지 못한다.

실패 방식과 운영 기준

corpus가 커지면 예전 parameter가 그대로 맞지 않는다

같은 ef_search=100이어도 node 수, cluster 구조, embedding model, 데이터 중복률, filter selectivity가 바뀌면 recall-latency curve가 바뀐다. index 도입 때 한 번 측정하고 끝낼 수 없다.

embedding model을 섞으면 거리의 의미가 무너진다

서로 다른 model/version에서 나온 vector는 차원이 같아도 같은 공간이라는 보장이 없다. embedding_model_id와 version을 저장하고 검색 공간을 분리해야 한다. 같은 column에 variable dimension을 저장할 수 있어도 HNSW index는 같은 dimension subset에 expression/partial index가 필요하다.

cosine HNSW의 zero vector

pgvector 문서는 NULL vector를 index하지 않고 cosine distance에서는 zero vector도 index하지 않는다고 명시한다. zero vector는 cosine denominator가 0이라 방향을 정의할 수 없다. ETL validation 없이 넣으면 “row는 table에 있는데 ANN 결과에는 없다”는 현상을 만들 수 있다.

index가 memory에 꼭 전부 들어가야 하는 것은 아니다

동작 자체는 가능하지만 graph traversal은 random page access가 많다. hot portion이 cache에 없으면 latency가 커질 수 있다.

SELECT pg_size_pretty(pg_relation_size('chunks_embedding_hnsw_cosine'));

index size, shared buffer hit, OS page cache, cold-start latency를 함께 본다.

build memory와 query memory는 다르다

maintenance_work_mem — initial HNSW graph build가 memory 안에 머무는 범위에 영향
work_mem * hnsw.scan_mem_multiplier — iterative query memory limit에 영향

maintenance_work_mem을 서버 RAM에 가깝게 올리면 다른 session과 OS를 굶길 수 있다. 공식 문서도 memory exhaustion을 경고한다.

production index build

일반 CREATE INDEX는 write를 막을 수 있다. pgvector 문서는 production에서 CREATE INDEX CONCURRENTLY를 권한다.

CREATE INDEX CONCURRENTLY chunks_embedding_hnsw_cosine
ON document_chunks
USING hnsw (embedding vector_cosine_ops);

concurrent build는 더 오래 걸리고 실패한 invalid index 정리 같은 운영 절차가 필요하다. migration에서는 lock, disk headroom, WAL/replica lag, rollback을 별도로 설계해야 한다.

자주 생기는 오해와 질문의 답

“WHERE를 ORDER BY보다 먼저 썼으니 pre-filter다”

아니다. SQL 문법 위치는 physical execution order를 강제하지 않는다. EXPLAIN과 index access method 능력을 봐야 한다.

“HNSW index와 B-tree index가 둘 다 있으니 자동으로 합쳐진다”

아니다. PostgreSQL은 bitmap을 제공하는 index끼리 BitmapAnd를 만들 수 있지만 pgvector 0.8.5 HNSW는 amgetbitmap=NULL이고 multi-column도 지원하지 않는다.

“LIMIT 20이면 HNSW도 정확히 20개만 찾는다”

아니다. HNSW 내부 search breadth는 ef_search이고, executor filter와 iterative scan에 따라 방문량과 반환량이 달라진다.

“결과가 20개면 recall 문제는 없다”

아니다. 20개를 채운 것과 eligible exact top-20을 찾은 것은 다르다.

“ef_search를 크게 하면 exact가 된다”

보장되지 않는다. 탐색 폭을 늘려 recall을 높일 수 있지만 graph quality, scan limit, memory limit, dead tuple, data topology 영향이 남는다. exact 보장이 필요하면 eligible set에서 exact distance를 계산한다.

“HNSW는 embedding을 압축한다”

기본 vector HNSW의 근사는 탐색 경로에 있다. halfvec, binary quantization, subvector indexing을 추가하면 representation approximation까지 더해진다. 두 종류의 근사를 분리해서 측정해야 한다.

“HNSW는 학습이 없으니 build가 싸다”

아니다. centroid training은 없지만 각 삽입에서 graph search, neighbor selection, bidirectional edge update가 필요하다. pgvector 문서도 IVFFlat보다 build가 느리고 memory를 더 쓴다고 설명한다.

“Recall은 model 성능 하나다”

아니다. 최종 retrieval recall에는 최소 다음이 곱쳐 있다.

embedding representation quality
chunking quality
distance metric 선택
ANN graph/build quality
query search breadth
metadata filter 실행 방식
candidate fusion
reranker

같은 embedding model도 exact search와 filtered HNSW에서 평가 순위가 달라질 수 있다.

질문의 SQL에 대한 최종 판단

원래 SQL의 보안·업무 조건을 query 안에 넣는 방향은 맞다.

WHERE realm_id = :realm_id
  AND module_id = :module_id
  AND approval_status = 'APPROVED'
  AND :plant_id = ANY(plant_scope)
  AND valid_from <= :today
  AND (valid_to IS NULL OR valid_to >= :today)
  AND acl_allows(:role)
ORDER BY embedding <=> :query_vector
LIMIT 20

그러나 이 SQL만 보고 다음 물리 실행을 보장한다고 말하면 틀린다.

전체 table
→ WHERE로 작은 허용 집합 확정
→ 그 집합만 HNSW 탐색

하나의 전역 pgvector HNSW index를 planner가 선택하면 실제 핵심은 다음일 수 있다.

전체 HNSW graph에서 ANN 탐색
→ 제한된 vector candidate/TID 반환
→ 일반 WHERE와 ACL로 제거
→ LIMIT을 채우거나 index scan이 끝날 때까지 진행

iterative scan이 꺼져 있으면 initial candidate가 소진된 뒤 적은 결과로 끝날 수 있다. 켜져 있으면 더 탐색하지만 scan tuple/memory 상한에서 멈춘다. filter가 극단적으로 좁으면 여전히 비싸거나 recall이 부족할 수 있다.

따라서 설계 질문은 “HNSW를 쓸까?”가 아니라 다음이어야 한다.

이 query의 eligible row 수와 selectivity는 얼마인가?
eligible exact top-20을 ground truth로 만들었는가?
현재 plan은 HNSW post-filter인가, metadata prefilter exact인가?
ef_search와 iterative mode별 recall-latency curve는 어떤가?
mandatory boundary를 partial index나 partition으로 graph 전에 줄일 수 있는가?
좁은 ACL에서는 exact path로 전환하는 것이 더 싼가?
결과 수와 recall을 따로 측정하는가?
SQL filter와 RLS가 권한 없는 원문이 DB 밖으로 나가기 전에 적용되는가?

내가 이제 이 문장을 읽는 방식

“pgvector HNSW에서는 필터와 ANN 실행 순서 때문에 recall이 줄 수 있다.”

이 문장을 이제 다음처럼 풀어 읽는다.

pgvector는 PostgreSQL에 vector type, distance operator, ANN index를 추가한다.

HNSW는 vector를 multi-layer proximity graph로 연결하고,
전체 vector를 보지 않은 채 일부 graph path만 탐색하는 ANN이다.

pgvector 0.8.5 HNSW는 scalar metadata를 함께 탐색하는 multi-column graph가 아니다.
따라서 전역 HNSW index scan이 먼저 제한된 vector candidate를 만들고,
PostgreSQL executor가 일반 WHERE 조건을 나중에 적용할 수 있다.

filter selectivity가 낮으면 candidate 대부분이 제거된다.
허용 집합 안의 진짜 nearest neighbor가 initial ANN candidate 밖에 있었다면
filter 뒤에는 복구할 방법이 없다.

그래서 반환 수와 Recall@k가 낮아진다.

해결은 무조건 ef_search를 키우는 것이 아니다.
iterative scan, exact prefilter, partial index, partitioning,
adaptive routing 중 데이터 분포와 보안 경계에 맞는 방식을 고르고
eligible exact ground truth로 검증해야 한다.

가장 중요한 근원은 한 줄이다.

filter(top-B of all)과 top-k within filtered set은 같은 연산이 아니다.

출처

1차 자료

pgvector. README v0.8.5. exact/approximate search, HNSW, filtering, iterative scan, monitoring 기준.
pgvector. CHANGELOG.md v0.8.5. 0.8.3~0.8.5의 HNSW vacuum·index corruption 수정 이력.
pgvector. src/vector.h v0.8.5. dense vector memory layout.
pgvector. sql/vector.sql v0.8.5. distance operator, access method, operator class 정의.
pgvector. src/hnsw.h v0.8.5. HNSW 기본값, layer 0 연결 수, level normalization.
pgvector. src/hnsw.h on-disk structures. meta/element/neighbor tuple 구조.
pgvector. src/hnswutils.c search layer. visited set과 candidate/result priority queue 탐색.
pgvector. src/hnswscan.c index scan. upper layer와 ground layer search, iterative resume.
pgvector. src/hnsw.c index access method handler. ordering, multi-column, INCLUDE, bitmap 지원 여부.
pgvector. src/ivfbuild.c IVFFlat build. sampling과 centroid 학습.
pgvector. src/ivfkmeans.c k-means. k-means++ 초기화와 Elkan k-means 구현.
pgvector. src/ivfscan.c IVFFlat scan. centroid routing과 probed list의 flat distance 계산.
pgvector. src/ivfinsert.c와 src/ivfvacuum.c. 기존 centroid를 사용한 insert와 VACUUM의 dead tuple 제거.
Yu. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. HNSW 원 논문.
PostgreSQL 18. Using EXPLAIN. physical plan, Index Cond, Filter 해석.
PostgreSQL 18. Indexes and ORDER BY. ORDER BY ... LIMIT과 index ordering.
PostgreSQL 18. Partial Indexes. predicate implication, parameterized clause 제약, partial index 남용 경고.
PostgreSQL 18. Table Partitioning. partition pruning과 물리 분할.
PostgreSQL 18. Row Security Policies. row visibility와 policy evaluation 경계.

보조 자료

핵심 동작 설명에는 다른 기술 블로그를 사용하지 않았다. 비유와 해석도 위 원 논문, 공식 문서, pgvector 0.8.5 source를 직접 대조해 작성했다.