[LLM & RAG] Vector Database

1. Vector DB의 정의

Text, image, audio 등 embedding 방식으로 표현된 데이터를 저장하고, 관리하고, 검색하는 기능을 제공하는 Embedding vector 전용 DB를 지칭합니다.

• 고차원(vector 차원 수)의 공간(index)에 Embedded Vector를 indexing하여 저장하는 방식
  입력 Query와 가장 가까운 이웃을 찾아주는 검색방식. ANN(Approximate Nearest Neighbor) 검색 알고리즘에 기반한 검색 효율성 도모
• CRUD(Create, Read, Update, Delete) 지원
• 벡터DB 서비스는 공통적으로 1) Indexing, 2) Querying 프로세스를 따르며, 종류에 따라 Loading, Transforming, Post-Processing 등 검색 성능을 높이기 위한 추가작업이 포함

 

2. 관계형 DB (Relational DB)와의 비교

(1) 관계형 DB는 테이블 형태로 데이터를 저장하고 SQL(Structured Query Language)을 사용하여 데이터를 조작. 
(2) RDB는 정형데이터에 적합하며, 테이블 간의 관계를 설정하여 데이터의 일관성과 무결성 유지.
(3) RDB는 온라인 트랜잭션 처리(OLTP)나 보고서 생성 등의 작업에 적합
(4) RDB는 ACID(Atomicity, Consistency, Isolation, Durability) 특성을 보장하여 데이터 안전성과 일관성 유지

 

3. Vector DB의 Process

(1) Indexing : DB에 vector data를 구조화된 index에 담는 행위

추후 검색 성능을 고려하여 보통 KNN이 아닌 ANN(Approximate Nearest Neighbor) 구조로 설계합니다. Vector DB의 경우 Relation DB처럼 쿼리가 들어올때마다 전부 검색후보로 올려서 거리계산에 사용한다는 것은 불가능하기 때문이지요.
(목적: 검색정확도와 검색속도 trade-off관계 최적화)

 

Indexing Structure : Vector Embedding을 어떤 구조로 저장할 것인가?

A. Hash index : 고차원 데이터를 저차원 Hashcode로 변환하여 Searching complexity 개선하는 방식입니다. 속도가 매우 빠르나 정확도가 낮습니다. 일반적 해싱과 반대로, vector indexing 시 비슷한 데이터들끼리 Hash 충돌*이 나도록 하는 구조입니다. 이때 사용되는 해싱함수를 그대로 쿼리 벡터에 대해서도 적용시켜 동일한 해시버킷에 위치한 벡터들에 대해서만 거리 계산을 수행합니다. 대표적으로 LSH(Locally Sensitive Hashing) 등이 여기에 해당한다고 할 수 있죠.

 *아무리 좋은 해시 함수라도 다른 키 값에 대해 동일한 해쉬값을 리턴하는 경우가 있고 이런 경우를 “충돌(collision)"이라고 합니다. 

벡터 DB 로 구현하는 LLM 기반 검색 엔진 & 유사 상품 추천 시스템

 

B. Tree index : Binary Search Tree 를 활용하여 고차원 벡터공간에서의 검색 속도 향상시키는 방법입니다. 속도가 빠르나 고차원벡터에서는 정확도가 낮습니다. 유사한 Vector들이 같은 sub tree node(혹은 공간)에 속하도록 하는 방식으로 검색 시 querying vector가 속하는 sub tree node에 존재하는 다른 vecto과의 거리만 계산합니다. 대표적으로 spotify Annoy 알고리즘 등이 이 카테고리에 해당하니다. 

https://sds-aau.github.io/M3Port19/portfolio/ann/

 

C. Inverted File(IVF) index : vector space를 Voronoi diagram으로 나누어 검색하는 방식. 검색속도가 빠르나 공간을 형성하는 벡터가 많을수록 공간 나누는 작업속도가 느려집니다. 

• Clustering효과와 유사
• Centroid point와의 거리계산 후, 가장 가까운 centroid에 해당하는 공간내 벡터들만 거리계산

 

D. Graph index : Embedding Vector들을 Graph 구조로 구조화하여 Embedding vector를 노드로, 연결되는 edge를 vector간 거리로 표현하는 방식입니다. 유사한 vector끼리 edge connection이 더 잘 이루어지도록 설계 합니다. 대표적으로  HNSW(Hierarchical Navigable Small World)와 같은 알고리즘들이 여기에 해당합니다. 검색속도도 빠르고 성능도 좋습니다. 다만 그래프를 구성하는 방식에 따라 검색 성능이 의존적(Parameter tuning필요)입니다.

 

Compression : Vector Embedding을 어떤 형태로 저장할 것인가? 

Flat : Embedding vector를 원 형상 그대로 두는 방식입니다. vector간 Brute-force 계산이 이루어집니다.  kNN Full search기 때문에 데이터의 크기에 따라 연산 Complexity도 선형증가하는 특성을 가집니다. 
Quantized : Embedding vector에 대해 더 작은 단위의 byte로 구성된 chunk 들로 변환시키는 작업입니다. (float >> int)

• Quantization(SQ): indexing하려는 vector값 분포를 토대로 자주 등장하는 구간을 정의하고(보통 95/99 percentile) 이 구간 바깥의 outlier들은 구간 내 min/max값으로 cliffing
• Product Quantization(PQ): raw vector를 n개의 chunk 혹은 sub vector단위로 분할 > sub vector 단위로 k-means clustering clustering 결과로 계산된 centroid들을 sub vector별 representation으로 mapping

 

(2) Querying

A. Keyword Search : 전통적방식으로 문서의 의미적 유사성을 고려하지 않습니다. 직관적이고 빠르지만 부정확하다고 할 수 있습니다. 유저의 검색실력에 따라 검색품질이 좌우되는 것이죠.

• Attribute Filter : 단순 입력 키워드에 대한 필터 기반검색
• Sparse Vector Search : Sparse Vector를 활용한 키워드검색

B. Semantic Search : Vector DB의 기본 검색방식입니다. Cosine similarity, Euclidian distance, dot-product등을 활용하여 의미적으로 유사한 문서를 찾아냅니다.   

C. Hybrid Search : Keyword search와 semantic search를 조합