Back to papers
Small Selectivities Matter: Lifting the Burden of Empty Samples
Summary: Addresses zero-tuple selectivities in sampling-based cardinality estimation with a novel approach compatible with any DBMS capable of sampling. Shows up to two orders of magnitude reduction in estimation error and 1.3-1.8x faster responses for complex filters, with negligible impact on optimization time.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 6086
- Venue
- SIGMOD
- Year
- 2021
- Pagerank
- 4.3461329e-05
- Overall Rank
- 9,380 | 34.75%
- DOI
-
10.1145/3448016.3452805
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 20 of 20 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 71 |
How Good Are Query Optimizers, Really? |
2016 |
VLDB |
0.00059038975 |
| 141 |
Selectivity Estimation Without the Attribute Value Independence Assumption |
1997 |
VLDB |
0.00041786333 |
| 204 |
Learned Cardinalities: Estimating Correlated Joins with Deep Learning |
2019 |
CIDR |
0.00034784455 |
| 325 |
The History of Histograms (abridged) |
2003 |
VLDB |
0.00027378328 |
| 512 |
STHoles: A Multidimensional Workload-Aware Histogram |
2001 |
SIGMOD |
0.00021380733 |
| 629 |
Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors |
2009 |
VLDB |
0.00018942366 |
| 684 |
Towards a Robust Query Optimizer: A Principled and Practical Approach |
2005 |
SIGMOD |
0.00018179769 |
| 758 |
Deep Unsupervised Cardinality Estimation |
2020 |
VLDB |
0.0001706608 |
| 1,043 |
Adaptive Ordering of Pipelined Stream Filters |
2004 |
SIGMOD |
0.00014476247 |
| 1,105 |
Cardinality Estimation Done Right: Index-Based Join Sampling |
2017 |
CIDR |
0.00013990395 |
| 1,254 |
Selectivity Estimation for Range Predicates using Lightweight Models |
2019 |
VLDB |
0.00013027411 |
| 1,981 |
Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses |
2018 |
VLDB |
9.8687545e-05 |
| 2,165 |
Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation |
2015 |
SIGMOD |
9.389622e-05 |
| 3,013 |
Cardinality Estimation Using Sample Views with Quality Assurance |
2007 |
SIGMOD |
7.7137441e-05 |
| 3,725 |
Estimating Cardinalities with Deep Sketches |
2019 |
SIGMOD |
6.8170734e-05 |
| 3,905 |
Native Store Extension for SAP HANA |
2019 |
VLDB |
6.6408563e-05 |
| 4,523 |
Simplicity Done Right for Join Ordering |
2021 |
CIDR |
6.1135504e-05 |
| 4,571 |
Adaptive Statistics in Oracle 12c |
2017 |
VLDB |
6.0773174e-05 |
| 5,905 |
Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA |
2014 |
SIGMOD |
5.2788785e-05 |
| 6,374 |
Optimization of Conjunctive Predicates for Main Memory Column Stores |
2016 |
VLDB |
5.0927058e-05 |
Semantically Similar Papers