Learned Graph Rewriting with Equality Saturation: A New Paradigm in Relational Query Rewrite and Beyond
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909260471861248 |
|---|---|
| author | Bărbulescu, George-Octavian Wang, Taiyi Singh, Zak Yoneki, Eiko |
| author_facet | Bărbulescu, George-Octavian Wang, Taiyi Singh, Zak Yoneki, Eiko |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12794 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learned Graph Rewriting with Equality Saturation: A New Paradigm in Relational Query Rewrite and Beyond Bărbulescu, George-Octavian Wang, Taiyi Singh, Zak Yoneki, Eiko Databases Machine Learning 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. |
| title | Learned Graph Rewriting with Equality Saturation: A New Paradigm in Relational Query Rewrite and Beyond |
| topic | Databases Machine Learning |
| url | https://arxiv.org/abs/2407.12794 |