# Exqutor: Extended Query Optimizer for Vector-augmented Analytical Queries

arXiv: https://arxiv.org/abs/2512.09695 · HTML: https://mlsanity.com/paper/2512.09695/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RAG pipeline design and evaluation, one of 15 directions in Retrieval-augmented generation.
- Builds on 25 of its 83 references that are in the map.
- First posted on arXiv 10 Dec 2025.

## Placed in

- Retrieval-augmented generation / [RAG pipeline design and evaluation](https://mlsanity.com/rag/rag-pipeline-design-and-evaluation/)

## Builds on (most cited first, 25 of 25)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [YFCC100M: The New Data in Multimedia Research](https://mlsanity.com/paper/1503.01817/) (2015)
- [Spider 2.0: Evaluating Language Models on Real-World Enterprise Text-to-SQL Workflows](https://mlsanity.com/paper/2411.07763/) (2024)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Blended RAG: Improving RAG (Retriever-Augmented Generation) Accuracy with Semantic Search and Hybrid Query-Based Retrievers](https://mlsanity.com/paper/2404.07220/) (2024)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Survey of Vector Database Management Systems](https://mlsanity.com/paper/2310.14021/) (2023)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [DeepDB: Learn from Data, not from Queries!](https://mlsanity.com/paper/1909.00607/) (2019)
- [High-Throughput Vector Similarity Search in Knowledge Graphs](https://mlsanity.com/paper/2304.01926/) (2023)
- [Manu: A Cloud Native Vector Database Management System](https://mlsanity.com/paper/2206.13843/) (2022)
- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [Vector Search with OpenAI Embeddings: Lucene Is All You Need](https://mlsanity.com/paper/2308.14963/) (2023)
- [Tree-based RAG-Agent Recommendation System: A Case Study in Medical Test Data](https://mlsanity.com/paper/2501.02727/) (2025)
- [HQANN: Efficient and Robust Similarity Search for Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2207.07940/) (2022)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Hybrid RAG-empowered Multi-modal LLM for Secure Data Management in Internet of Medical Things: A Diffusion-based Contract Approach](https://mlsanity.com/paper/2407.00978/) (2024)
- [Consistent and Flexible Selectivity Estimation for High-Dimensional Data](https://mlsanity.com/paper/2005.09908/) (2020)
- [Analytical Engines With Context-Rich Processing: Towards Efficient Next-Generation Analytics](https://mlsanity.com/paper/2212.07517/) (2022)
- [Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory](https://mlsanity.com/paper/2405.03267/) (2024)
- [Kepler: Robust Learning for Faster Parametric Query Optimization](https://mlsanity.com/paper/2306.06798/) (2023)
- [AnDB: Breaking Boundaries with an AI-Native Database for Universal Semantic Analysis](https://mlsanity.com/paper/2502.13805/) (2025)
- [Analyzing Query Optimizer Performance in the Presence and Absence of Cardinality Estimates](https://mlsanity.com/paper/2311.17293/) (2023)

## Abstract (arXiv)

Vector similarity search is becoming increasingly important for data science pipelines, particularly in Retrieval-Augmented Generation (RAG), where it enhances large language model inference by enabling efficient retrieval of relevant external knowledge. As RAG expands with table-augmented generation to incorporate structured data, workloads integrating table and vector search are becoming more prevalent. However, efficiently executing such queries remains challenging due to inaccurate cardinality estimation for vector search components, leading to suboptimal query plans. In this paper, we propose Exqutor, an extended query optimizer for vector-augmented analytical queries. Exqutor is a pluggable cardinality estimation framework designed to address this issue, leveraging exact cardinality query optimization techniques to enhance estimation accuracy when vector indexes (e.g., HNSW, IVF) are available. In scenarios lacking these indexes, we employ a sampling-based approach with adaptive sampling size adjustment, dynamically tuning the sample size to balance estimation accuracy and sampling overhead. This allows Exqutor to efficiently approximate vector search cardinalities while minimizing computational costs. We integrate our framework into pgvector, VBASE, and DuckDB, demonstrating performance improvements of up to four orders of magnitude on vector-augmented analytical queries.