Qdrant의 필터 적용 벡터 검색 방식: 페이로드 필터를 견디는 HNSW

벡터 검색은 필터를 추가하기 전까지는 쉽다. “비슷한 문서를 찾아줘”는 깔끔한 최근접 이웃 쿼리지만, “tenant = acme이고 lang = en인 비슷한 문서를 찾아줘”부터는 표준 인덱스인 HNSW가 조용히 무너지기 시작한다. 나는 Qdrant가 이 문제를 어떻게 처리하는지 **v1.18.2, 커밋 44ad62f**에서 읽었다. 답은 구체적인 두 가지 엔지니어링 조치다. 필터의 카디널리티를 추정해 검색 전략을 고르고, 필터링된 하위 그래프가 끊어지지 않도록 추가 그래프 링크를 만든다. 모든 주장은 코드의 해당 줄을 가리킨다.

삼십 초 만에 보는 HNSW

Qdrant의 벡터 인덱스는 HNSW, 즉 계층적 탐색 가능 스몰 월드 그래프다. 각 포인트에는 기하 분포에서 뽑은 임의의 최상위 레벨이 배정된다(-ln(u) * level_factor, graph_layers_builder.rs:391). 그래서 상위 레이어는 희소하고 레이어 0은 조밀하다. 쿼리는 맨 위에서 진입해 희소 레이어를 내려가며 탐욕적으로 단 하나의 최적 이웃으로 이동한 다음(graph_layers.rs:299), 기본 레이어에서 폭이 ef인 빔 검색을 수행한다. 고정 크기 큐에 최적의 ef개 후보를 유지하다가 탐색 경계의 후보가 ef번째 최적 후보보다 나을 수 없으면 멈춘다(graph_layers.rs:126). 이웃은 빌드 시점에 다양성 휴리스틱으로 선택한다. 후보가 포인트 자체보다 이미 선택된 이웃에 더 가까우면 버린다(links_container.rs:59). 노드당 링크는 m개로 제한된다(레이어 0에서는 m0 = 2m). 기본값은 m = 16, ef_construct = 100이다(types.rs:1414).

필터가 이것을 망가뜨리는 이유

이제 tenant = acme를 추가해보자. 나쁜 선택지가 두 개 있다. 사후 필터링: 일반 그래프 검색을 실행한 뒤 일치하지 않는 결과를 버린다. 하지만 포인트 중 acme가 1%뿐이라면 상위 ef개가 거의 모두 버려져 재현율이 무너진다. 사전 필터링: 먼저 일치하는 집합을 가져온다. 하지만 일치하는 id의 단순 목록으로는 그래프 구조를 활용할 수 없으므로 다시 스캔해야 한다. Qdrant는 어느 쪽도 기본값으로 받아들이지 않고 대신 결정을 내린다.

조치 1: 필터를 추정한 다음 전략을 고른다

검색하기 전에 Qdrant는 페이로드 인덱스에 *이 필터와 일치하는 포인트가 몇 개인가?*라고 묻는다. estimate_cardinality는 { min, exp, max } 범위를 반환한다(vector_index_impl.rs:114. 정확한 키워드 일치에서는 개수가 정확하다). 그런 다음 설정된 full_scan_threshold를 기준으로 분기한다.

추정 카디널리티	전략	이유
max < threshold	필터링된 집합의 정확 스캔	일치하는 포인트가 매우 적어서 무차별 대입이 그래프보다 낫다(:122)
min > threshold	필터 적용 HNSW 그래프 검색	그래프를 쓸 가치가 있을 만큼 충분한 포인트가 일치한다(:135)
임곗값 양쪽에 걸침	id 몇 개를 표본 추출해 확인	추정 범위가 너무 불분명해 결정할 수 없다(:152)

정확 스캔 분기는 전체 컬렉션을 훑지 않는다. 페이로드 인덱스의 포스팅에서 일치하는 id만 바로 가져와 점수를 계산한다(search.rs:293). 따라서 선택성이 매우 높은 필터(user_id = 42)는 작은 정확 검색이 되고, 느슨한 필터(대부분 영어인 말뭉치의 lang = en)는 그래프를 사용한다. full_scan_threshold(기본값 10,000, API에서는 KB 단위로 표현되고 내부에서 벡터 개수로 변환된다)는 두 전략 사이를 조절하는 다이얼이다.

조치 2: 필터링된 하위 그래프의 연결을 유지한다

그래프 분기에도 함정이 있다. HNSW를 검색하면서 acme 포인트만 받아들인다면 실제로 탐색하는 것은 필터가 유도한 하위 그래프다. 그런데 이 하위 그래프는 끊어질 수 있다. 두 acme 포인트 사이에 다른 acme 포인트를 통하는 경로가 없을 수 있기 때문이다. Qdrant는 주석에서 침투 이론을 직접 인용해 이유를 설명한다. “포인트 중 1/K만 남으면 무작위 그래프가 끊어지며, 여기서 K는 포인트당 평균 링크 수다”(build.rs:378). m ≈ 16이라면 포인트의 약 1/16 미만을 남기는 필터는 그래프를 산산이 끊을 위험이 있다.

Qdrant의 “필터링 가능한 HNSW”에서 핵심인 해법은 실제로 사용할 필터를 위해 빌드 시점에 추가 링크를 만드는 것이다. Qdrant는 인덱싱된 각 페이로드 필드에서 빈도가 높은 값을 순회한다. 그리고 각 값에 해당하는 포인트 블록마다 그 포인트로만 제한된 작은 HNSW를 별도로 만든다. BuildConditionChecker는 블록 구성원만 이웃으로 받아들인다(build_condition_checker.rs:11). 그런 다음 그 링크를 주 그래프에 병합한다(build.rs:523). 이제 acme 전용 하위 그래프는 자체 연결 조직을 갖는다. 별도의 링크 예산인 payload_m을 사용하고(types.rs:684), 무조건 비용을 치르지는 않는다. 이미 충분히 연결됐거나 끊어질 수 없을 만큼 큰 블록은 건너뛴다(build.rs:490). 비용은 분명하다. 링크가 많아지면 메모리를 더 쓰고 인덱싱도 오래 걸린다. 그래서 저장하는 모든 필드가 아니라 인덱싱된 페이로드 필드에만 이 작업을 적용한다.¹

조절값과 그 대가

네 가지 숫자가 재현율, 속도, 메모리의 균형을 결정한다.

• m (기본값 16) — 노드당 링크 수. 높을수록 재현율과 연결성이 좋아지고 메모리를 더 쓴다.
• ef_construct (기본값 100) — 빌드 시점의 빔 폭. 높을수록 그래프가 좋아지고 인덱싱은 느려진다.
• ef (검색 시점의 빔) — 높을수록 재현율이 좋아지고 쿼리는 느려진다.
• full_scan_threshold (기본값 약 10k) — 필터 적용 쿼리가 그래프에서 정확 스캔으로 전환되는 지점이다.
• payload_m — 필터링된 하위 그래프를 위한 추가 링크 예산으로, 빠른 필터 적용 검색을 위해 치르는 비용이다.

더 큰 지도에서 어디에 놓일까?

이것은 앞서 내가 해부한 임베딩 우선 코딩 에이전트(Continue) 뒤에 있는 검색 기반층이다. 그 아래에서는 정확히 이런 종류의 필터 적용 벡터 검색을 수행한다. 내가 벡터 데이터베이스를 나눌 때 사용할 축은 필터링을 얼마나 일급 요소로 다루는가다. 프로덕션에서 벡터 쿼리에는 거의 항상 필터가 따라오기 때문이다(테넌트, 언어, 권한 범위 등). 많은 시스템은 필터링을 후처리 단계로 덧붙이고 선택성이 높은 필터에서 조용히 재현율을 잃는다. Qdrant는 필터를 전략 선택과 인덱스 구조 모두의 일급 입력으로 다룬다. 다른 대안과 비교할 때 찾아봐야 할 설계의 특징이 바로 이것이다.

언제 이걸 선택할까?

벡터 검색에 필터를 적용하고 그 필터의 선택성이 높을 때 Qdrant를 선택하면 된다. 멀티테넌트 앱, 권한 범위가 적용된 RAG, 패싯 검색이 그 예다. 카디널리티 기반 전략과 페이로드 인식 링크는 단순한 HNSW가 성능 저하를 보이는 바로 그 경우를 위해 만들어졌다. 트레이드오프는 알고 들어가야 한다. 빠른 필터 적용 검색을 얻으려면 필터링하는 페이로드 필드를 인덱싱해야 하고, 추가 링크에는 메모리와 빌드 시간이 든다. 그러므로 저장하는 모든 필드가 아니라 실제로 쿼리하는 필드를 인덱싱해야 한다. 쿼리가 적당한 크기의 데이터셋을 대상으로 필터 없이 최근접 이웃을 찾는 것이라면 이 장치 대부분은 작동하지 않으며 더 단순한 인덱스로도 충분하다.

방법론과 범위

나는 **Qdrant v1.18.2의 커밋 44ad62f**를 읽었고, lib/segment/src/index/hnsw_index/와 이 인덱스가 의존하는 페이로드 인덱스에 초점을 맞췄다. 핵심 주장 세 가지, 즉 HNSW 그래프와 검색, 카디널리티 기반 전략 선택, 침투 이론을 근거로 삼은 빌드 시점의 페이로드 인식 링크는 각각 이 커밋에서 적대적 주장 검증을 거쳤고 확인됐다.

범위의 주의점을 명확히 밝힌다.

• full_scan_threshold는 공개 설정에서 KiloBytes 단위로 문서화돼 있지만 내부에서는 벡터 개수로 비교된다(인덱스를 열 때 변환된다). 기본값(10,000)을 인용했지만, API에서는 이 단위를 문자 그대로의 벡터 개수가 아니라 “크기 임곗값”으로 봐야 한다.
• Qdrant에는 일치하지 않는 이웃을 통과해 일치하는 이웃에 도달하는 ACORN 방식의 필터 적용 검색도 있다. 하지만 이것은 선택성에 따라 선택되어 별도로 디스패치되는 알고리즘이지 기본 필터 적용 경로가 아니므로, 위의 주 메커니즘에서는 제외했다.
• 나는 벤치마크가 아니라 인덱스를 읽었다. 재현율과 지연 시간 수치는 데이터와 ef에 따라 달라지며, 여기에는 성능 측정 결과가 없다.

Footnotes

1. 각주로 남길 만한 별개의 연결성 메커니즘이 하나 더 있다. 인덱스를 다시 빌드하는 동안 포인트가 삭제될 때 링크를 복구하는 “healer”(graph_layers_healer.rs)다. 이 메커니즘은 이웃이 사라진 생존 포인트를 다시 연결한다. 이는 시간이 지나며 발생하는 삭제에 관한 것이지 필터에 관한 것이 아니다. 위의 페이로드 m 링크가 필터의 핵심이다. ↩