Holistic query Approximation via RL Modeling

Summary: Presents Holistic Approximate Query Processing: select a compact approximation set to accelerate both aggregate and non-aggregate queries; problem formalized and shown NP-complete. Proposes HARLM, an RL solver that handles large action spaces and generalizes beyond workloads, yielding ~30% accuracy improvement and 10–35× speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h44ec83da5a12a4da
Venue: VLDB
Year: 2025
Pagerank: 4.9605343e-05
Overall Rank: 11,303 | 24.24%
DOI: 10.14778/3725688.3725695
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Susan B. Davidson (University of Pennsylvania)
2. Tova Milo (Tel Aviv University)
3. Kathy Razmadze (Tel Aviv University)
4. Gal Zeevi (Tel Aviv University)

BibTeX Citation

@article{davidson_vldb25,
        title = {{Holistic query Approximation via RL Modeling}},
        author = {Davidson, Susan B. and Milo, Tova and Razmadze, Kathy and Zeevi, Gal},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {6},
        pages = {1635--1648},
        doi = {10.14778/3725688.3725695},
        url = {https://doi.org/10.14778/3725688.3725695},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
320	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021128745
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013503124
1,804	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.5971444e-05
1,839	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.5187688e-05
2,057	Automatically Generating Data Exploration Sessions Using Deep Reinforcement Learning	2020	SIGMOD	9.0995439e-05
3,348	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.3783668e-05
3,428	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.2957009e-05
3,983	Using Trees to Depict a Forest	2009	VLDB	6.8662651e-05
4,270	Sample Debiasing in the Themis Open World Database System	2020	SIGMOD	6.6762181e-05
4,348	Relational Data Synthesis using Generative Adversarial Networks: A Design Space Exploration	2020	VLDB	6.6367564e-05
4,792	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.4010108e-05
6,182	Guided Exploration of User Groups	2020	VLDB	5.8423254e-05
6,300	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.8017237e-05
7,396	Hear the Whole Story: Towards the Diversity of Opinion in Crowdsourcing Markets	2015	VLDB	5.5198102e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
2	8,189	Complete Approximations of Incomplete Queries	2013	VLDB
3	11,347	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB
4	1,583	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD
5	8,669	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD
6	12,300	Holistic Query Evaluation over Information Extraction Pipelines	2018	VLDB
7	4,792	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR
8	4,508	LearnedSQLGen: Constraint-aware SQL Generation using Reinforcement Learning	2022	SIGMOD
9	3,062	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR
10	5,918	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB