When Data and Queries Misalign: Understanding Performance Degradation in Streaming Approximate Nearest Neighbor Search

Vector databases increasingly operate in streaming settings where inserted vectors and incoming queries evolve over time, often causing unpredictable recall degradation in approximate nearest neighbor search (ANNS). In this paper, we argue that such degradation is primarily driven by data-query relationship shift, i.e., the evolving mismatch between the current data being indexed and the query workload, rather than by data or query drift in isolation. Specifically, we make the following three contributions. First, we use Mahalanobis distance as a lightweight metric to measure the data-query relationship, and design workloads representing static and dynamic data-query relationships based on it. Second, we evaluate these workloads using real-world datasets and demonstrate that the data-query relationship is the primary factor driving ANNS recall degradation under evolving data and query distributions. Finally, based on this insight, we outline key design steps for an online DBMS that supports adaptive index and search maintenance through continuous monitoring of the data-query relationship.