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.1135504e-05
Overall Rank: 4,523 | 68.54%
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,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
3,885	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.6674822e-05
3,990	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5581983e-05
4,417	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.2037371e-05
5,930	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	5.2682075e-05
5,972	SafeBound: A Practical System for Generating Cardinality Bounds	2023	SIGMOD	5.2474768e-05
6,969	LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences	2025	SIGMOD	4.8799937e-05
7,123	ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation	2024	SIGMOD	4.8251036e-05
7,344	Join Size Bounds using l_p-Norms on Degree Sequences	2024	PODS	4.7565607e-05
8,279	Galley: Modern Query Optimization for Sparse Tensor Programs	2025	SIGMOD	4.5435639e-05
9,380	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	4.3461329e-05
9,662	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	4.3097631e-05
9,845	Path-centric Cardinality Estimation for Subgraph Matching	2025	VLDB	4.2721228e-05
9,869	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	4.2675361e-05
9,960	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	4.2294678e-05
10,531	SPECIAL: Synopsis Assisted Secure Collaborative Analytics	2025	VLDB	4.1945683e-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.00059038975
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
1,105	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00013990395
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,981	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8687545e-05
1,989	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8478437e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
6,374	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0927058e-05
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
3,474	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0625972e-05
387	Optimization of Large Join Queries	1988	SIGMOD	0.0002471967
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
11,705	Improving Join Reorderability with Compensation Operators	2018	SIGMOD	4.1945683e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05