AlphaJoin: Join Order Selection à la AlphaGo


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. Inspired by the success of ‘AlphaGo’ for the game of Go, in this paper, we propose an optimization approach refered to as ‘AlphaJoin’, which applies AlphaGo’s techniques, namely Monte Carlo Tree Search, to the join order selection problem. Preliminary results indicate that our approach consistently outperforms a state-of-the-art method and the PostgreSQL’s optimizer on its own respective execution engine.

PhD workshop at VLDB