Our paper "Gradient-Based Join Ordering" (with @maribelacosta ) will be presented at IJCAI 2026! Join ordering, deciding the order in which to evaluate the joins of a database query, is a classic and discrete NP-hard problem, and one of the most important in any database engine. Current engines approach it using discrete algorithms like dynamic programming, greedy heuristics, or genetic algorithms. In our new paper, we explored a different option. If the cost model is differentiable (e.g., a neural network), why not search using a gradient? For that, we relax discrete query plans into a soft adjacency matrix, i.e., a continuous superposition of plans, and descend the cost landscape directly via gradient descent. Differentiable structural penalties (degree constraints, acyclicity, left-linearity) combined with temperature annealing ensure the optimization converges to a valid, discrete plan. Interestingly, although the cost model is only ever trained on valid, discrete plans, the relaxed space between them turns out to be smooth and informative — the local gradient reliably points towards better plans. Key results on two standard benchmarks: • Plan quality matches and often surpasses discrete baselines • Only ~10 cost model evaluations are needed, vs. hundreds for randomized search • Runtime of 40–200 ms with more favorable scaling in query size than greedy search We think this is a first step towards query optimizers that treat plan search as continuous optimization rather than combinatorial enumeration. #IJCAI2026 #QueryOptimization #DatabaseSystems #GraphNeuralNetworks #KnowledgeGraphs