Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores

Summary: SYA converts binary join plans into 2-phase Nested Semijoin Algebra (Lookup/Expand) plans and evaluates them by shredding in column stores to attain instance-optimal acyclic join evaluation. Provably avoids blowups and is no-regret vs binary plans; on 1,849 queries it speeds 85.3% up to 62.5x. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13889
Venue: VLDB
Year: 2025
Pagerank: 4.6010599e-05
Overall Rank: 8,034 | 44.11%
DOI: 10.14778/3742728.3742737

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,467	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7218691e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
8,718	Parachute: Single-Pass Bi-Directional Information Passing	2025	VLDB	4.4612599e-05
9,747	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	4.2897489e-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
60	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00064439773
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
185	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00036538405
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
735	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017452467
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011049779
1,783	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	0.00010568101
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,401	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8954126e-05
3,375	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD	7.1633324e-05
3,511	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.0254052e-05
4,465	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1604282e-05
6,056	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2321475e-05
6,340	Apache Arrow DataFusion: A Fast, Embeddable, Modular Analytic Query Engine	2024	SIGMOD	5.1051018e-05
6,658	Scalable Querying of Nested Data	2021	VLDB	4.9711629e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,988	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1945683e-05
5,576	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.426344e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
7,467	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7218691e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05