3 papers
cs.DB2026
Database Theory in Action: Yannakakis' Algorithm
Paraschos Koutris, Stijn Vansummeren, Qichen Wang +2
Yannakakis' seminal algorithm is optimal for acyclic joins, yet it has not been widely adopted due to its poor performance in practice. This paper briefly surveys recent advancemen…
cs.DB2026
Algorithms for Optimizing Acyclic Queries
Zheng Luo, Wim Van den Broeck, Guy Van den Broeck +1
Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically opt…
cs.DB2025
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores
Liese Bekkers, Frank Neven, Stijn Vansummeren +1
Acyclic join queries can be evaluated instance-optimally using Yannakakis' algorithm, which avoids needlessly large intermediate results through semi-join passes. Recent work propo…