What is New in Join-Aggregate Query Processing?

Join-aggregate queries defined over commutative semirings subsume a wide variety of common algorithmic problems, such as graph pattern matching, graph colorability, matrix multiplication, and constraint satisfaction problems. Developing efficient algorithms for computing join-aggregate queries in the conventional RAM model has been a holy grail in database theory. One of the most celebrated results in this area is the Yannakakis algorithm dating back to 1981. Despite its prominence as a textbook solution, no improvements in its complexity have been made over the past 40 years.

In this talk, I review the latest advancement for join-aggregate query processing that has been inspired or initialized by the Simons program in Fall 2023. I will introduce the first algorithm that improves upon Yannakakis for computing acyclic join-aggregate queries and is proved to be output-optimal among all combinatorial algorithms. One application is an output-optimal algorithm for chain matrix multiplication over sparse matrices. Beyond combinatorial algorithms, I will also show how fast matrix multiplication can further speed up the processing of conjunctive queries, a critical subclass of join-aggregate queries.  Finally, I will highlight a few interesting open problems in this area.