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.9769913e-05
Overall Rank: 11,247 | 24.41%
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.00061067652
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021166957
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.0001409096
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013543
1,797	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.6143465e-05
1,828	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.547768e-05
2,050	Automatically Generating Data Exploration Sessions Using Deep Reinforcement Learning	2020	SIGMOD	9.1186729e-05
3,341	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.4028264e-05
3,417	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3184905e-05
3,965	Using Trees to Depict a Forest	2009	VLDB	6.8890329e-05
4,254	Sample Debiasing in the Themis Open World Database System	2020	SIGMOD	6.698367e-05
4,329	Relational Data Synthesis using Generative Adversarial Networks: A Design Space Exploration	2020	VLDB	6.656734e-05
4,779	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.416435e-05
6,165	Guided Exploration of User Groups	2020	VLDB	5.8617079e-05
6,285	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.8209714e-05
7,377	Hear the Whole Story: Towards the Diversity of Opinion in Crowdsourcing Markets	2015	VLDB	5.5381227e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
2	8,174	Complete Approximations of Incomplete Queries	2013	VLDB
3	11,291	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,650	Anytime Approximation in Probabilistic Databases via Scaled Dissociations	2019	SIGMOD
6	12,257	Holistic Query Evaluation over Information Extraction Pipelines	2018	VLDB
7	4,779	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR
8	4,485	LearnedSQLGen: Constraint-aware SQL Generation using Reinforcement Learning	2022	SIGMOD
9	3,057	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR
10	5,905	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB