Database Theory + X: Search-based Program Optimization

@article{db-x-egg,
    author = {
      Zhang, Yihong and
      Suciu, Dan and
      Wang, Yisu Remy and 
      Willsey, Max
    },
    title = {Database Theory + X: Search-based Program Optimization},
    year = {2024},
}

Recent work in programming languages developed an approach to term rewritings based on equality saturation (EqSat), which, instead of applying destructively the rewrite rules, maintains all equivalent expressions in a structure called an E-graph. This paper describes two surprising connections between EqSat and databases, going both ways. On one hand equality saturation can be viewed as a query evaluation problem, with great benefits. On the other hand, most sophisticated SQL query optimizers are based on the Volcano/Cascades framework which, we explain, is a variant of EqSat.