Database Theory in Action: Search-based Program Optimization

@article{Zhang2025dbx-egg,
  title={Database Theory in Action: Search-Based Program Optimization},
  author={Zhang, Yihong and Suciu, Dan and Wang, Yisu Remy and Willsey, Max},
  booktitle={28th International Conference on Database Theory (ICDT 2025)},
  pages={34--1},
  year={2025},
  organization={Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}
}

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.