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: 14013
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,831 | 25.69%
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
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
1,767	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.805856e-05
1,799	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.7326398e-05
2,058	Automatically Generating Data Exploration Sessions Using Deep Reinforcement Learning	2020	SIGMOD	9.2480248e-05
3,288	I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making	2017	VLDB	7.5578177e-05
3,370	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.4700891e-05
3,881	Using Trees to Depict a Forest	2009	VLDB	7.0490549e-05
4,205	Sample Debiasing in the Themis Open World Database System	2020	SIGMOD	6.8337021e-05
4,261	Relational Data Synthesis using Generative Adversarial Networks: A Design Space Exploration	2020	VLDB	6.7982037e-05
4,789	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.5072039e-05
6,039	Guided Exploration of User Groups	2020	VLDB	5.9990875e-05
6,262	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.9361728e-05
7,222	Hear the Whole Story: Towards the Diversity of Opinion in Crowdsourcing Markets	2015	VLDB	5.6679185e-05

Semantically Similar Papers

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