VBASE: Unifying Online Vector Similarity Search and Relational Queries viaRelaxed Monotonicity

논문정보: https://www.usenix.org/conference/osdi23/presentation/zhang-qianxi

VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity | USENIX

 

Motivation

• 벡터 인덱스를 관계형 데이터베이스의 전통적인 인덱스(e.g. B-Tree)와 동일하게 취급하기 어려운 것은, monotonicity를 갖고 있지 않기 때문이다. 이에 따라서 현존하는 vector index/database에서는 TopK 를 바탕으로 monotonicity-preserving tentative index를 만들어서 쿼리를 실행하게 하지만, 이 경우 최적의 K를 알 수 없다는 점이 가장 큰 문제다.
  • 예를 들어서 최종적으로 5개의 벡터를 찾아내야 하는 상황을 가정하자. 현재의 시스템에서는 먼저 TopK로 K'개를 골라낸 뒤에 여기에서 튜플의 관계형 데이터에 대한 필터링을 거쳐서 적어도 5개 이상을 남길 수 있어야 하는데, K'를 몇으로 하는 게 적절할 지 예측하기 쉽지 않다. 큰 K'를 사용한다면 정확도가 올라가지만 query latency가 길어진다.
• 그렇다면 벡터 인덱스가 monotonicity를 어떻게 따르게 하여, 전통적인 인덱스와 동일하게 사용할 수 있을 것인가?

Key Idea

• Relaxed monotonicity라는 개념을 통해 벡터 검색과 기존 데이터베이스 시스템의 공통 기반을 마련한다.
• 상기의 개념화를 통해, 벡터와 스칼라 자료 모두에 대해 통합된 쿼리 실행 엔진을 구현한다. 이때, 벡터 자료에 대한 쿼리 실행도 iterator model(i.e. volcano model)에 따라 이루어지도록 한다.
• 위와 같은 쿼리 실행의 결과는 최적의 K'값에 기반한 TopK방식의 쿼리 실행 결과와 동일한 결과를 갖는다는 점을 증명할 수 있으며, K'에 대한 별도의 예측 없이 인덱스 traversal 과정에서 최적의 K'를 찾게 되는 구조라는 점이 우월한 성능을 보장한다.

Details

• 벡터 인덱스 traversal 과정은 두 개의 단계로 특징지어지는데, 큰 변동폭을 가지면서도 서서히 target 벡터의 영역으로 가까워지는 단계(Phase 1)와 target 벡터 영역에 도달하여 비교적 작은 변동폭을 갖되 target 벡터로부터 서서히 멀어지는 단계(Phase 2)로 볼 수 있다.
• 이때 relaxed monotonicity 개념을 통해, Phase 2에 도달하였는지를 식별할 수 있다. 지금까지 방문한 벡터들 가운데 query와 가장 가까운 E개의 벡터 중 가장 먼 것의 거리를 반지름으로 하여 query를 중심에 둔 원을 그릴 때, 가장 최근 방문한 w 개의 벡터들이 쿼리와 갖는 거리 중 중앙값(median)이 이 원의 바깥에 있게 되면(즉 중앙값이 반지름보다 커지면) 우리의 주된 관심 영역에서 벗어난 traversal이 이루어진다는 것이다.
  • 수식으로는 $\exists{s} \; M^{t}_{q} \geq R_{q} \; \forall{t} \geq s$ 과 같이 표현되는데, 즉 traversal을 하다보면 어느 시점 이후로는 점점 멀어지기만 하기 마련이라는 의미다.
• 이 개념의 장점은 on-the-fly로 쿼리 실행 종료 조건을 탐지할 수 있다는 것인데, 흥미롭게도 기존의 잘 알려진 벡터 인덱스들은 모두 relaxed monotonicity를 만족하고 있다(애초에 이를 염두에 두고 설계된 개념으로 볼 수 있겠다). 물론, strict monotonicity를 만족하는 전통 인덱스들은 relaxed monotonicity의 특수한 경우로서 볼 수 있다.
• 이를 바탕으로 벡터 인덱스 또한 전통 인덱스와 동일한 방식으로 작동하도록 재설계할 경우, iterator model에서 vector가 하나씩 emit되어서 필터를 거치는 식으로 실행시킬 수 있다. 이렇게 한 개씩 처리된 벡터 데이터가 relaxed monotonicity 조건을 pass(즉 phase 2로 전이)하고 termination condition(K개가 추출)도 만족되면 쿼리 실행이 종료된다. 반면 기존의 TopK방식 시스템에서는 K'의 상위 벡터들을 뽑아낸 뒤에 이에 대해서 필터를 적용하기 때문에, 우리의 목표치인 K개를 정확히 뽑아낸다는 보장이 없다.
• 이외에 상세한 구현이나 cost estimation, multi-column scan에 대해서도 설명하고 있다.