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: h0fe9ea15756ca21c
Venue: SIGMOD
Year: 2022
Pagerank: 5.5499953e-05
Overall Rank: 7,332 | 50.71%
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 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,699	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.7058728e-05
8,196	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.3794981e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
8,879	Spatial Query Optimization With Learning	2024	VLDB	5.2568354e-05
9,209	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	5.2061781e-05
9,718	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1353964e-05
10,294	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0431863e-05
10,802	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9793485e-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
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
145	Neo: A Learned Query Optimizer	2019	VLDB	0.0002908188
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021167555
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019829769
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019444411
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019045544
692	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014741011
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010180835
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
4,688	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.4697463e-05
5,126	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.261175e-05
7,633	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4792473e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
2	5,911	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB
3	4,741	Machine Learning for Databases	2021	VLDB
4	4,711	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB
5	9,333	Deep Query Optimization	2019	SIGMOD
6	9,718	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB
7	8,276	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD
8	3,210	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
9	1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD
10	692	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB