Simplicity Done Right for Join Ordering

Summary: Lightweight join-ordering: a simple general upper bound for multi-joins, bound-guided enumeration, and sampling-as-execution for fast selectivity estimates. Delivers much lower planning overhead and consistently faster end-to-end JOB runtimes than prior work. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 400
Venue: CIDR
Year: 2021
Pagerank: 6.1079584e-05
Overall Rank: 4,526 | 68.55%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
3,886	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.6610704e-05
3,992	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5519369e-05
4,413	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.1989918e-05
5,931	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	5.2632167e-05
5,978	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	5.2424396e-05
6,967	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	4.875312e-05
7,118	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	4.8204951e-05
7,337	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7532633e-05
8,274	Galley: Modern Query Optimization for Sparse Tensor Programs	2025	SIGMOD	4.5392079e-05
9,387	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.341968e-05
9,662	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	4.3056334e-05
9,845	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	4.2680295e-05
9,868	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	4.2634472e-05
9,959	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	4.2254157e-05
10,540	SPECIAL: Synopsis Assisted Secure Collaborative Analytics	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
203	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034868567
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
1,104	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.0001398479
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,978	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8764627e-05
1,993	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8403548e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
6,372	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0878306e-05
8,345	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5361313e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
979	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014871114
3,476	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0560383e-05
388	Optimization of Large Join Queries	1988	SIGMOD	0.00024654816
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
11,710	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1905499e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05