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.00014749318
Overall Rank: 688 | 95.38%
DOI: -
PDF: Download (CC BY 3.0)

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.00035876108
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021166957
406	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019050182
462	An End-to-End Learning-based Cost Estimator	2020	VLDB	0.00017836105
510	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00017059914
981	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00012713454
1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202293
1,465	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	0.00010572023
1,543	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010305662
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010177136
1,735	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7566604e-05
2,002	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	9.2076835e-05
2,217	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	8.8151982e-05
2,342	Learned Cardinality Estimation: An In-depth Study	2022	SIGMOD	8.6074783e-05
2,518	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	8.3532841e-05
2,583	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2589842e-05
2,844	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	7.9446987e-05
2,975	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7905662e-05
3,053	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.7041081e-05
3,092	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6548729e-05
3,132	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	7.6107287e-05
3,208	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.5355264e-05
3,563	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2023194e-05
3,742	FACE: A Normalizing Flow based Cardinality Estimator	2022	VLDB	7.0564546e-05
3,983	Simplicity Done Right for Join Ordering	2021	CIDR	6.8722161e-05
4,330	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	6.6564176e-05
4,716	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	6.4536666e-05
5,006	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3159614e-05
5,236	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	6.2153504e-05
5,500	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.1020763e-05
5,829	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9764044e-05
5,904	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	5.9511271e-05
6,664	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.715134e-05
6,796	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6784895e-05
6,824	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	5.670071e-05
7,653	Disclosure-Compliant Query Answering	2024	SIGMOD	5.4746904e-05
7,885	Identifying Insufficient Data Coverage in Databases with Multiple Relations	2020	VLDB	5.4315576e-05
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
8,137	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.391109e-05
8,170	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3827384e-05
8,351	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.3480813e-05
9,122	Presto’s History-based Query Optimizer	2024	VLDB	5.2251319e-05
9,640	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.1448486e-05
9,962	Graph Transformers for Query Plan Representation: Potentials and Challenges	2025	VLDB	5.1014161e-05
10,222	PRICE: A Pretrained Model for Cross-Database Cardinality Estimation	2025	VLDB	5.0560976e-05
10,343	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.0176429e-05
10,434	Bridging the Gap: Cardinality Estimation for Semantic Queries on Unstructured Data	2026	SIGMOD	4.9769913e-05
10,638	CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations	2026	SIGMOD	4.9769913e-05
10,684	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	4.9769913e-05
10,842	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9769913e-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.00061067652
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.000408505
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036476265
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034748721
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034099838
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024589307
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017744392
746	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014282427
837	Proactive Re-Optimization	2005	SIGMOD	0.00013551072
883	Dynamic Programming Strikes Back	2008	SIGMOD	0.00013263866
1,258	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011308863
1,892	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4150583e-05
1,931	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3511556e-05
1,989	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2469024e-05
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.7615858e-05
2,252	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7480805e-05
3,427	Efficient Processing of Window Functions in Analytical SQL Queries	2015	VLDB	7.3048595e-05
3,800	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0130412e-05
4,046	Adaptive Query Processing in the Looking Glass	2005	CIDR	6.8297725e-05
6,802	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6773357e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS
2	9,640	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,258	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,020	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB
8	7,368	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD
9	2,432	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD
10	11,957	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD