Selectivity Functions of Range Queries are Learnable*

Summary: ML-based selectivity estimation for range queries; bounded VC-dimension implies learnable functions. Empirical results show simple learners match specialized methods on orthogonal, linear, and distance-based ranges with theory-sized training data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6349
Venue: SIGMOD
Year: 2022
Pagerank: 4.7248554e-05
Overall Rank: 7,442 | 48.28%
DOI: 10.1145/3514221.3517896

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,565	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.0033542e-05
8,440	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.505741e-05
8,636	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	4.4758336e-05
9,078	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	4.3959645e-05
9,487	Spatial Query Optimization With Learning	2024	VLDB	4.3300131e-05
9,811	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	4.2742278e-05
10,627	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
203	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034868567
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
329	Neo: A Learned Query Optimizer	2019	VLDB	0.00027301488
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
606	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019251186
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
752	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00017138049
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,727	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010731889
2,359	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.967267e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.955077e-05
5,477	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	5.4856699e-05
5,630	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	5.4010111e-05
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
373	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354685
9,311	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB	4.3535588e-05
5,787	Machine Learning for Databases	2021	VLDB	5.3256401e-05
5,343	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB	5.5582234e-05
9,117	Deep Query Optimization	2019	SIGMOD	4.3885415e-05
9,811	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	4.2742278e-05
8,383	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD	4.5261239e-05
3,955	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5895015e-05
2,364	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	8.955077e-05
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459