Conference PaperDatabase Theory in Action: Search-Based Program OptimizationZhang, Yihong; Suciu, Dan; Wang, Yisu Remy; Willsey, MaxRoy, Sudeepa; Kara, AhmetRecent 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.Schloss Dagstuhl – Leibniz-Zentrum für Informatik2025-01-011062711432834:1-34:61868-8969978-3-95977-364-5https://doi.org/10.4230/LIPICS.ICDT.2025.342312195Query optimizationprogram optimizationCascades frameworkequality saturationDatalogTheory of computation → Equational logic and rewritingTheory of computation → Database query processing and optimization (theory)6 pages793211 bytesapplication/pdfCreative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccessNational Science Foundation