A Learned Query Rewrite System using Monte Carlo Tree Search

Query rewrite transforms a SQL query into an equivalent one but with higher performance.

Existing problems

• How to represent the large search space or rewrite order.
• how to define the order? The order of applying different rewrite rules significantly affects the query performance.
• How to estimate the cost reduction of a rewrite? Rewriting rules functions differently for different queries.

This paper propose a query rewritten system, which accept (query + rewrite rules) => optimal rewrite order + query

• Model possible orders as a policy tree, root = input query. path = an rewritten order.
• Note utility:
  • cost between latency of executing original and current node + access pattern.
• Monte Carlo Tree Search to explore the policy tree to find the optimal node
• Cost estimation
  • M_R[i,j]: cost reduction of applying rule j to operator i
  • Q_C[i,j]: operator i contains columsn j
  • M_R[i,j]: index, distinct value

---

• ← Previous Post
• Next Post →