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
hd7dca7a4601cd891
Venue
CIDR
Year
2017
Pagerank
0.00014725904
Overall Rank
689 | 95.39%
DOI
-
PDF
Download (CC BY 3.0)

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 54 citing papers.

Rank Citing Paper Year Venue Pagerank
84 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00035920657
320 DeepDB: Learn from Data, not from Queries! 2020 VLDB 0.00021128745
405 Deep Unsupervised Cardinality Estimation 2020 VLDB 0.00019020138
453 An End-to-End Learning-based Cost Estimator 2020 VLDB 0.0001801482
508 NeuroCard: One Cardinality Estimator for All Tables 2021 VLDB 0.00017108973
983 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012677179
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012181459
1,444 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010616242
1,541 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010288394
1,583 Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries 2020 SIGMOD 0.00010148362
1,740 Flow-Loss: Learning Cardinality Estimates That Matter 2021 VLDB 9.7289523e-05
2,009 FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation 2021 VLDB 9.1813272e-05
2,228 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.7912743e-05
2,348 Learned Cardinality Estimation: An In-depth Study 2022 SIGMOD 8.5910072e-05
2,523 Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation 2022 VLDB 8.3316032e-05
2,584 Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation 2021 VLDB 8.2435322e-05
2,852 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9201312e-05
2,987 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.767043e-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,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.5902303e-05
3,212 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.5145409e-05
3,555 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.1877332e-05
3,740 FACE: A Normalizing Flow based Cardinality Estimator 2022 VLDB 7.0398782e-05
3,995 Simplicity Done Right for Join Ordering 2021 CIDR 6.8530469e-05
4,329 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.64569e-05
4,725 Scalable Reservoir Sampling on Many-Core CPUs 2019 SIGMOD 6.4337491e-05
5,029 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.2952031e-05
5,245 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 6.1995935e-05
5,522 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.0818991e-05
5,717 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0067263e-05
5,841 Joins on Samples: A Theoretical Guide for Practitioners 2020 VLDB 5.9569427e-05
6,672 Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation 2023 SIGMOD 5.6975871e-05
6,812 dbET: Execution Time Distribution-based Plan Selection 2023 SIGMOD 5.6597129e-05
6,840 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.6513231e-05
7,666 Disclosure-Compliant Query Answering 2024 SIGMOD 5.4565877e-05
7,902 Identifying Insufficient Data Coverage in Databases with Multiple Relations 2020 VLDB 5.4135994e-05
7,975 Robust Query Processing: Mission Possible 2020 VLDB 5.3985544e-05
8,154 Thrifty Query Execution via Incrementability 2020 SIGMOD 5.3732833e-05
8,188 Efficient Query Re-optimization with Judicious Subquery Selections 2023 SIGMOD 5.3649397e-05
8,363 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.3305234e-05
9,141 Presto’s History-based Query Optimizer 2024 VLDB 5.2078543e-05
9,667 Small Selectivities Matter: Lifting the Burden of Empty Samples 2021 SIGMOD 5.1278365e-05
9,995 Graph Transformers for Query Plan Representation: Potentials and Challenges 2025 VLDB 5.0845476e-05
10,045 Agile-Ant: Self-managing Distributed Cache Management for Cost Optimization of Big Data Applications 2024 VLDB 5.0786422e-05
10,257 PRICE: A Pretrained Model for Cross-Database Cardinality Estimation 2025 VLDB 5.039379e-05
10,370 An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL 2025 SIGMOD 5.0010514e-05
10,500 Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data 2026 SIGMOD 4.9605343e-05
10,699 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.9605343e-05
10,745 Qualitative Join Discovery in Data Lakes using Examples 2026 SIGMOD 4.9605343e-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
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061463175
53 Eddies: Continuously Adaptive Query Processing 2000 SIGMOD 0.00040739114
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034691614
98 LEO - DB2's LEarning Optimizer 2001 VLDB 0.00034050614
215 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00024554257
471 Robust Query Processing through Progressive Optimization 2004 SIGMOD 0.00017691682
750 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014246313
838 Proactive Re-Optimization 2005 SIGMOD 0.00013528646
881 Dynamic Programming Strikes Back 2008 SIGMOD 0.0001324243
1,261 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00011289724
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
1,935 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3407959e-05
1,987 Plan Bouquets: Query Processing without Selectivity Estimation 2014 SIGMOD 9.2323722e-05
2,248 Cache-Efficient Aggregation: Hashing Is Sorting 2015 SIGMOD 8.7484225e-05
2,261 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7351549e-05
3,438 Efficient Processing of Window Functions in Analytical SQL Queries 2015 VLDB 7.2807703e-05
3,807 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 6.9902343e-05
4,069 Adaptive Query Processing in the Looking Glass 2005 CIDR 6.8080574e-05
6,816 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6593309e-05
Previous Page 1 / 1 Next

Semantically Similar Papers