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

• URL: http://arxiv.org/abs/2407.12794v1
• Date: Wed, 19 Jun 2024 21:11:19 GMT
• Title: Learned Graph Rewriting with Equality Saturation: A New Paradigm in Relational Query Rewrite and Beyond
• Authors: George-Octavian Bărbulescu, Taiyi Wang, Zak Singh, Eiko Yoneki,
• Abstract summary: Rewriting logical and physical relational query plans is proven to be an NP-hard sequential decision-making problem. In this paper, we address the query rewrite problem by interleaving Equality Saturation and Graph Reinforcement Learning.
• Score: 0.3749861135832073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Adaptive Query Rewriting: Aligning Rewriters through Marginal Probability of Conversational Answers [66.55612528039894]
  AdaQR is a framework for training query rewriting models with limited rewrite annotations from seed datasets and completely no passage label. A novel approach is proposed to assess retriever's preference for these candidates by the probability of answers conditioned on the conversational query.
  arXiv  Detail & Related papers  (2024-06-16T16:09:05Z)
• RaFe: Ranking Feedback Improves Query Rewriting for RAG [83.24385658573198]
  We propose a framework for training query rewriting models free of annotations. By leveraging a publicly available reranker, oursprovides feedback aligned well with the rewriting objectives.
  arXiv  Detail & Related papers  (2024-05-23T11:00:19Z)
• LLM-R2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency [65.01402723259098]
  We propose a novel method of query rewrite named LLM-R2, adopting a large language model (LLM) to propose possible rewrite rules for a database rewrite system. Experimental results have shown that our method can significantly improve the query execution efficiency and outperform the baseline methods.
  arXiv  Detail & Related papers  (2024-04-19T13:17:07Z)
• Enhancing Conversational Search: Large Language Model-Aided Informative Query Rewriting [42.35788605017555]
  We propose utilizing large language models (LLMs) as query rewriters. We define four essential properties for well-formed rewrites and incorporate all of them into the instruction. We introduce the role of rewrite editors for LLMs when initial query rewrites are available, forming a "rewrite-then-edit" process.
  arXiv  Detail & Related papers  (2023-10-15T03:04:17Z)
• Doc2SoarGraph: Discrete Reasoning over Visually-Rich Table-Text Documents via Semantic-Oriented Hierarchical Graphs [79.0426838808629]
  We propose TAT-DQA, i.e. to answer the question over a visually-rich table-text document. Specifically, we propose a novel Doc2SoarGraph framework with enhanced discrete reasoning capability. We conduct extensive experiments on TAT-DQA dataset, and the results show that our proposed framework outperforms the best baseline model by 17.73% and 16.91% in terms of Exact Match (EM) and F1 score respectively on the test set.
  arXiv  Detail & Related papers  (2023-05-03T07:30:32Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• Better Query Graph Selection for Knowledge Base Question Answering [2.367061689316429]
  This paper presents a novel approach based on semantic parsing to improve the performance of Knowledge Base Question Answering (KBQA) Specifically, we focus on how to select an optimal query graph from a candidate set so as to retrieve the answer from knowledge base (KB)
  arXiv  Detail & Related papers  (2022-04-27T01:53:06Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions over Knowledge Graph [16.26384829957165]
  We propose a new two-stage approach to build query graphs. In the first stage, the top-$k$ related instances are collected by simple strategies. In the second stage, a graph generation model performs hierarchical generation.
  arXiv  Detail & Related papers  (2021-11-01T07:08:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.