[Elasticsearch] 벡터 검색 (kNN, Vector Search)

관련 포스트
https://blog.naver.com/sssang97/223790220320
Elasticsearch는 벡터 검색을 지원하는 대표적인 데이터베이스 중 하나다.
사실 원래 주 목적은 텍스트 검색이긴 한데, 어쩌다보니 Vector search 데이터베이스로도 이름을 꽤 날리게 되었다.

벡터검색은 Elasticsearch 8.0부터 지원된다.

벤치마크 기준으로 보면 전문 Vector Database들에 비해서는 처리량이나 기본 성능이 부족한 부분이 있긴 하지만, 비전문 Vector Database 중에서는 가장 뛰어나다는게 일반적인 인식인 것 같다.

kNN (k-nearest neighor)와 HNSW

Elasticsearch는 k-nearest neighor이라는 알고리즘에 기반해서 벡터 검색을 지원한다.
알고리즘 자체는 굉장히 오래된 녀석이다. 1951년에 처음 고안되었다.

https://www.ibm.com/kr-ko/think/topics/knn
기본적인 개념 자체는 단순하다.
특정 위치에서 가장 가까운 이웃 3개가 필요하다고 하면, 유클리드 거리 기반으로 조회를 하는 것이다.

물론 elasticsearch의 knn은 유클리드 거리 외에도 코사인과 dot product를 지원하기 때문에, 순수한 kNN이라고 하기는 어려울 수도 있을 것 같다.

아무튼 이건 개념적인 용어일 뿐이고, 실제 인덱스 구현은 HNSW 방법론을 통해 만들어져있다.

그럼 대강 사용해보면서 그 구조를 짚어보겠다.

인덱스 생성

벡터 검색용 인덱스를 만드는 것은 그리 어렵지 않다.

### 
PUT http://{{HOST}}:{{PORT}}/vector_index
Content-Type: application/json

{
    "settings": {},
    "mappings": {
        "properties": {
            "vector": {
                "type": "dense_vector",
                "dims": 256,
                "index": true,
                "similarity": "dot_product"
            }
        }
    }
}
###

타입을 "dense_vector"로 두고, 벡터의 길이("dims"), 유사도 방법을 정해주면 되는 것이다.
저러면 256 벡터에 대해서 dot product 유사도 처리를 해주는 벡터가 완성된다.

유사도 알고리즘

방금 저기서는 dot product를 사용했는데, 3가지의 기본적인 유사도 알고리즘을 지원한다.

1. l2_norm - 유클리드 거리
2. cosine - 코사인 유사도
3. dot_product - dot product

잘 모른다면, 각각에 대해서는 별도 문서를 참조하는 것을 권한다.
https://blog.naver.com/sssang97/223790220320

HNSW 인덱스 옵션

Elasticsearch의 벡터 구현 방법론은 HNSW 뿐이지만, 성능 요구사항이나 사용사례에 따라서 추가 조정을 할 부분은 있다.

이런 식으로 타입이나 노드의 개수 등을 미세조정할 수 있다.

"type"은 이런 것들이 있다.

1. hnsw
2. int8_hnsw - 기본값. 정확도를 희생해서 메모리 사용량을 4배까지 줄임
3. int4_hnsw - 정확도를 희생해서 메모리 사용량을 8배까지 줄임
4. bbq_hnsw - 정확도를 희생해서 메모리 사용량을 32배까지 줄임
5. flat
6. int8_flat
7. int4_flat
8. bbq_flat

flat이 붙는 녀석은 단순무식하게 정확한 kNN 검색을 수행하는 거라서, 오차가 없는 대신 매우 느리거나 리소스를 과다하게 소모할 수 있다.
hnsw이 오차가 있는 대신 성능을 보장할 수 있는 ANN 인덱스 설정이라서, 대개는 이것들을 기본으로 고려하는 것이 맞다.

"m"은 HNSW 그래프 구조에서 노드가 몇개의 이웃과 연결되는지를 정의한다.
이걸 늘리면 메모리 사용량이 늘어나는 대신 정확도가 향상된다. 기본값은 16이다.

"ef_construction"은 노드를 구성할때 탐지하는 후보의 개수다. 이게 커지면 인덱스 구성 시간이 느는 대신에 정확도가 향상된다. 기본값은 100이다.

보통 최적화를 할때는 type이나 "ef_construction"는 잘 건드리지 않고, 옵션 "m"을 적절히 조정하고 쿼리할때 후보 수를 적절히 주는 것에 주안점을 주게 된다.

데이터 넣고 검색해보기

데이터를 삽입하는 것은 기존 인덱스와 별로 다르지 않다.
dot product이니 일반화된 벡터 배열로 넣어주기만 하면 된다.

검색을 할때는 기존 인덱스와 좀 다르다.
knn 옵션을 통해 검색 요청을 정의하는데

이런 식으로 가져올 개수(k)과, 고려할 후보군(num_candicaties)를 지정해줘야 한다.
여기서는 사실 num_candidates가 좀 핵심이었다.

Elasticsearch는 알다시피 멀티 샤드로 구성될 수 있는 분산 데이터베이스다.
샤드가 2개 있고, 샤드당 각각 약 1000개의 데이터가 분산되어있다고 가정해보자.

그러면 이 경우에 어떤 식으로 가장 유사도가 높은 2개만 가져올 수 있을까?

러프하게 생각한다면, 샤드마다 유사도가 높은 2개를 가져온 다음에, 그걸 모아서 4개 중에서 다시 2개를 선별하는 식으로 처리할 수 있을 것이다.
근데 샤드마다 2개를 선택하기 전에, 후보군을 대략적으로 추리는 작업이 전처리로 들어간다. 여기에 관여하는 것이 num_candidates다.

https://www.elastic.co/search-labs/blog/vector-search-set-up-elasticsearch
num_candicaties이 100이라고 하면, 각 샤드마다 근사한 랭킹 기반으로 100개를 후보군으로 추린 다음에, 거기서 샤드별로 유사도가 높은 2개를 조회한다. 그리고 코디네이터가 최종적인 2개를 뽑아서 반환하는 것이다.

num_candicaties 값이 높을수록 후보군의 범위가 넓어지기 때문에 오차 발생 확률이 떨어진다는 장점이 있다. 당연히 대신 메모리 사용량이나 리소스 소모가 늘어난다.
하지만 일반적인 벤치마크에 의하면 num_candicaties 증가로 인한 리소스 소모량 대비 정확도 증가는 딱히.. 눈에 띄는 정도는 아니라고 한다. 통상적으로 k와 같거나 2배 정도로 잡는게 상식적인 것 같다.

그리고 k와 num_candicaties 옵션은 비교적 최근 버전인 Elasticsearch 8.12부터는 optional 값으로 바뀌었다.
문서에는 대충 써놨는데, num_candicaties를 미설정할 경우에는 k*1.5 값으로 처리된다.

참조
https://www.elastic.co/guide/en/elasticsearch/reference/current/dense-vector.html
https://www.elastic.co/search-labs/blog/vector-similarity-techniques-and-scoring
https://danawalab.github.io/elastic/2022/07/08/ES-Similarity-Search.html
https://www.elastic.co/docs/solutions/search/vector/knn
https://www.ibm.com/think/topics/knn
https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector
https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector
https://www.elastic.co/search-labs/blog/elasticsearch-knn-and-num-candidates-strategies

https://www.elastic.co/search-labs/blog/vector-search-set-up-elasticsearch
https://www.elastic.co/search-labs/blog/simplifying-knn-search
https://github.com/elastic/elasticsearch/pull/101209/files