[Clickhouse] 벡터 검색 (Vector Search)

clickhouse는 자체적으로 벡터 검색을 위한 함수들을 제공한다.
물론 전문 벡터 DB들처럼 높은 읽기 처리량과 레이턴시 보장을 제공하는건 아니라서, 실시간 서비스용으로는 사용할 수 없다.

하지만 데이터셋이 엄청나게 크진 않고 기존 데이터셋이 clickhouse에 있다면, 실험-검증용으로 가볍게 쓰기에는 충분하다.

clickhouse는 인덱스를 쓰지 않는 정확한 벡터 검색과, 인덱스를 사용하는 오차 있는 벡터 검색을 제공한다.

벡터 유사도 함수와 정확한 벡터 검색

clickhouse는 함수의 형태로 유사도 연산을 제공한다. 따로 뭘 설치할 필요는 없다.

select 
cosineDistance(  
   [0.5736801028251648, 0.2516217529773712, -0.6825592517852783],
   [0.5636801028251648, 0.3516217529773712, -0.16825592517852783]
) as cosine, 
dotProduct(  
   [0.5736801028251648, 0.2516217529773712, -0.6825592517852783],
   [0.5636801028251648, 0.3516217529773712, -0.16825592517852783]
) as dot, 
L2Distance(  
   [1, 2, 3], 
   [2, 3, 4]
) as euclid

그냥 이렇게 벡터값 2개 넣으면 비교해주는 식이다.

정확한 벡터 검색을 수행하는 방법도, 저 유사도 함수를 가져다가 정렬에 붙이는 것에서 벗어나지 않는다.
간단하다.

create table default.vector_test (
  id String, -- uuidv7
	color String, -- Red, Blue, Yellow, Black, White, Green
	vector Array(Float) -- 256 vector
) 
Engine = MergeTree
Order by id

그냥 적당히 벡터 저장용 컬럼 추가한 다음에

INSERT INTO default.vector_test
SELECT 
    generateUUIDv7() as id,
    ['Red', 'Blue', 'Yellow', 'Black', 'White', 'Green'][toUInt8(rand() % 6) + 1] as color,
    arrayMap(x -> randNormal(0.5, 0.3), range(256)) as vector
FROM numbers(5000000)
SETTINGS max_insert_threads=4;

벡터 값 넣어주고

select * 
from 테이블
where ... 
order by 
L2Distance(  
   vector, 
   [2, 3, 4, ...]
) asc

이런 식으로, Distance 결과로 정렬을 걸면 된다. l2은 작을수록 가까우니 asc를 걸고, dot/cosine은 클수록 가까운 것이니 desc를 걸면 되겠다.

그럼 이런 식으로 동작한다. 풀스캔 기반이긴 하지만, clickhouse 자체가 워낙 이런 부분에 최적화가 잘 되어있다보니 인덱스 없이 돌아도 어지간한 사이즈에서는 충분히 빠르다.

정확한 검색의 문제

저 정확한 검색의 단점은, 데이터 크기가 비대해질수록 성능 부하가 막심해진다는 것이다. 항상 풀스캔해서 모든 데이터에 대해 벡터연산을 수행하기 때문이다.
그래서 이런 방식은 하드웨어가 아무리 좋더라도 규모 확장에 따라 한계에 부딪히게 된다.

내 경우에도 100-500만개 정도에서는 수월하게 잘 돌았지만, 2000만개쯤 되니 거의 10초 가까이 걸렸다.

벡터 인덱스와 근사치 검색

다행히 clickhouse는 HNSW 벡터 인덱스 기반의 근사치 검색 또한 제공한다.
완전히 일치하지는 않지만, 그 대가로 빠르고 효율적인 부분검색을 가능케 하는 것이다.

이 기능은 안정화되지 않았고, 부족한 부분이 제법 많다.
현재 25 버전 기준으로도 베타 버전 상태에 있다.

아무튼, 저 유클리드 벡터에 대해 인덱스를 추가하고 싶다면, 이런 식으로 할 수 있다.

SET allow_experimental_vector_similarity_index=true;

ALTER TABLE default.vector_test
ADD INDEX vector_index vector TYPE vector_similarity('hnsw', L2Distance, 'f64', 0, 0);

vector_similarity의 매개변수는 DB 버전에 따라 정신없이 계속 바뀐다. 어떤 버전에서는 차원을 받기도 하고 안받기도 하고, 매개변수 숫자도 와리가리한다. 문서를 보고 사용할 수가 없다.

아무튼 만들고 나면 인덱스가 적용이 될텐데...

사실 잘 되진 않는다.

clickhouse의 vector index가 그렇게 순진한 형태로 구현된 것이 아니기 때문이다.
이 벡터 인덱스는 다른 인덱스들과 마찬가지로 SKIP Index 기반으로 구현된다. 잘 모른다면 이에 대한 구조 이해가 선행되어야 한다.
https://blog.naver.com/sssang97/223926075870
아무튼 중요한 것은, 벡터 인덱스는 행 단위가 아니라 granule 단위의 애매한 인덱스 단위라는 것이다.
그래서 이것도 일치하는 블록을 찾아내는 인덱스가 아니라, 일치하지 않는 블록을 버리는 인덱스로 구현된다.

그렇다보니 이건 항상 효율적이진 않아서 DB가 벡터 인덱스를 선택하지 않을 수도 있다. 기존 방식대로 스캔하는게 유리하다 판단하면 과감하게 버리고 쓰지 않는다.

EXPLAIN을 걸어보면, 인덱스를 어떻게 타는지를 확인해볼 수 있다.

내 경우에는 스킵한 비율이 높지 않아서 쓰니마니한 구성이 되어버린 상황이긴 하다.

사전 필터링과 사후 필터링

벡터 검색을 수행할때 가장 골치아픈 부분 중 하나가 필터링이다. 벡터 인덱스의 구조상 사전 필터링의 구현에는 상당한 tradeoff가 존재하기 때문이다.

사후 필터링은 쉽다. 100개 가져오면 그 중에 맞지 않는 필터링 조건에 맞지 않는 20개(예시)를 버리고 80개만 던져주면 되는 것이기 때문이다.

clickhouse의 필터링 동작은 좀 미묘한 부분이 있다. 명시적이지 않고, 현재 테이블 상태에 따라서 사전/사후 필터링을 자동으로 동작하기 때문이다. (나중에 달라질 수 있음)

만약 필터링 조건에 사용되는 값이 기본키, 그러니까 파티션 키의 일부라면, 그건 사전 필터링이 될 수 있다.
필터링으로 거른 다음에 벡터 검색을 수행한다는 것이다.
반면 필터링 조건에 사용되는 필드가 Skip Index에 걸려있거나, 아무것도 없다면 그건 사후 필터링을 선택한다.

관련된 플래그는 vector_search_filter_strategy이다. 기본값은 auto라서 자동으로 필터링 방식을 선택한다.

그래서 기본키로 인덱스를 걸어보면

실제로 999개를 스캔해와서 999개에 대해서만 벡터 검색을 수행한다는 것을 볼 수 있다.

참조
https://clickhouse.com/docs/knowledgebase/vector-search
https://clickhouse.com/docs/engines/table-engines/mergetree-family/annindexes
https://clickhouse.com/docs/sql-reference/functions/distance-functions
https://clickhouse.com/docs/operations/settings/settings#vector_search_filter_strategy