ReJOOSp: Reinforcement Learning for Join Order Optimization in SPARQL

Abstract

The choice of a good join order plays an important role in the query performance of databases. However, determining the best join order is known to be an NP-hard problem with exponential growth with the number of joins. Because of this, nonlearning approaches to join order optimization have a longer optimization and execution time. In comparison, the models of machine learning, once trained, can construct optimized query plans very quickly. Several efforts have applied machine learning to optimize join order for SQL queries outperforming traditional approaches. In this work, we suggest a reinforcement learning technique for join optimization for SPARQL queries, ReJOOSp. SPARQL queries typically contain a much higher number of joins than SQL queries and so are more difficult to optimize. To evaluate ReJOOSp, we further develop a join order optimizer based on ReJOOSp and integrate it into the Semantic Web DBMS Luposdate3000. The evaluation of ReJOOSp shows its capability to significantly enhance query performance by achieving high-quality execution plans for a substantial portion of queries across synthetic and real-world datasets.

Keywords

• Semantic Web database
• SPARQL query optimization
• join order optimization
• deep learning
• reinforcement learning