OSDI '23

Currently Playing: OSDI '23 - VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed...

OSDI '23 - VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity Qianxi Zhang, Microsoft Research Asia, Shuotao Xu, Microsoft Research Asia, Qi Chen, Microsoft Research Asia, Guoxin Sui, Microsoft Research Asia, Jiadong Xie, Microsoft Research Asia and East China Normal University, Zhizhen Cai, Microsoft Research Asia and University of Science and Technology of China, Yaoqi Chen, Microsoft Research Asia and University of Science and Technology of China, Yinxuan He, Microsoft Research Asia and Renmin University of China, Yuqing Yang, Microsoft Research Asia, Fan Yang, Microsoft Research Asia, Mao Yang, Microsoft Research Asia, Lidong Zhou, Microsoft Research Asia Approximate similarity queries on high-dimensional vector indices have become the cornerstone for many critical online services. An increasing need for more sophisticated vector queries requires integrating vector search systems with relational databases. However, high-dimensional vector indices do not exhibit monotonicity, a critical property of conventional indices. The lack of monotonicity forces existing vector systems to rely on monotonicity-preserving tentative indices, set up temporarily for a target vector's TopK nearest neighbors, to facilitate queries. This leads to suboptimal performance due to the difficulty to predict the optimal K. This paper presents VBase, a system that efficiently supports complex queries of both approximate similarity search and relational operators. VBase identifies a common property, relaxed monotonicity, to unify two seemingly incompatible systems. This common property allows VBase to circumvent the constraints of a TopK-only interface to achieve significantly higher efficiency, while provably preserving the semantics of TopK-based solutions. Evaluation results show VBase offers up to three orders-of-magnitude higher performance than state-of-the-art vector systems on complex online vector queries. VBase further enables analytical similarity queries that previous vector systems do not, and shows 7,000× speedup with 99.9% accuracy of exact queries. View the full OSDI '23 program at https://www.usenix.org/conference/osdi23/technical-sessions