DBScholar

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
h362e0db68bf4ab80
Venue
SIGMOD
Year
1990
Pagerank
0.00036394222
Overall Rank
79 | 99.48%
DOI
10.1145/93597.93611

Incoming Non-self Citations Over Time

Authors

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 50 of 68 citing papers.

Rank Citing Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
234 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023726296
277 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002235043
285 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022143946
287 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00022060616
311 Approximate Query Processing Using Wavelets 2000 VLDB 0.00021315058
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020265363
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
450 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.0001806593
453 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001801482
457 Self-tuning Histograms: Building Histograms Without Looking at Data 1999 SIGMOD 0.00017915659
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017359343
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016221103
594 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015814493
689 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014725904
750 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014246313
921 Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines 1990 VLDB 0.00013036878
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012181459
1,126 Probabilistic Skylines on Uncertain Data 2007 VLDB 0.00011888563
1,156 QuickSel: Quick Selectivity Learning with Mixture Models 2020 SIGMOD 0.00011759683
1,164 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.0001170903
1,187 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00011580993
1,206 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011510881
1,261 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011289724
1,469 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010533259
1,511 Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation 2015 SIGMOD 0.00010408003
1,541 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010288394
1,569 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010177494
1,580 SchemaSQL - A Language for Interoperability in Relational Multi-database Systems 1996 VLDB 0.00010153792
1,583 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010148362
1,609 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.0001007196
1,647 Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results 1994 SIGMOD 9.9747449e-05
1,803 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.5987229e-05
1,828 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5396315e-05
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
2,176 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9031141e-05
2,523 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3316032e-05
2,682 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 8.1203255e-05
2,852 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9201312e-05
2,994 Optimizing Boolean Expressions in Object Bases 1992 VLDB 7.756091e-05
3,009 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7439468e-05
3,060 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.6828463e-05
3,093 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6378811e-05
3,361 Exact Cardinality Query Optimization for Optimizer Testing 2009 VLDB 7.3621595e-05
3,555 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.1877332e-05
4,563 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5201574e-05
Previous Page 1 / 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.0023948467
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047770864
46 Benchmarking Database Systems: A Systematic Approach 1983 VLDB 0.00044656322
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00039922419
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031291457
175 Simple Random Sampling from Relational Databases 1986 VLDB 0.00026701703
183 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026316699
425 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018437618
480 Random Sampling from B+ trees 1989 VLDB 0.00017573936
960 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00012825107
1,012 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012489386
1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010696781
1,648 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 9.9739132e-05
3,339 Database Evaluation Using Multiple Regression Techniques 1984 SIGMOD 7.3895792e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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