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

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 3 of 53 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,539	Juggler: Autonomous Cost Optimization and Performance Prediction of Big Data Applications	2022	SIGMOD	5.093636e-05
11,644	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD	5.093636e-05
11,902	Tighter Upper Bounds for Join Cardinality Estimates	2018	SIGMOD	5.093636e-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
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

Semantically Similar Papers

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