Technical Summary: Gradient-Based Join Ordering (GBJO)

Problem Statement

Join ordering is a fundamental, NP-hard problem in database query optimization, requiring the selection of the most efficient sequence to evaluate joins (binary operators) within a query. The performance of query execution is critically dependent on this choice; suboptimal ordering can lead to impractically long delays, while optimal ordering can result in instantaneous responses.

Traditionally, this problem is modeled as a discrete combinatorial search over the space of binary tree plans, guided by a cost model. However, existing approaches face a trade-off between effectiveness and efficiency:

• Exhaustive methods (e.g., Dynamic Programming) guarantee optimality for specific cost models but suffer from exponential or factorial time complexity, making them intractable for large queries.
• Heuristic methods (e.g., Greedy Search, Iterative Improvement, Genetic Algorithms) are computationally efficient but often converge to suboptimal local minima.
• Learned approaches using Reinforcement Learning (RL) have shown promise but suffer from sample inefficiency and unstable convergence dynamics.

Methodology

The paper proposes Gradient-Based Join Ordering (GBJO), a novel approach that reformulates the discrete join ordering problem as a continuous optimization problem. This is achieved by relaxing the discrete search space into a differentiable domain, allowing the use of gradient descent to minimize query cost.

1. Continuous Relaxation of Plan Space

Instead of representing a query plan as a discrete binary adjacency matrix $A \in \{0, 1\}^{N \times N}$, GBJO relaxes this into a continuous "soft" adjacency matrix $A_{soft}$.

• Logit Matrix: A real-valued logit matrix $L$ is introduced.
• Softmax Transformation: Edge probabilities are derived via a softmax function with a temperature parameter $\tau$:
  $$A_{soft, ij} = \frac{\exp(L_{ij}/\tau)}{\sum_k \exp(L_{ik}/\tau)}$$
• Annealing: The temperature $\tau$ is linearly annealed from an initial high value to a minimum value ($\tau_{min} \to 0$) over optimization steps. This allows for broad exploration early in the process and forces convergence toward binary (discrete) values in later stages.

2. Differentiable Cost Model

The approach utilizes a Graph Neural Network (GNN) as the cost model ($\hat{C}_\theta$).

• The GNN takes the query structure and the soft adjacency matrix as input to predict the execution cost.
• Unlike traditional statistical estimators, the GNN is differentiable, enabling the backpropagation of cost gradients with respect to the plan structure ($L$).
• The model is trained on valid discrete plans to predict the $C_{out}$ cost (output cardinality plus recursive costs of children).

3. Structural Constraints via Differentiable Penalties

Optimizing the cost alone in the continuous space leads to invalid plans (e.g., cycles, disconnected graphs). To ensure validity, the objective function includes differentiable penalty terms that vanish only when the plan satisfies structural constraints:

• Degree Constraints ($P_{TO}, P_{JI}, P_{JO}$): Enforce that triple-pattern nodes have exactly one outgoing edge, join nodes have two incoming and one outgoing edge, and the root has no outgoing edges.
• Left-Linearity ($P_{LL}$): Enforces a specific tree structure (optional, but used in experiments) where join nodes have specific child configurations.
• Acyclicity ($P_{ACYC}$): Uses a trace-based penalty ($\text{tr}(e^{A_{soft}}) - N$) to suppress cycles, ensuring the graph is a Directed Acyclic Graph (DAG).

4. Optimization Objective

The final objective function $L_t$ combines the predicted cost and the weighted structural penalties:
$$L_t = \hat{C}_\theta(X, A_{soft}) + \lambda(t) P_{STRUCT}$$

• The penalty weight $\lambda(t)$ is nonlinearly increased over time to allow unconstrained exploration initially and enforce validity at the end.
• The optimization is performed using Gradient Descent with Nesterov momentum and a One-Cycle Learning Rate schedule.

5. Projection to Discrete Plan

After optimization, the resulting soft matrix $A_{soft}$ is projected back to a valid discrete plan using a greedy search algorithm that selects the highest-probability edges to form a valid left-linear tree.

Key Contributions

1. Novel Gradient-Based Method: The paper introduces the first gradient-based approach for join ordering that operates on a continuous relaxation of the discrete search space, utilizing learned GNN cost models.
2. Differentiable Constraints: It demonstrates how to enforce complex structural validity constraints (tree topology, acyclicity) using differentiable penalties, enabling end-to-end gradient-based search.
3. Empirical Superiority: The method is shown to find plans with costs comparable to or lower than traditional discrete search methods (Dynamic Programming, Greedy, Genetic Algorithms) and other continuous baselines (NeuralSort, CMA-ES).
4. Scalability: The approach exhibits better runtime scaling than many classic discrete algorithms, requiring significantly fewer cost model evaluations (e.g., 10 iterations vs. hundreds for randomized baselines).

Experimental Results

The authors evaluated GBJO on two datasets: LUBM (synthetic, structured) and Wikidata (complex, heterogeneous), using star- and path-shaped queries.

• Cost Model Accuracy: The GNN cost model achieved low median Q-errors (ranging from 1.07 to 2.34) across datasets, indicating accurate cost estimation.
• Plan Quality:
  • GBJO matched or surpassed the median true costs of discrete search methods (including Dynamic Programming and Genetic Search) across various query sizes.
  • For large query sizes, GBJO found plans with costs several orders of magnitude lower than random plans.
  • GBJO outperformed other continuous optimization methods (NeuralSort and CMA-ES), suggesting that the specific combination of temperature annealing, time-dependent penalties, and gradient-based traversal is critical.
• Runtime Performance:
  • GBJO demonstrated low wall-clock time (40–200 ms), dominated only by Greedy Search and NeuralSort.
  • Unlike Dynamic Programming (exponential growth) or Iterative Improvement (growing runtime), GBJO maintained a favorable scaling trend.
• Landscape Analysis: Visualizations of the cost landscape revealed that even though the model was trained only on discrete plans, the relaxed continuous space provided meaningful directional gradients toward lower-cost solutions.

Significance and Claims

The paper positions this work as a first step toward gradient-based join ordering. The authors claim that by exploiting the differentiability of learned cost models, it is possible to bypass the limitations of discrete combinatorial search.

• Feasibility: The results demonstrate that gradient descent can successfully navigate the "superposition" of plans to find high-quality solutions, even though these intermediate states do not correspond to physically valid execution plans.
• Efficiency: The approach offers a practical alternative for real-time query optimization, balancing the need for high-quality plans with low computational overhead.
• Future Potential: The authors suggest that this framework could lead to more effective and efficient query optimizers in the future, particularly as model compilation and kernel optimization can further reduce runtime.

The paper maintains a modest tone, acknowledging that while the current implementation is not fully runtime-optimized, the theoretical framework and empirical results establish a viable path forward for differentiable query optimization.