mlsanityData to 14 Oct 2026

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

arXiv 2407.12794 ↗First posted 19 Jun 2024cs.DB cs.LGcited by 3

On the map: Deep reinforcement learning methods → RL training of language and agent models

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.

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.

Builds on

12 of 36 references.

References · 12

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  5. 2018Fundamentals of Recurrent Neural Network (RNN) and Long Short-Term Memory (LSTM) Networkcited by 420
  6. 2018Human-level performance in first-person multiplayer games with population-based deep reinforcement learningcited by 264
  7. 2019Neo: A Learned Query Optimizercited by 80
  8. 2019An End-to-End Learning-based Cost Estimatorcited by 43
  9. 2021Equality Saturation for Tensor Graph Superoptimizationcited by 27
  10. 2018Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sourcescited by 25
  11. 2019Plan-Structured Deep Neural Network Models for Query Performance Predictioncited by 24
  12. 2022Optimizing Recursive Queries with Program Synthesiscited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 2.

3 papers.

  1. 2024OCMDP: Observation-Constrained Markov Decision Processcited by 2
  2. 2025A Learned Cost Model-based Cross-engine Optimizer for SQL Workloadscited by 2
  3. 2025EGG-SR: Embedding Symbolic Equivalence into Symbolic Regression via Equality Graphcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2025E3-Rewrite: Learning to Rewrite SQL for Executability, Equivalence,and Efficiency
  2. 2026RELOAD: A Robust and Efficient Learned Query Optimizer for Database Systems
  3. 2026Rewrite What Matters: Adaptive Multilingual Query Rewriting for Reasoning via Agentic Reinforcement Learning
  4. 2025Graph-Reward-SQL: Execution-Free Reinforcement Learning for Text-to-SQL via Graph Matching and Stepwise Reward
  5. 2025QUITE: A Query Rewrite System Beyond Rules with LLM Agents
  6. 2025STRuCT-LLM: Unifying Tabular and Graph Reasoning with Reinforcement Learning for Semantic Parsing
  7. 2026ReToolSQL: Agentic Reinforcement Learning for Robust Text-to-SQL
  8. 2026LLM-Guided Strategy Synthesis for Scalable Equality Saturation