Reinforcement Learning for Join Order Optimization in PostgreSQL: Query Rewriting and Evaluation on JOB and TPC-H Benchmarks

Abstract

Join order optimization is a critical combinatorial problem in query processing. This paper applies reinforcement learning (RL) techniques to the join order optimization task in PostgreSQL by implementing and evaluating three separate RL-based optimizers: Proximal Policy Optimization (PPO), Deep Q-Network (DQN), and Advantage Actor-Critic (A2C). Each method is trained on the Join Order Benchmark (JOB) and evaluated on both JOB and TPC-H workloads. Performance is compared against PostgreSQL’s default planner without join reordering (PG-Old) and the built-in PostgreSQL optimizer with reordering enabled (PG-Join). Results show that RL-based methods significantly reduce execution times compared to PG-Old and often perform on par with or better than PG-Join, especially for complex multi-join queries. Among the tested methods, PPO achieves the most consistent improvements, with up to 4.47× average speedup over PG-Old on JOB and measurable gains on TPC-H. These findings demonstrate the potential of reinforcement learning as a practical and adaptive approach to join order optimization in relational databases.