Practical Selectivity Estimation through Adaptive Sampling

Summary: Adaptive random sampling is extended to practical selectivity estimation for selects and joins, with tighter bounds on sample size for fixed accuracy. Introduces sanity bounds for highly skewed data or very small results and shows encouraging performance when integrated with a commercial relational DBMS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h362e0db68bf4ab80
Venue: SIGMOD
Year: 1990
Pagerank: 0.00036487763
Overall Rank: 79 | 99.48%
DOI: 10.1145/93597.93611

Incoming Non-self Citations Over Time

Authors

1. Richard J. Lipton (Princeton University)
2. Jeffrey F. Naughton (University of Wisconsin)
3. Donovan A. Schneider (University of Wisconsin)

BibTeX Citation

@inproceedings{lipton_sigmod90,
        title = {{Practical Selectivity Estimation through Adaptive Sampling}},
        author = {Lipton, Richard J. and Naughton, Jeffrey F. and Schneider, Donovan A.},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.93611},
        url = {https://dl.acm.org/doi/10.1145/93597.93611},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 68 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,679	The Power of Sampling in Knowledge Discovery	1994	PODS	6.4726631e-05
4,958	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB	6.3394776e-05
5,021	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.3106761e-05
5,656	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.0488629e-05
6,791	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6811782e-05
7,332	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.5499953e-05
7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.5103311e-05
7,519	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.502959e-05
9,976	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	5.1031384e-05
9,992	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.099523e-05
10,322	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.0346745e-05
10,858	Sema: A High-performance System for LLM-based Semantic Query Processing	2026	VLDB	4.9793485e-05
11,089	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.9793485e-05
11,257	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	4.9793485e-05
11,290	Cardinality Estimation for Having-Clauses	2025	VLDB	4.9793485e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-05
12,549	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	4.9793485e-05
12,677	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
46	Benchmarking Database Systems: A Systematic Approach	1983	VLDB	0.00044784799
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026784195
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026389403
422	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018492336
477	Random Sampling from B+ trees	1989	VLDB	0.00017632787
956	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00012865801
1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012529816
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
1,641	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00010007832
3,334	Database Evaluation Using Multiple Regression Techniques	1984	SIGMOD	7.4152053e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
2	57	On Random Sampling over Joins	1999	SIGMOD
3	1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
4	346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD
5	11,951	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD
6	175	Simple Random Sampling from Relational Databases	1986	VLDB
7	9,849	Analysis and Application of Adaptive Sampling	2000	PODS
8	1,184	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD
9	1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS
10	1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS