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.529034e-05
Overall Rank: 7,355 | 50.70%
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,718	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.6843134e-05
8,219	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.359172e-05
8,412	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3211467e-05
8,908	Spatial Query Optimization With Learning	2024	VLDB	5.2369727e-05
9,240	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	5.1867235e-05
9,753	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1159926e-05
10,327	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0241309e-05
10,873	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9605343e-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.00047654188
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035920657
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
142	Neo: A Learned Query Optimizer	2019	VLDB	0.00029114937
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
320	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021128745
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
381	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019497061
405	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019020138
690	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014703258
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012181459
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011759683
1,583	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010148362
1,935	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3407959e-05
4,703	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.4458272e-05
5,153	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.2375324e-05
7,654	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4588598e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	287	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
2	5,918	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB
3	4,765	Machine Learning for Databases	2021	VLDB
4	4,726	Learned Index Benefits: Machine Learning Based Index Performance Estimation	2022	VLDB
5	9,365	Deep Query Optimization	2019	SIGMOD
6	9,753	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB
7	8,297	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD
8	3,212	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
9	1,583	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD
10	690	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB