Cómo construir un optimizador SQL con Egg y Rust

Un equipo de la comunidad RisingLight ha desarrollado un optimizador SQL didáctico en Rust utilizando el framework Egg, una biblioteca de reescritura de expresiones basada en equality saturation y e-graphs. El proyecto, disponible en el repositorio 'sql-optimizer-labs', contiene menos de mil líneas de código y, aun así, implementa técnicas clásicas de optimización: simplificación de expresiones, constant folding, predicate pushdown, column pruning, reordenación de joins y estimación de coste. Combina optimización basada en reglas (RBO) con optimización basada en coste (CBO) y es capaz de trabajar sobre consultas reales del benchmark TPC-H. El artículo describe paso a paso cómo definir el lenguaje SQL mediante el macro define_language de Egg —con nodos para valores, listas, operadores y nodos de plan (scan, proj, filter, join, agg, order, limit)— y cómo traducir una sentencia SELECT con joins, GROUP BY, HAVING, ORDER BY y LIMIT a su árbol de plan correspondiente en forma de S-expression. A continuación, explica cómo escribir reglas de reescritura con el macro rewrite! para casos representativos: simplificación algebraica (por ejemplo, (* ?a 2) → (<< ?a 1)), plegado de constantes, empuje de predicados, transformación a HashJoin, reordenación de joins y definición de una función de coste. Egg, creado por el grupo egraphs-good, sustenta su tecnología en el paper premiado como Distinguished Paper en POPL 2021 y permite a los desarrolladores prototipar optimizadores para lenguajes propios de forma flexible. Para quienes quieran profundizar, el código completo está en GitHub y el optimizador se integra con la base de datos RisingLight.