Sub-optimal Join Order Identification with L1-error

Summary: Introduces L1-error, a permutation distance over subplan cardinalities with the same join count, weighting errors by magnitude and prioritizing small multi-way joins. Used within a standard decision tree, L1-error accurately identifies sub-optimal plans across four benchmarks, with gains when combined with Q-error as a low-overhead composite feature. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6827
Venue: SIGMOD
Year: 2024
Pagerank: 4.1905499e-05
Overall Rank: 10,945 | 23.94%
DOI: 10.1145/3639272

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 26 of 26 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
203	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034868567
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
606	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019251186
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
752	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00017138049
782	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016665859
905	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423174
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459
1,344	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012477274
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011050093
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,825	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010392367
2,053	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.682841e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,769	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1512848e-05
2,778	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1345892e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
2,937	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	7.8552033e-05
2,971	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7935535e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9291549e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
3,455	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0760196e-05
2,080	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5954034e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
3,992	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5519369e-05
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011050093
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482