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

**Authors:** Yuxuan Zhu, Tengjun Jin, Stefanos Baziotis, Chengsong Zhang, Charith Mendis, Daniel Kang  
**arXiv:** [2503.21087](https://arxiv.org/abs/2503.21087)  
**Date:** 2025-03-27  
**Summary page:** https://www.summarizepaper.com/en/paper/2503.21087v1/

## Key points

- Authors Yuxuan Zhu, Tengjun Jin, Stefanos Baziotis, Chengsong Zhang, Charith Mendis, and Daniel Kang introduce two innovative techniques TAQA and BSAP to address challenges in approximate query processing (AQP).
- TAQA is a two-stage online AQP algorithm that provides user-specified error guarantees, eliminates maintenance overheads, and avoids modifications to database management systems.
- BSAP enables block-level sampling with statistical guarantees within the algorithm to enhance the efficiency of TAQA.
- The authors develop a prototype middleware system called PilotDB to implement these techniques and achieve a priori error guarantees and substantial speedups on various DBMSs.
- Evaluation of PilotDB on PostgreSQL, SQL Server, and DuckDB shows significant speedups of up to 126 times when running with a 5% guaranteed error.
- Contributions include the proposal of TAQA for achieving error guarantees simultaneously (P1), development of BSAP for enabling block sampling for nested and join queries (P2), and construction/evaluation of PilotDB implementing both techniques (P3).
- This research addresses limitations in existing literature related to approximate query processing by introducing novel algorithms and statistical techniques that improve performance while maintaining error guarantees across different DBMSs.

## Summary

In their technical report "PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees," authors Yuxuan Zhu, Tengjun Jin, Stefanos Baziotis, Chengsong Zhang, Charith Mendis, and Daniel Kang introduce two innovative techniques <b>TAQA and BSAP </b>to address challenges faced by existing methods in <b>approximate query processing (AQP)</b>. These techniques aim to provide user-specified error guarantees, eliminate maintenance overheads, and avoid modifications to database management systems. The first technique, <b>TAQA </b>, is a two-stage online AQP algorithm that successfully achieves all three properties for arbitrary queries. However, it may be slower than exact queries when using standard row-level sampling. To enhance the efficiency of TAQA, the authors also propose <b>BSAP </b>, which enables block-level sampling with statistical guarantees within the algorithm. To implement these techniques and achieve a priori error guarantees and substantial speedups on various DBMSs, the authors develop a prototype middleware system called <b>PilotDB </b>. This system is compatible with all database management systems supporting efficient block-level sampling. The evaluation of PilotDB on PostgreSQL, SQL Server, and DuckDB using real-world benchmarks demonstrates significant speedups of up to 126 times when running with a 5% guaranteed error. The contributions of this work include the proposal of TAQA for achieving error guarantees simultaneously (P1), the development of BSAP for enabling block sampling to answer approximate nested and join queries (P2), and the construction and evaluation of PilotDB implementing both techniques (P3). Overall, this research addresses key limitations in existing literature related to approximate query processing by introducing novel algorithms and statistical techniques that significantly improve performance while maintaining error guarantees across different database management systems.