# Gradient-Based Join Ordering

arXiv: https://arxiv.org/abs/2511.14482 · HTML: https://mlsanity.com/paper/2511.14482/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 45 references that are in the map.
- First posted on arXiv 18 Nov 2025.

## Builds on (most cited first, 17 of 17)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [KEPLER: A Unified Model for Knowledge Embedding and Pre-trained Language Representation](https://mlsanity.com/paper/1911.06136/) (2019)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [SoftSort: A Continuous Relaxation for the argsort Operator](https://mlsanity.com/paper/2006.16038/) (2020)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Deep Reinforcement Learning for Join Order Enumeration](https://mlsanity.com/paper/1803.00055/) (2018)
- [Gradient-based Planning with World Models](https://mlsanity.com/paper/2312.17227/) (2023)
- [Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks](https://mlsanity.com/paper/2303.01140/) (2023)
- [Neuro-Symbolic Query Optimization in Knowledge Graphs](https://mlsanity.com/paper/2411.14277/) (2024)

## Abstract (arXiv)

Join ordering is the NP-hard problem of selecting the most efficient order in which to evaluate joins (conjunctive, binary operators) in a database query. Because query execution performance critically depends on this choice, join ordering lies at the core of query optimization. Traditional approaches cast this problem as a discrete combinatorial search over binary trees guided by a cost model, but they have trade-offs between effectiveness and efficiency. We show that when the cost model is differentiable, query plans can be continuously relaxed into a soft adjacency matrix that represents a superposition of plans. This continuous relaxation, combined with differentiable constraints that enforce plan validity, enables a gradient-based search for low-cost plans within this relaxed space. Using a Graph Neural Network as the cost model, we demonstrate that this gradient-based approach can find comparable and even lower-cost plans compared to traditional discrete search methods on two different graph datasets. Furthermore, we empirically show that the runtime of this approach scales better than discrete search algorithms. We believe this first step towards gradient-based join ordering can lead to more effective and efficient query optimizers in the future.