"What is New in Join-Aggregate Query Processing?"

by Xiao Hu

Abstract: 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 will present the first combinatorial algorithm that improves Yannakakis for computing acyclic join-aggregate queries. Moreover, this algorithm is proven 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.

Xiao Hu is an Assistant Professor in the David R. Cheriton School of Computer Science at the University of Waterloo. Her research focuses on foundational query processing in data management, specifically addressing modern challenges driven by emerging data characteristics -- such as large-volume, high-speed, private, and high-dimensional data -- and evolving computing architectures like parallel and distributed systems and GPUs. Her contributions to the field have been recognized with the ACM PODS Best Paper Award 2025, the ICDT Best Paper Award 2024, and the ACM SIGMOD Best Paper Honorable Mention 2024, alongside multiple PODS Distinguished Paper Awards (2024 and 2025) and ACM SIGMOD Research Highlight Awards (2025 and 2026).