Deep Reinforcement Learning for Join Order Enumeration
This addresses query performance issues for database systems, but it is incremental as it adapts existing techniques to a specific domain.
The paper tackles the problem of join order selection in query optimization by applying deep reinforcement learning to enable learning from feedback, resulting in a proof-of-concept system that matches or outperforms PostgreSQL in plan quality and efficiency.
Join order selection plays a significant role in query performance. However, modern query optimizers typically employ static join enumeration algorithms that do not receive any feedback about the quality of the resulting plan. Hence, optimizers often repeatedly choose the same bad plan, as they do not have a mechanism for "learning from their mistakes". In this paper, we argue that existing deep reinforcement learning techniques can be applied to address this challenge. These techniques, powered by artificial neural networks, can automatically improve decision making by incorporating feedback from their successes and failures. Towards this goal, we present ReJOIN, a proof-of-concept join enumerator, and present preliminary results indicating that ReJOIN can match or outperform the PostgreSQL optimizer in terms of plan quality and join enumeration efficiency.