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.00014753664
Overall Rank: 688 | 95.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Viktor Leis (Technical University of Munich)
2. Bernhard Radke (Technical University of Munich)
3. Andrey Gubichev (Google; Technical University of Munich)
4. Alfons Kemper (Technical University of Munich)
5. Thomas Neumann (Technical University of Munich)

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
85	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035864347
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021167555
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019045544
461	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.00017829982
512	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017050173
982	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012714044
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010576304
1,542	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010308631
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010180835
1,734	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7545773e-05
2,004	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	9.2065719e-05
2,216	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.8177753e-05
2,342	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.6060437e-05
2,522	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	8.3477168e-05
2,583	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2589758e-05
2,846	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9453616e-05
2,974	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7938744e-05
3,052	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7052471e-05
3,090	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6584982e-05
3,131	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6141006e-05
3,210	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.5363533e-05
3,562	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2046519e-05
3,741	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.0594076e-05
3,982	Simplicity Done Right for Join Ordering	2021	CIDR	6.8750228e-05
4,330	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.6595681e-05
4,713	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	6.4564798e-05
5,003	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3188773e-05
5,241	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	6.2154384e-05
5,496	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.1049663e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
5,901	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	5.9539374e-05
6,660	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.7178404e-05
6,791	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6811782e-05
6,818	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	5.672718e-05
7,647	Disclosure-Compliant Query Answering	2024	SIGMOD	5.4772833e-05
7,880	Identifying Insufficient Data Coverage in Databases with Multiple Relations	2020	VLDB	5.43413e-05
7,954	Robust Query Processing: Mission Possible	2020	VLDB	5.4190023e-05
8,131	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.3936608e-05
8,164	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3852872e-05
8,347	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.350539e-05
9,113	Presto’s History-based Query Optimizer	2024	VLDB	5.2276066e-05
9,632	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.1472849e-05
9,956	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	5.1038322e-05
10,216	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.0584922e-05
10,336	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.0200193e-05
10,422	Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data	2026	SIGMOD	4.9793485e-05
10,627	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.9793485e-05
10,673	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	4.9793485e-05
10,832	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9793485e-05

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.00061066921
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024598661
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
836	Proactive Re-Optimization	2005	SIGMOD	0.00013557047
884	Dynamic Programming Strikes Back	2008	SIGMOD	0.00013267935
1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011310561
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.250242e-05
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.7649358e-05
2,251	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7511987e-05
3,427	Efficient Processing of Window Functions in Analytical SQL Queries	2015	VLDB	7.3082914e-05
3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0163619e-05
4,045	Adaptive Query Processing in the Looking Glass	2005	CIDR	6.8328968e-05
6,800	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6792071e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS
2	9,632	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
3	1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
4	1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD
5	15	How Good Are Query Optimizers, Really?	2016	VLDB
6	1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD
7	5,022	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB
8	7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD
9	2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
10	11,951	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD