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.9793485e-05
Overall Rank: 11,239 | 24.44%
DOI: 10.14778/3725688.3725695

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.00061066921
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021167555
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
840	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.0001354605
1,797	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.6187325e-05
1,829	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.5510333e-05
2,048	Automatically Generating Data Exploration Sessions Using Deep Reinforcement Learning	2020	SIGMOD	9.1229916e-05
3,341	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.4063139e-05
3,419	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3190065e-05
3,963	Using Trees to Depict a Forest	2009	VLDB	6.8922952e-05
4,253	Sample Debiasing in the Themis Open World Database System	2020	SIGMOD	6.7015395e-05
4,329	Relational Data Synthesis using Generative Adversarial Networks: A Design Space Exploration	2020	VLDB	6.6597797e-05
4,781	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.4162085e-05
6,162	Guided Exploration of User Groups	2020	VLDB	5.8644841e-05
6,282	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.8237283e-05
7,371	Hear the Whole Story: Towards the Diversity of Opinion in Crowdsourcing Markets	2015	VLDB	5.5407456e-05

Semantically Similar Papers

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