## 3 Our Approach
### Reinforcement Learning for Join Order Optimization in SPARQL (ReJOOSp)  
While the number of tables in SQL is small, the number of predicates in SPARQL is very high. This is a significant difference in possible encoding for machine learning. In SQL, it is enough to say which tables should be joined. On the other hand, in SPARQL, the triple patterns must be explicitly connected, dramatically increasing the input size for machine learning and making it harder for the model to learn what is essential. Figure 4 shows an example query with two subject-subject joins and one subject-object join. A plausible approach would be to join the subject-subject joins independently from each other first. The assumption here is, that a subject-subject join is often a 1 to 1 join. Additionally, those joins can be evaluated independently. Afterward, both intermediate results are joined. Figure 4: Example SPARQL query. We use the Stable Baselines 3 [47] framework because there are many more open-source contributors than other frameworks. Especially, there is a community add-on [48] that extends the built-in PPO model with the possibility of masking. Applying masks to the available actions is crucial for the model to produce good join trees. We use the default MLP policy with two layers and 64 nodes, also used in other join order optimizing articles [49]. Using more layers increases the number of learning steps required since the model must first learn how to use these hidden layers. We need to keep the training phase short. Otherwise, the changes in the dataset will immediately render the newly trained model useless. We want to treat the machine learning model as a black box. This allows us to focus on encoding the query and computing a reward. The reward should reflect the quality of the join tree compared to other previously executed join trees. Therefore, the algorithm needs to know the best and worst case. Calculating the reward for joins with up to five inputs is straightforward, as traversing all join trees and keeping statistics on the good and the bad is possible. However, since the model is intended to work with larger joins, for example, with 20 join inputs, this approach will not work, as it is impossible to collect statistics on all possible join trees. To solve this problem, we extend the machine learning pipeline to the concept shown in Figure 5.  
The default optimizer is initially used to initialize the statistics for each SPARQL query. These statistics only map the query to the total network traffic volume. These statistics do not contain specific join orders. Consequently, the model could not learn the competitor's  
Figure 5: Machine learning concept. The blue component uses an external SQL DBMS. The red components are executed within Lupsodate3000. The white components are implemented in Python. strategies. Furthermore, whenever we calculate a new reward during training, we extend these statistics with the number of intermediate results produced by the current join plan. All of these statistics about queries and their generated intermediate result counts are stored in a separate SQL DBMS. These statistics will continually improve as the model is trained. The reward calculation function can be seen in Figure 6. The variables \(v_{max}\) and \(v_{min}\) refer to the min and max network traffic for this specific query, while \(v_{current}\) refers to the traffic for the current join plan. Even if the actual best and worst case is unknown, this estimation is good enough to train the model. \[r= \begin{cases}0&\text{if }v_{max}=v_{min}\\ -10&\text{if }v_{current}=null\\ min\Big{(}10,-\log\Big{(}\frac{v_{current}-v_{min}}{v_{max}-v_{min}}\Big{)} \Big{)}&\text{otherwise}\end{cases} \]  
A logarithmic reward function and a minimum compensate for the potentially high variation between different join trees. We generally want to reward good join trees and penalize those whose intermediate results are very high, or the DBMS decides to abort our benchmark because it takes too long.