# PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees (Technical Report)

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Mar 2025.

## Built on by (most cited first, 2 of 2)

- [SemBench: A Benchmark for Semantic Query Processing Engines](https://mlsanity.com/paper/2511.01716/) (2025)
- [Evergreen: Efficient Claim Verification for Semantic Aggregates](https://mlsanity.com/paper/2604.26180/) (2026)

## Abstract (arXiv)

After decades of research in approximate query processing (AQP), its adoption in the industry remains limited. Existing methods struggle to simultaneously provide user-specified error guarantees, eliminate maintenance overheads, and avoid modifications to database management systems. To address these challenges, we introduce two novel techniques, TAQA and BSAP. TAQA is a two-stage online AQP algorithm that achieves all three properties for arbitrary queries. However, it can be slower than exact queries if we use standard row-level sampling. BSAP resolves this by enabling block-level sampling with statistical guarantees in TAQA. We simple ment TAQA and BSAP in a prototype middleware system, PilotDB, that is compatible with all DBMSs supporting efficient block-level sampling. We evaluate PilotDB on PostgreSQL, SQL Server, and DuckDB over real-world benchmarks, demonstrating up to 126X speedups when running with a 5% guaranteed error.