Research on Deep Reinforcement Learning-Based Multi-Table Join Order Selection

Abstract

This paper presents a comprehensive survey of join order selection (JOS) in database query optimization, with a particular focus on deep reinforcement learning (DRL)-based approaches. By synthesizing representative systems such as Google Balsa and Microsoft Adaptive Query Processing, we characterize current trends and open challenges in reinforcement learning-driven query optimization. We formulate the multi-way join ordering problem as a Markov Decision Process (MDP) and systematically compare key design dimensions, including state representation (e.g., graph neural networks versus vectorized statistical features), action space design (e.g., join pair selection versus join subtree expansion), and reward function design (e.g., sparse versus intermediate rewards), analyzing their impacts on optimization outcomes. For multi-objective optimization, we survey strategies such as Pareto optimization and scalarization, highlighting their effectiveness in balancing query latency reduction with resource consumption and execution stability. To enhance model generalization, we examine the roles of curriculum learning and meta-learning in improving sample efficiency and robustness across heterogeneous workloads. In addition, we categorize hybrid architectures that integrate DRL with traditional cost-based optimizers (CBOs), including designs where DRL functions as a query rewriter, a search-space guide for plan enumeration, or a post-optimization validator. Finally, extensive empirical evaluations on standard benchmarks such as TPC-H and the Join Order Benchmark (JOB) demonstrate that DRL-based methods can outperform classical optimizers, particularly for complex queries with large search spaces.