Deep Reinforcement Learning for Join Order Enumeration

Join order selection plays a significant role in query performance. However, modern query optimizers typically employ static join order enumeration algorithms that do not incorporate feedback about the quality of the resulting plan. Hence, optimizers often repeatedly choose the same bad plan, as they have no mechanism for "learning from their mistakes." Here, we argue that deep reinforcement learning techniques can be applied to address this challenge. These techniques, powered by artificial neural networks, can automatically improve optimizer decision-making by incorporating feedback. Towards this goal, we present ReJOIN, a proof-of-concept join enumerator, as well as preliminary results indicating that ReJOIN can match or outperform the PostgreSQL optimizer in terms of plan quality and join enumeration efficiency.