Instance-Optimal Acyclic Joins: From Theory to Systems

Abstract

This tutorial revisits Yannakakis algorithm (YA) as a central example of how database theory can guide practical query processing. Yannakakis algorithm gives an instance-optimal guarantee for evaluating acyclic joins, and its core ideas, including join trees, semijoin reduction, and information passing, have influenced decades of work in query evaluation. Recent studies have renewed interest in the Yannakakis algorithm by demonstrating that its structure-aware principles can be applied to modern database systems, yielding practical methods for robust SQL analytics. This tutorial introduces the foundations of the Yannakakis algorithm and acyclic query processing, surveys recent advances in theory and systems, and discusses how these ideas extend to query optimization and general queries beyond the multi-way joins. The goal is to give the audience both a clear conceptual understanding of Yannakakis algorithm and a broad view of its growing role in modern data management.