Elasticsearch는 전통적인 키워드 검색(BM25)뿐 아니라, 벡터 기반 검색(Vector Search) 을 통해 의미 기반 검색을 지원한다.
이번 글에서는 Elasticsearch에서 사용하는 벡터 검색 방식과,그 핵심 알고리즘인 HNSW에 대해 간단히 정리해본다.
1. Elasticsearch의 Vector 검색과 kNN
Elasticsearch에서 dense_vector 필드를 사용해 벡터를 인덱싱하면, 벡터 간의 유사도를 기준으로 검색할 수 있다.
이때 사용하는 검색 방식은 흔히 kNN(k-Nearest Neighbors) 라고 부른다.
kNN이란?
-
하나의 벡터를 기준으로 가장 가까운 N개의 벡터(문서) 를 찾는 방법이다.
→ 즉, 벡터 공간에서 “거리”가 가장 짧은 문서들을 선택하는 방식이다.
2. 그런데 실제로는 ‘정확한’ kNN을 쓰지 않는다
이론적으로 kNN은 매우 단순하다.
모든 문서의 벡터와 쿼리 벡터를 하나하나 비교해서 가장 가까운 N개를 고르면 된다.
하지만 여기서 문제가 발생한다.
문제점
문서 수가 적을 때는 가능하지만, 문서 수가 수천만, 수억개가 되면 모든 벡터를 비교하는 것은 너무 느리다
이 방식은 흔히 Brute-force kNN(전수 조사) 이라고 부르며, 대규모 검색 시스템에서는 현실적으로 사용하기 어렵다.
3. 그래서 사용하는 것이 ANN (Approximate Nearest Neighbor)
이 문제를 해결하기 위해 Elasticsearch는 ANN(근사 최근접 이웃 검색) 방식을 사용한다.
ANN은 말 그대로,
“가장 정확한 최근접 이웃”이 아니라 “거의 가장 가까운 최근접 이웃”을 훨씬 빠르게 찾는 방법이다.
Elasticsearch에서 사용하는 대표적인 ANN 알고리즘이 바로 HNSW (Hierarchical Navigable Small World) 이다.
4. HNSW란 무엇인가?
HNSW는 그래프 기반 ANN 알고리즘이다.
벡터 하나를 노드(node)로 보고 서로 가까운 벡터들을 그래프의 간선(edge) 으로 연결한다.
검색 시에는 이 그래프를 따라 이동하며 가까운 벡터를 빠르게 찾아간다.
핵심은 “모든 벡터를 보지 않는다” 는 점이다.
5. HNSW를 직관적으로 이해하기
HNSW의 동작 방식은 지도를 보며 위치를 찾아가는 과정과 매우 유사하다.
예를 들어, 집 주소가 서울시 송파구 신천동 시그니엘이라고 가정해 보자.
대부분의 사람들이 한반도 전체 지도에서 집에 위치를 꼭 찍어 찾지는 않는다.
먼저 서울시 수준으로 범위를 좁힌다 -> 그다음 송파구 -> 그다음 신천동 -> 마지막으로 빌딩을 찾는다.
즉, 처음에는 넓은 범위에서 대략적인 위치를 찾고 점점 좁은 범위로 이동하며 최종 목적지에 도달한다
HNSW도 동일하다.
상위 레이어에서는 대략적인 위치를 빠르게 찾고 하위 레이어로 내려갈수록 점점 더 정확한 최근접 이웃을 찾는다
6. 그래서 성능이 왜 좋아질까?
이 방식의 장점은 명확하다.
모든 벡터를 비교하지 않고 극히 일부 벡터만 비교해도 최근접 이웃을 찾을 수 있다.
검색 속도는 압도적으로 빨라지고 대규모 벡터 검색이 가능해진다.
7. 정확도는 괜찮을까?
ANN은 전수 조사 기반의 kNN보다 이론적으로는 정확도가 떨어질 수 있다.
하지만 실제로는,적절한 파라미터 설정(m, ef_construction, num_candidates)을 사용하면 대부분의 경우 결과는 거의 동일하지만 성능은 상당히 개선된다.
그래서 실무에서는 정확한 kNN 대신 ANN(HNSW)을 더 효율적이다.
3줄요약
-
Elasticsearch의 벡터 검색은 개념적으로 kNN 기반이다. 하지만 대규모 환경에서는 전수 조사 kNN을 사용할 수 없다.
-
그래서 HNSW 기반 ANN 검색을 사용한다
-
HNSW는 그래프 + 계층 구조를 활용해 빠르고 효율적으로 최근접 이웃을 찾는다
