Learning to Optimize Join Queries With Deep Reinforcement Learning

08/09/2018
by   Sanjay Krishnan, et al.
0

Exhaustive enumeration of all possible join orders is often avoided, and most optimizers leverage heuristics to prune the search space. The design and implementation of heuristics are well-understood when the cost model is roughly linear, and we find that these heuristics can be significantly suboptimal when there are non-linearities in cost. Ideally, instead of a fixed heuristic, we would want a strategy to guide the search space in a more data-driven way---tailoring the search to a specific dataset and query workload. Recent work in deep reinforcement learning (Deep RL) may provide a new perspective on this problem. Deep RL poses sequential problems, like join optimization, as a series of 1-step prediction problems that can be learned from data. We present our deep RL-based DQ optimizer, which currently optimizes select-project-join blocks, and we evaluate DQ on the Join Order Benchmark. We found that DQ achieves plan costs within a factor of 2 of the optimal solution on all cost models and improves on the next best heuristic by up to 3×. Furthermore, DQ executes 10,000× faster than exhaustive enumeration and more than 10× faster than left/right-deep enumeration on the largest queries in the benchmark.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset