ACJoin: A Low-Latency Multi-Table Join Order Selection Model With Minimum Cost Using Asynchronous Advantage Actor-Critic

Join order selection is one of the most challenging problems in query optimization and plays an essential role in providing high query performance in Big Data management. Currently, researchers have applied deep reinforcement learning methods, for example, Rejoin and DQ, to join order selection in order to obtain high query performance. However, Rejoin and DQ cannot capture the structural characteristic of the join tree, which may lead to similar encoding structure for different execution plans. To tackle these challenges, we propose a new learning optimizer called ACJoin (asynchronous advantage Actor-Critic for multi-table Join order selection). ACJoin employs a new encoding method to capture the structural characteristics of the join tree through integrating GRU (Gated Recurrent Unit). In particular, ACJoin can distinguish different execution plans. It uses A3C (Asynchronous Advantage Actor-Critic) to guide the join order selection and reduce the time taken to find the best query plan with the minimum cost. Compared with existing search strategies, ACJoin can find the globally optimal solution with efficient and stable query performance. Extensive experiments are conducted on the real JOB and the synthetic TPC-H datasets. The results show that ACJoin outperforms the state-of-the-art join order selection methods and DRL Deep Reinforcement Learning)-based methods in cost and latency.