Exploring Monte Carlo Tree Search for Join Order Selection

Abstract

Query optimization remains a difficult problem, and existing database management systems (DBMSs) often miss good execution plans. Identifying an efficient join order is key to achieving good performance in database systems. A primary challenge in join order selection is enumerating a set of candidate orderings and identifying the most effective ordering. Searching in larger candidate spaces increases the potential of finding well working plans, but also increases the cost of query optimization. In this paper, we explore the benefits of Monte Carlo Tree Search (MCTS) for the join order selection problem. MCTS is a search method usually used in games to predict the set of moves that should be taken to reach a final winning solution with high likelihood. It simulates the game many times and tries to predict the most promising move based on the simulation results. For example, in the game of Go, MCTS simulates the game several times to select the actions and orders which have the highest probability to win. Inspired by this method, we explore the application of MCTS to join order selection. Our main idea is to simulate many possible join orders, and to apply MCTS to select the order to execute with the highest estimated performance. We design a neural network to predict the query execution time of a given plan, to which we refer as Order Value Network (OVN). MCTS leverages this network to score candidate query plans.

Publication
North East Database Day
Date
Links