DQN-Guided Rule-Class Selection for Search-Based Query Rewriting

Abstract

Query rewrite transforms a SQL query into a semantically equivalent form expected to execute more efficiently. Search-based rewriters such as LearnedRewrite organize alternative rewrite orders as a policy tree and explore it with Monte Carlo Tree Search. In the publicly released LearnedRewrite implementation, expansion enumerates every applicable rule class at each search node, and each candidate triggers a rewrite execution and a PostgreSQL EXPLAIN call, making expansion a measurable contributor to rewrite latency.

This thesis formulates expansion-time rule-class selection as a state-dependent decision problem and proposes DQRS (DQN-Guided Rule-Class Selection), which ranks the legal rule classes at each state with a Deep Q-Network and forwards only the top k to the unchanged rewriter routine. On an in-domain workload derived from the TPC-H benchmark at k = 1, average rewrite latency falls from 15.3 ms to 4.0 ms and average policy-tree size from 9.9 to 2.4 nodes, reductions of about 74% and 76%. Average cost reduction is preserved while the median falls from 156 to 103, so the method exposes an explicit operating point on the efficiency–quality trade-off rather than dominating the baseline. Under an identical legal-action mask and at the same node count, learned ranking attains a median cost reduction of 103 against 13 for random selection. Transferred without retraining to a workload derived from the TPC-DS benchmark at k = 4, DQRS reduces latency by about 24% and node count by about 30% at unchanged cost reduction, but in this saturated regime it is not distinguishable from random selection.

The baseline throughout is the released implementation, which omits the learned cost estimator of the original paper, and all quality figures are optimizer-side estimates rather than measured execution time. Extending the evaluation from optimizer estimates to end-to-end execution time is the primary direction for future work.