Abstract: An algorithm is instance-optimal if it has the best possible asymptotic run time for every input instance. Such an algorithm is essentially perfect in terms of computational complexity. Instance-optimal algorithms are exceedingly rare, yet one of the most fundamental operations in data analytics - the relational join - can be computed instance-optimally. In particular, a seminal algorithm by Yannakakis runs in time O(|IN|+|OUT|) for the class of acyclic join queries. Yet, no mainstream database system implements Yannakakis' algorithm, mainly due to its high constant overhead. In this talk, I will present recent breakthroughs to eliminate the overhead of Yannakakis' algorithm while retaining its optimality, paving the way for practical adoption. I will also summarize some new results on instance-optimal algorithms for generating query plans to guide the execution of Yannakakis' algorithm.

Bio: Remy Wang is an Assistant Professor at UCLA. His work on performance optimization of data processing systems has been recognized with numerous awards from conferences in both databases and programming languages, including SIGMOD, PODS, POPL, and OOPSLA. Most recently, he has been fascinated by beautiful algorithms developed by database theorists, and is working to make them more practical.