Lune

ICDE2026Top-tier venue

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

Yipeng Liu, Yuming Lin, Zhicheng Pan, Chengcheng Yang, You Li, Aoying Zhou

Abstract

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 2.42−5.79×\mathbf{2. 4 2 - 5. 7 9} \boldsymbol{\times} speedup over state-of-the-art baselines.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement LearningJunxiong Wang, Immanuel Trummer, Ahmet Kara, Dan OlteanuVLDB 2023 · 10 citations
  2. Worst-Case-Optimal Similarity Joins on Graph DatabasesDiego Arroyuelo, Benjamin Bustos, Adrián Gómez-Brandón, Aidan Hogan et al.SIGMOD 2024 · 3 citations
  3. Worst-Case Optimal BGPs on Temporal GraphsDiego Arroyuelo, Aidan Hogan, Gonzalo Navarro, Juan L. ReutterVLDB 2026
  4. R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query OptimizationMin Shi, Peng Peng, Xin Xiao, Lei Zou et al.SIGMOD 2026
  5. Efficient Join Order Selection Learning with Graph-based RepresentationJin Chen, Guanyu Ye, Yan Zhao, Shuncheng Liu et al.KDD 2022 · 27 citations
Dusk over the sea between two cliffs drawn in fine vertical lines