APEX: Adaptive Variable-Wise Parallel Execution for Worst-Case Optimal Joins on Graph Queries

Graph queries are ubiquitous in graph databases and knowledge graphs, supporting applications such as recommender systems, question answering, and semantic search. In recent years, worst-case optimal join (WCOJ) algorithms play a critical role in evaluating graph queries. However, their practical performance is hindered by load imbalance in parallelization and poor execution order of join variables. In this paper, we propose APEX, Adaptive variable-wise Parallel EXecution for WCOJ on graph queries. First, APEX parallelizes the core intersection operations in Leapfrog Triejoin by materializing and organizing all intersection results for a variable at once. This is enabled by a candidate propagation graph, which captures dependencies among variables and their intersection results. Second, we further propose a reinforcement learning policy with a graph convolutional network encoder that selects the next variable based on query structure and runtime feedback. To accelerate lookups on the candidate propagation graph, we introduce two techniques: (i) dependency-source detection to prune the traversal space, and (ii) a Bloom filter to avoid redundant checks. Extensive experiments on diverse real-world and synthetic datasets demonstrate that APEX achieves up to $\mathbf{2. 4 2 - 5. 7 9} \boldsymbol{\times}$ speedup over state-of-the-art baselines.