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: 13890
Venue: VLDB
Year: 2025
Pagerank: 4.5967078e-05
Overall Rank: 8,035 | 44.16%
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,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
8,711	Parachute: Single-Pass Bi-Directional Information Passing	2025	VLDB	4.4582346e-05
9,746	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	4.2856385e-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
59	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.0006445664
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
185	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00036529607
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
729	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017448059
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
1,334	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012543633
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
1,638	Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation	2022	VLDB	0.00011050093
1,781	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	0.00010557953
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,398	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8871067e-05
3,380	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD	7.1565855e-05
3,516	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.018912e-05
4,466	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1545841e-05
6,060	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2271244e-05
6,332	Apache Arrow DataFusion: A Fast, Embeddable, Modular Analytic Query Engine	2024	SIGMOD	5.1021765e-05
6,661	Scalable Querying of Nested Data	2021	VLDB	4.9663934e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,987	I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server	2026	CIDR	4.1905499e-05
5,582	Conjunctive Queries with Inequalities Under Updates	2018	VLDB	5.4211286e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
7,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05