# Learned Graph Rewriting with Equality Saturation: A New Paradigm in Relational Query Rewrite and Beyond

arXiv: https://arxiv.org/abs/2407.12794 · HTML: https://mlsanity.com/paper/2407.12794/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL training of language and agent models, one of 15 directions in Deep reinforcement learning methods.
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 19 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL training of language and agent models](https://mlsanity.com/deeprl/rl-training-of-language-and-agent-models/)

## Builds on (most cited first, 12 of 12)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Fundamentals of Recurrent Neural Network (RNN) and Long Short-Term Memory (LSTM) Network](https://mlsanity.com/paper/1808.03314/) (2018)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Equality Saturation for Tensor Graph Superoptimization](https://mlsanity.com/paper/2101.01332/) (2021)
- [Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources](https://mlsanity.com/paper/1802.10233/) (2018)
- [Plan-Structured Deep Neural Network Models for Query Performance Prediction](https://mlsanity.com/paper/1902.00132/) (2019)
- [Optimizing Recursive Queries with Program Synthesis](https://mlsanity.com/paper/2202.10390/) (2022)

## Built on by (most cited first, 3 of 3)

- [OCMDP: Observation-Constrained Markov Decision Process](https://mlsanity.com/paper/2411.07087/) (2024)
- [A Learned Cost Model-based Cross-engine Optimizer for SQL Workloads](https://mlsanity.com/paper/2506.02802/) (2025)
- [EGG-SR: Embedding Symbolic Equivalence into Symbolic Regression via Equality Graph](https://mlsanity.com/paper/2511.05849/) (2025)

## Abstract (arXiv)

Query rewrite systems perform graph substitutions using rewrite rules to generate optimal SQL query plans. Rewriting logical and physical relational query plans is proven to be an NP-hard sequential decision-making problem with a search space exponential in the number of rewrite rules. In this paper, we address the query rewrite problem by interleaving Equality Saturation and Graph Reinforcement Learning (RL). The proposed system, Aurora, rewrites relational queries by guiding Equality Saturation, a method from compiler literature to perform non-destructive graph rewriting, with a novel RL agent that embeds both the spatial structure of the query graph as well as the temporal dimension associated with the sequential construction of query plans. Our results show Graph Reinforcement Learning for non-destructive graph rewriting yields SQL plans orders of magnitude faster than existing equality saturation solvers, while also achieving competitive results against mainstream query optimisers.