Database Paper Browser

Back to papers

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
2465
Venue
SIGMOD
Year
1990
Pagerank
0.00051315959
Overall Rank
92 | 99.37%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 67 citing papers.

Rank Citing Paper Year Venue Pagerank
4,359 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 6.2569955e-05
4,681 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.0034918e-05
5,220 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 5.6216111e-05
6,278 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 5.1309442e-05
7,271 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 4.7813404e-05
7,457 Selectivity Functions of Range Queries are Learnable* 2022 SIGMOD 4.7247191e-05
7,581 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 4.7057641e-05
7,854 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 4.6350172e-05
9,663 Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets 2003 VLDB 4.3089103e-05
9,691 Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes 2023 SIGMOD 4.3035354e-05
9,945 SSCard: Substring Cardinality Estimation using Suffix Tree-Guided Learned FM-Index 2026 SIGMOD 4.2432653e-05
10,353 Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 PODS 4.1945683e-05
10,590 ACE: A Cardinality Estimator for Set-Valued Queries 2025 VLDB 4.1945683e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
11,320 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 4.1945683e-05
12,060 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.1945683e-05
12,191 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.1945683e-05
Previous Page 2 / 2 Next

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.0040449103
10 Benchmarking Database Systems: A Systematic Approach 1983 VLDB 0.0012103754
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00070894702
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
134 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00042452811
228 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00032269684
357 Random Sampling from B+ trees 1989 VLDB 0.00026020098
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
897 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015528028
1,398 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00012197586
2,859 Database Evaluation Using Multiple Regression Techniques 1984 SIGMOD 7.9939981e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
372 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354779
18 On Random Sampling over Joins 1999 SIGMOD 0.00092385438
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05
367 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025509745
11,446 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1945683e-05
46 Simple Random Sampling from Relational Databases 1986 VLDB 0.00070894702
9,523 Analysis and Application of Adaptive Sampling 2000 PODS 4.331052e-05
1,020 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014624893
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868