How to design a Meta-Algorithm that designs algorithms

Database engines today are expected to be able to solve a wide variety of advanced problems about the data they store. A user issues a query to the engine describing some problem they would like to solve. The query optimizer is the key component of the engine whose job is to design an efficient algorithm for this particular problem, described as a “query plan”. The ultimate goal of query optimization is for the optimizer to become a “meta-algorithm” that can automatically design an optimal algorithm for any given problem.

In this talk, we describe two lines of work taking small steps towards the above goal. In the first line of work, we develop such a meta-algorithm for a common class of queries that subsumes graph pattern matching and CSP among other problems. We show that our meta-algorithm, despite its generality, subsumes known algorithms in the literature that were tailored to specific queries and also discovers new algorithms. In the second line of work, we present a different kind of meta-algorithm: one that is “templated” by some algebraic abstraction. This allows us to instantiate this meta-algorithm into different algorithms for different problems spanning databases, logic, linear algebra, and probabilistic graphical models, among other application domains.