CSE Colloquium – Query Optimization: How to design a Meta-Algorithm that designs Algorithms?

Presenter: Mahmoud Abo Khamis, RelationalAI

Abstract:

Database systems have evolved from simple bookkeeping tools to comprehensive data analytics platforms capable of learning from the data and making business decisions. As a result, database queries expanded in their expressive power and applications to include tensor computations, constraint satisfaction problems, graph analytics, scientific computing, SAT solving, among others. This puts a lot of pressure on modern query optimizers to rise up to the occasion and produce efficient query plans for a wide variety of very complex queries that describe problems in different domains. The ultimate goal of query optimization is for the query optimizer to become a “meta-algorithm” where you can feed in any problem definition and get back an efficient algorithm for this particular problem.

In this talk, we describe two related frameworks for query optimization that aim to take us one step in the direction of the above goal. The first framework is based on information theory. It uses information theory to get provably accurate cost estimates for query plans and to find the best query plan. Among other applications, this framework currently achieves the best known complexity for graph pattern matching problems, thus subsuming and generalizing known results in this area, where, for decades, algorithms used to be designed by hand for specific graph patterns. The second framework is based on algebra. It uses algebraic abstractions to unify and generalize algorithms across different domains, in the same way template programming allows for reusing code across different applications.

Bio:

Mahmoud Abo Khamis is a Senior Computer Scientist at RelationalAI, where he has worked since 2017. He received his Ph.D. in Computer Science and Engineering from the State University of New York at Buffalo in 2016. Prior to joining RelationalAI, he was a Senior Database Engineer at Infor from 2015 to 2017. His research interests include database systems and theory, in-database machine learning, query optimization and evaluation, information theory, and beyond worst-case analysis. His work has been recognized with two Test-of-Time Awards at ACM PODS 2025 and 2026, three Best Paper Awards at ACM SIGMOD 2025 and ACM PODS 2022 and 2016, three ACM SIGMOD Research Highlight Awards, and the 2016 Best CSE Dissertation Award from SUNY Buffalo. His work has also received multiple invitations to the Journal of the ACM, ACM STOC, and ACM TODS. He is on the Editorial Board of ACM TODS, and serves on the program committees of ACM PODS, ICDT, and ICALP among others.

Hosted by: Professor Nikos Tziavelis

Location: Engineering 2, Room E2-180 (*Refreshments such as coffee, tea, pastries, and fresh fruit will be provided in-person.)

Zoom: https://ucsc.zoom.us/j/93445911992?pwd=YkJ2TQtF79h0PcNXbEcpZLbpK0coiY.1&jst=3