Gradient-Based Join Ordering
Tim Schwabe, Maribel Acosta · 2025
Read Gradient-Based Join Ordering by Tim Schwabe, Maribel Acosta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14482.txt.
Introduction
Tim Schwabe and Maribel Acosta propose a gradient based method for ordering joins in database queries. Join order strongly affects how fast a query runs, yet finding the best order is a hard search problem. Classic methods search over discrete tree plans with a cost model. That search forces trade offs between speed and plan quality.
When the cost model can be differentiated, plans can be relaxed into a soft matrix form. Gradient search can then move through that relaxed space toward low cost plans. Using a graph neural network as the cost model, the method finds plans as good as or better than discrete search. Its run time also scales more favorably.
Catalog record
| CREATOR | Tim Schwabe, Maribel Acosta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-14482
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Gradient-Based Join Ordering Tim Schwabe, Maribel Acosta Abstract Join ordering is the NP-hard problem of selecting the most efficient sequence in which to evaluate joins (conjunctive, binary operators) in a database query. As the performance of query execution 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 often suffer from high computational complexity and limited scalability. We show that, when the cost model is differentiable, the query plans can be continuously relaxed into a soft adjacency matrix representing a superposition of plans. This continuous relaxation, together with a Gumbel-Softmax parameterization of the adjacency matrix and differentiable constraints enforcing plan validity, enables gradient-based search for plans within this relaxed space. Using a learned 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 local search methods on two different graph datasets. Furthermore, we empirically show that the runtime of this approach scales linearly with query size, in contrast to quadratic or exponential runtimes of classical approaches. We believe this first step towards gradient-based join ordering can lead to more effective and efficient query optimizers in the future. K eywords Join Ordering \cdot Query Optimization \cdot Graph Neural Networks \cdot Knowledge Graphs 1 Introduction Figure 1: Join Ordering using a learned Cost Model. Continuously relaxing the discrete Search Space of Plans allows traversing it using Gradient Descent. The initial Plan is a superposition of all possible plans. The gradient search converges to a valid plan (the corners of the space) by minimizing the predicted cost. Query optimization, particularly join ordering, is one of the most critical tasks in any database system. It involves determining the optimal evaluation sequence for the joins in a query, such that the resulting execution order has a low query runtime. Efficiently ordering join operations can significantly impact query execution time, often resulting in either instantaneous responses or impractically long delays. At the core of join ordering is a cost model , which estimates the computational expense associated with executing a query or a part of it. Accurately estimating these costs is a challenging statistical estimation problem, primarily due to the complex data distributions and correlations within real-world databases. But, finding a good join ordering does not only involve estimating one query plan. It constitutes a discrete search problem over the space of plans, which are represented as binary trees, and which grows super-exponentially. Classical approaches to navigating this space typically rely on discrete methods like dynamic programming, which systematically evaluates possible plans at exponential cost, or greedy heuristics, which choose locally optimal steps fast but usually find suboptimal solutions. Recently, learned cost models based on neural networks have been proposed, demonstrating significant superiority in cost estimation compared to classical statistical methods. However, these learned cost models are either still paired with traditional discrete search methods or completely rely on Reinforcement Learning, which is sample inefficient and has unstable convergence dynamics. In this work, we present a fundamentally different direction: we can exploit the differentiability of learned cost models and reformulate join ordering as a continuous optimization problem via relaxation of the discrete search space. As shown in Figure 1 , we represent query plans as continuous adjacency matrices, enabling direct gradient-based search guided by a differentiable cost model. Therefore, the main contributions of this work are: • We propose a novel gradient-based method for join ordering using learned cost models based on Graph Neural Networks, operating on a continuous relaxation of the discrete search space. • We empirically show that this method generates solutions that approach and sometimes outperform ones found by discrete local search methods. • We empirically show that the runtime of this approach is linear, as opposed to quadratic or exponential for discrete approaches. 2 Preliminaries In this work, we assume a graph data model, where queries typically involve a large number of joins due to the fine-grained, triple-based representation of relationships. We assume basic familiarity with sets, graphs, and matrix notation. 2.1 Triple - Based Graph Queries We assume a graph data model in which the data is stored as triples , i.e. labelled, directed edges t=(s,p,o)\in\mathcal{E}, where each element belongs to a set s,p,o\in\mathcal{I} . A finite set of triples \mathcal{E} forms an edge - labelled directed graph. Triple patterns and conjunctive queries. Such graphs are queried with triple patterns , i.e., triples in which any position may be a variable from an infinite set \mathcal{V} (s.t. \mathcal{V}\cap\mathcal{I}=\emptyset ) of variables : tp=(s,p,o)\in(\mathcal{I}\cup\mathcal{V})^{3}. A triple pattern is the most basic query. Its answer is the set of solution mappings \Omega_{tp}=\bigl\{\mu:vars(tp)\!\to\!\mathcal{I}\,\bigm|\,\mu(tp)\in\mathcal{E}\bigr\}, where vars(tp) are the variables appearing in tp . The number of solution mappings is called the cardinality |\Omega_{tp}| of the triple pattern. More general conjunctive queries combine several triple patterns Q=\{tp_{1},\dots,tp_{n}\}\subseteq(\mathcal{I}\cup\mathcal{V})^{3} . Join Operators. The answer to a conjunctive query is obtained by iteratively joining the solution mappings. Let \operatorname{dom}(\mu) denote the variables on which \mu is defined. Mappings \mu_{1},\mu_{2} are compatible , \mu_{1}\sim\mu_{2} if they assign the same value to every shared variable, i.e. \forall v\in\operatorname{dom}(\mu_{1})\cap\operatorname{dom}(\mu_{2}):\mu_{1}(v)=\mu_{2}(v). Their union \mu_{1}\cup\mu_{2} is the mapping with domain \operatorname{dom}(\mu_{1})\cup\operatorname{dom}(\mu_{2}) . The join of two solution sets is then \Omega_{1}\Join\Omega_{2}=\bigl\{\mu_{1}\cup\mu_{2}\ \big|\ \mu_{1}\in\Omega_{1},\;\mu_{2}\in\Omega_{2},\;\mu_{1}\sim\mu_{2}\bigr\}, i.e., a set of solution mappings with cardinality |\Omega_{1}\Join\Omega_{2}| . 2.2 Query Plans The final set of solution mappings is invariant to the order in which the triple patterns are joined. However, since the number of intermediate results can differ vastly, the order still matters. A query plan p for Q defines the order in which these joins occur. Formally, it is a binary tree whose leaves correspond exactly to the triple patterns in Q , and internal nodes represent join operators combining intermediate results from their children. • A plan is bushy if no structural restrictions exist. Joins may freely combine the results of arbitrary subplans. • A plan is left-linear if each join operator has at most one non-leaf child. Such plans represent sequential join orders. Since the space of bushy plans is vast ( C_{n-1}n! , where C_{n-1} is the Catalan Number), commercial optimizers often restrict the search space to left-linear plans (with size n! ). While our proposed method is general and can search the space of bushy plans as fast as the space of left-linear plans, we focus on left-linear plans in this work. For a query with n triple patterns, we represent a plan p as an adjacency matrix A\in\{0,1\}^{\left(2n-1\right)\times\left(2n-1\right)} , where A_{ij}=1 means node i is joined into node j . The first n indices in A correspond to triple patterns, and the last n-1 indices correspond to join nodes (see example in Figure 2 ). Figure 2: A join plan p is represented as a \left(2n-1\right)\times\left(2n-1\right) dimensional matrix f(p)=A . The first n rows denote the outgoing edges of triple patterns, while the last n-1 rows are outgoing edges of join nodes. The root node always corresponds to the last row. 2.3 Execution Cost and Cost Model The goal of join ordering is to minimize the execution cost of a plan, which measures resources used, e.g.,