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: 6410
Venue: SIGMOD
Year: 2022
Pagerank: 5.6731116e-05
Overall Rank: 7,206 | 50.57%
DOI: 10.1145/3514221.3517896

Incoming Non-self Citations Over Time

Authors

1. Xiao Hu (Duke University)
2. Yuxi Liu (Duke University)
3. Haibo Xiu (Duke University)
4. Pankaj K. Agarwal (Duke University)
5. Debmalya Panigrahi (Duke University)
6. Sudeepa Roy (Duke University)
7. Jun Yang (Duke University)

BibTeX Citation

@inproceedings{hu_sigmod22,
        title = {{Selectivity Functions of Range Queries are Learnable*}},
        author = {Hu, Xiao and Liu, Yuxi and Xiu, Haibo and Agarwal, Pankaj K. and Panigrahi, Debmalya and Roy, Sudeepa and Yang, Jun},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517896},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517896},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,576	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.8364729e-05
8,048	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.5003171e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
9,101	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	5.324758e-05
9,626	Spatial Query Optimization With Learning	2024	VLDB	5.2434488e-05
9,958	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1879626e-05
10,875	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.093636e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
154	Neo: A Learned Query Optimizer	2019	VLDB	0.00028726181
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
1,573	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010328171
1,936	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.4557372e-05
4,617	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.604437e-05
5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.4020848e-05
7,554	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.6001388e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
2	9,353	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB
3	5,340	Machine Learning for Databases	2021	VLDB
4	4,643	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB
5	9,215	Deep Query Optimization	2019	SIGMOD
6	9,958	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB
7	8,124	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD
8	3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
9	1,573	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD
10	697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB