<p>In today’s analytics and recommendation systems, querying data that combines structured and unstructured forms has become essential. While approximate nearest neighbor search (ANNS) usually converts unstructured data, such as text and videos, to high-dimensional vectors, vector search is implemented as a relational engine plugin in contemporary database systems, which solely rely on ANN indices. Current vector-relational database systems (e.g., CHASE, VBASE) employ fixed execution strategies that commit unconditionally to ANN index traversal for all vector similarity operations, regardless of query characteristics. This design is fundamentally suboptimal: (1) Under highly selective structured predicates (e.g., <InlineEquation ID="IEq1"><EquationSource Format="TEX">\(\sigma = 0.01\)</EquationSource></InlineEquation>), ANN over-fetches hundreds of candidates of which up to 95% are discarded post-filter, wasting substantial computational resources. (2) Sparse vector distributions cause ANN graph traversal to explore irrelevant regions, degrading efficiency and recall. DYNAMICANN overcomes this with a cost-aware optimizer that evaluates a runtime cost ratio <InlineEquation ID="IEq2"><EquationSource Format="TEX">\(C_\text {ANN}/C_\text {Scan}\)</EquationSource></InlineEquation>, where: <InlineEquation ID="IEq3"><EquationSource Format="TEX">\(C_\text {ANN} = \alpha \cdot \log _2(N) + K' \cdot \beta \cdot d + K' \cdot (1-\sigma ) \cdot \gamma\)</EquationSource></InlineEquation> (HNSW graph traversal, distance computations, post-filter overhead); <InlineEquation ID="IEq4"><EquationSource Format="TEX">\(C_\text {Scan} = 0.1{\cdot }N + M{\cdot }(\beta {\cdot }d+\gamma )\)</EquationSource></InlineEquation>, <InlineEquation ID="IEq5"><EquationSource Format="TEX">\(M=N\cdot \sigma\)</EquationSource></InlineEquation>. The ANN path is selected if <InlineEquation ID="IEq6"><EquationSource Format="TEX">\(C_\text {ANN} < 0.9 \cdot C_\text {Scan}\)</EquationSource></InlineEquation>; scan if <InlineEquation ID="IEq7"><EquationSource Format="TEX">\(C_\text {Scan} < 0.9 \cdot C_\text {ANN}\)</EquationSource></InlineEquation>; else ANN is preferred to preserve recall. We evaluate DYNAMICANN on four representative hybrid query templates (LAION-400M, 512-dim): Q1 (top-K, single filter, <InlineEquation ID="IEq8"><EquationSource Format="TEX">\(\sigma {=}0.05\)</EquationSource></InlineEquation>); Q2 (distance-range, <InlineEquation ID="IEq9"><EquationSource Format="TEX">\(\sigma {=}0.01\)</EquationSource></InlineEquation>); Q3 (join + distance-range, <InlineEquation ID="IEq10"><EquationSource Format="TEX">\(\sigma {=}0.4\)</EquationSource></InlineEquation>); Q4 (windowed top-K, <InlineEquation ID="IEq11"><EquationSource Format="TEX">\(\sigma {=}0.15\)</EquationSource></InlineEquation>). Accuracy is Recall@10: fraction of true nearest neighbors in top-10 vs. brute-force ground truth. By combining adaptive vector search and cost-based relational optimization, DYNAMICANN achieves measured speedups of 2.1–9.8<InlineEquation ID="IEq12"><EquationSource Format="TEX">\(\times\)</EquationSource></InlineEquation> over CHASE for low-selectivity queries (<InlineEquation ID="IEq13"><EquationSource Format="TEX">\(\sigma \le 0.05\)</EquationSource></InlineEquation>), maintaining Recall@10 <InlineEquation ID="IEq14"><EquationSource Format="TEX">\(>97\%\)</EquationSource></InlineEquation> across all query types, with plan-switching overhead <InlineEquation ID="IEq15"><EquationSource Format="TEX">\(<1\%\)</EquationSource></InlineEquation> of total execution time.</p>

Adaptive optimization for hybrid vector-relational queries via cost-aware plan switching

期刊论文
出版模式：

开放获取
发表日期：

2026年6月27日

查看全文

Alok Kumar,
Kiran Rajput,
Utsav Upadhyay,
Rahul Malik,
Satyabrata Roy,
Lokesh Sharma

摘要

In today’s analytics and recommendation systems, querying data that combines structured and unstructured forms has become essential. While approximate nearest neighbor search (ANNS) usually converts unstructured data, such as text and videos, to high-dimensional vectors, vector search is implemented as a relational engine plugin in contemporary database systems, which solely rely on ANN indices. Current vector-relational database systems (e.g., CHASE, VBASE) employ fixed execution strategies that commit unconditionally to ANN index traversal for all vector similarity operations, regardless of query characteristics. This design is fundamentally suboptimal: (1) Under highly selective structured predicates (e.g., \(\sigma = 0.01\)), ANN over-fetches hundreds of candidates of which up to 95% are discarded post-filter, wasting substantial computational resources. (2) Sparse vector distributions cause ANN graph traversal to explore irrelevant regions, degrading efficiency and recall. DYNAMICANN overcomes this with a cost-aware optimizer that evaluates a runtime cost ratio \(C_\text {ANN}/C_\text {Scan}\), where: \(C_\text {ANN} = \alpha \cdot \log _2(N) + K' \cdot \beta \cdot d + K' \cdot (1-\sigma ) \cdot \gamma\) (HNSW graph traversal, distance computations, post-filter overhead); \(C_\text {Scan} = 0.1{\cdot }N + M{\cdot }(\beta {\cdot }d+\gamma )\), \(M=N\cdot \sigma\). The ANN path is selected if \(C_\text {ANN} < 0.9 \cdot C_\text {Scan}\); scan if \(C_\text {Scan} < 0.9 \cdot C_\text {ANN}\); else ANN is preferred to preserve recall. We evaluate DYNAMICANN on four representative hybrid query templates (LAION-400M, 512-dim): Q1 (top-K, single filter, \(\sigma {=}0.05\)); Q2 (distance-range, \(\sigma {=}0.01\)); Q3 (join + distance-range, \(\sigma {=}0.4\)); Q4 (windowed top-K, \(\sigma {=}0.15\)). Accuracy is Recall@10: fraction of true nearest neighbors in top-10 vs. brute-force ground truth. By combining adaptive vector search and cost-based relational optimization, DYNAMICANN achieves measured speedups of 2.1–9.8\(\times\) over CHASE for low-selectivity queries (\(\sigma \le 0.05\)), maintaining Recall@10 \(>97\%\) across all query types, with plan-switching overhead \(<1\%\) of total execution time.