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: 2527
Venue: SIGMOD
Year: 1990
Pagerank: 0.00037054261
Overall Rank: 76 | 99.49%
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 17 of 67 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,584	The Power of Sampling in Knowledge Discovery	1994	PODS	6.6181342e-05
4,857	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB	6.4752373e-05
4,926	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.4428362e-05
5,537	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.1820087e-05
7,193	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6770249e-05
7,206	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.6731116e-05
7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.629255e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
9,793	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	5.2193018e-05
9,825	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.2143223e-05
10,097	SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index	2026	SIGMOD	5.1502319e-05
10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.093636e-05
10,851	ACE: A Cardinality Estimator for Set-Valued Queries	2025	VLDB	5.093636e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-05
12,258	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	5.093636e-05
12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB	5.093636e-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.0024089429
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
45	Benchmarking Database Systems: A Systematic Approach	1983	VLDB	0.00045531113
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026881845
417	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018819871
467	Random Sampling from B+ trees	1989	VLDB	0.00018002218
934	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00013108714
992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012790174
1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010965236
1,614	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00010215186
3,280	Database Evaluation Using Multiple Regression Techniques	1984	SIGMOD	7.5709479e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
2	54	On Random Sampling over Joins	1999	SIGMOD
3	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
4	339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD
5	11,644	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD
6	173	Simple Random Sampling from Relational Databases	1986	VLDB
7	9,676	Analysis and Application of Adaptive Sampling	2000	PODS
8	1,172	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD
9	1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS
10	992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS