A Learned Query Rewrite System using Monte Carlo Tree Search
1 minute read ∼ Filed in : A paper noteIntroduction
Query rewrite: transforms a SQL query into an equivalent one but with higher performance.
Challenges:
Order is important in rewriting, but there are huge numbers of orders.
- How to represent such a large amount of orders is a major challenge.
- Given a large search space, how to find the optimal order efficiently?
- How to estimate the cost reduction of a rewrite?
GAP:
Existing heuristics methods have limitations:
- it uses a pre-defined order to rewrite the queries and will fall in a local optimum.
- it is hard to effectively estimate the benefits of rewriting a query.
Solution
SQL query + a set of rewrite rules => LearnedRewrite => optimized rewritten query.
- policy tree -> represent the order search space
- Monte Carlo Tree Seach to explore the tree and find the optimal node.