Treffer: Database Theory in Action: Search-Based Program Optimization
Title:
Database Theory in Action: Search-Based Program Optimization
Authors:
Contributors:
Yihong Zhang and Dan Suciu and Yisu Remy Wang and Max Willsey
Publisher Information:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publication Year:
2025
Collection:
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics )
Subject Terms:
Document Type:
Fachzeitschrift
article in journal/newspaper<br />conference object
File Description:
application/pdf
Language:
English
Relation:
Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.34
DOI:
10.4230/LIPIcs.ICDT.2025.34
Availability:
Accession Number:
edsbas.83512730
Database:
BASE
Weitere Informationen
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.