DBScholar

Back to papers

Cardinality Estimation Done Right: Index-Based Join Sampling

Summary: Index-based join sampling: a main-memory cardinality estimator that uses existing indexes to sample join results and produce accurate multi-table cardinalities. Low, configurable sampling overhead substantially improves estimates and end-to-end plan quality and integrates easily into existing systems. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
312
Venue
CIDR
Year
2017
Pagerank
0.00014911698
Overall Rank
694 | 95.25%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{leis_cidr17,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '17},
        title = {{Cardinality Estimation Done Right: Index-Based Join Sampling}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Leis, Viktor and Radke, Bernhard and Gubichev, Andrey and Kemper, Alfons and Neumann, Thomas},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank Citing Paper Year Venue Pagerank
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035838391
323 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021264788
401 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019092557
465 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001803934
513 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017190574
1,061 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012369764
1,122 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.0001209124
1,499 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010564536
1,536 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010460864
1,573 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010328171
1,876 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.5717543e-05
1,988 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.3501502e-05
2,203 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.9610447e-05
2,543 Learned Cardinality Estimation: An In-depth Study 2022 SIGMOD 8.4445934e-05
2,620 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.3363963e-05
2,723 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.2049453e-05
2,991 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.8880723e-05
3,070 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7900444e-05
3,086 A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation 2021 SIGMOD 7.7708642e-05
3,162 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.6785856e-05
3,215 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6324234e-05
3,228 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6215176e-05
3,545 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.3249967e-05
3,688 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 7.201795e-05
3,959 Simplicity Done Right for Join Ordering 2021 CIDR 6.9879431e-05
4,409 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.7178579e-05
4,800 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 6.502434e-05
4,900 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.4534715e-05
5,277 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 6.2859099e-05
5,368 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.2448114e-05
5,743 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 6.1025457e-05
6,325 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9125893e-05
6,543 Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation 2023 SIGMOD 5.8461929e-05
6,704 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.797374e-05
7,193 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6770249e-05
7,503 Disclosure-Compliant Query Answering 2024 SIGMOD 5.6029996e-05
7,721 Identifying Insufficient Data Coverage in Databases with Multiple Relations 2020 VLDB 5.5587371e-05
7,829 Robust Query Processing: Mission Possible 2020 VLDB 5.5360082e-05
7,967 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.5169373e-05
8,183 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.4714466e-05
9,455 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 5.2653318e-05
9,756 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 5.2258278e-05
10,028 PRICE: A Pretrained Model for Cross-Database Cardinality Estimation 2025 VLDB 5.1745962e-05
10,108 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 5.1347137e-05
10,206 Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data 2026 SIGMOD 5.093636e-05
10,438 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 5.093636e-05
10,486 Qualitative Join Discovery in Data Lakes using Examples 2026 SIGMOD 5.093636e-05
11,083 Graph Transformers for Query Plan Representation: Potentials and Challenges 2025 VLDB 5.093636e-05
11,264 Agile-Ant: Self-managing Distributed Cache Management for Cost Optimization of Big Data Applications 2024 VLDB 5.093636e-05
11,290 Presto’s History-based Query Optimizer 2024 VLDB 5.093636e-05
Previous Page 1 / 2 Next

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
18 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059284255
53 Eddies: Continuously Adaptive Query Processing 2000 SIGMOD 0.00041071971
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
89 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00035031529
100 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034385207
241 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00023654664
492 Robust Query Processing through Progressive Optimization 2004 SIGMOD 0.0001756877
730 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014539362
829 Proactive Re-Optimization 2005 SIGMOD 0.00013769838
1,013 Dynamic Programming Strikes Back 2008 SIGMOD 0.00012652549
1,256 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011457194
1,893 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.5269935e-05
1,936 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.4557372e-05
1,987 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.3517129e-05
2,250 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.8694486e-05
2,275 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.8196821e-05
3,673 Efficient Processing of Window Functions in Analytical SQL Queries 2015 VLDB 7.2113383e-05
3,813 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.1051056e-05
3,988 Adaptive Query Processing in the Looking Glass 2005 CIDR 6.9720123e-05
6,688 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.8015211e-05
Previous Page 1 / 1 Next

Semantically Similar Papers