arXiv:2511.14482cs.DBcs.LG2025-11

用梯度法优化数据库连接顺序,更快找到高效查询方案。

Gradient-Based Join Ordering

  • 将连接顺序问题转化为可微的连续空间搜索
  • 在两个图数据集上达到甚至优于传统方法的性能
  • 适合对查询优化效率有要求的数据库系统开发者

连接顺序是数据库查询优化中的核心难题,属于NP难问题。传统方法基于成本模型在二叉树空间中进行离散搜索,但存在效率与效果的权衡。本文提出当成本模型可微时,可将查询计划连续松弛为表示计划叠加的软邻接矩阵,并结合可微约束保证计划有效性,从而在该连续空间中进行梯度搜索。采用图神经网络作为成本模型,在两个图数据集上验证了该方法能获得与传统方法相当甚至更低开销的计划,且运行时间增长更缓慢。这是迈向基于梯度的连接顺序优化的重要一步,有望提升未来查询优化器的效率与效果。

原文摘要 · Abstract (English)

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.

数据库查询优化图神经网络可微优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。