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: 6826
Venue: SIGMOD
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,942 | 23.88%
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.0040449103
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
608	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019235898
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
758	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.0001706608
784	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016675823
910	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423056
1,254	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013027411
1,341	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012486285
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,826	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010400425
2,050	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.6886663e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,762	FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation	2021	VLDB	8.1585394e-05
2,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
2,785	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1286814e-05
2,969	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7974762e-05
2,985	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	7.7795847e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
5,880	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2898074e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9338479e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
3,449	Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation	2022	VLDB	7.0824319e-05
2,083	Towards a Learning Optimizer for Shared Clouds	2019	VLDB	9.5834572e-05
2,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
3,990	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5581983e-05
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975