Fugu-MT 論文翻訳(概要): Gradient-Based Join Ordering

論文の概要: Gradient-Based Join Ordering

arxiv url: http://arxiv.org/abs/2511.14482v1
Date: Tue, 18 Nov 2025 13:24:28 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-19 16:23:53.13295
Title: Gradient-Based Join Ordering
Title（参考訳）: 勾配に基づく結合順序付け
Authors: Tim Schwabe, Maribel Acosta,
Abstract要約: ジョイン順序付けは、データベースクエリのジョインを評価する最も効率的なシーケンスを選択する問題である。従来のアプローチでは、コストモデルによってガイドされたバイナリツリーを個別に実行時に検索する、という問題があった。コストモデルが異なる場合、クエリ計画がソフトな隣接行列に連続的に緩和可能であることを示す。学習したグラフニューラルネットワークをコストモデルとして使用することにより、この勾配に基づくアプローチが、同等で低コストなプランを見つけることができることを示す。
参考スコア（独自算出の注目度）: 0.532836690371986
License: http://creativecommons.org/licenses/by/4.0/
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.
Abstract（参考訳）: ジョイン順序付け(Join ordering)は、データベースクエリにおいて結合(接続子、バイナリ演算子)を評価する最も効率的なシーケンスを選択するNPハード問題である。クエリ実行のパフォーマンスは、この選択に批判的に依存するため、ジョイン順序付けはクエリ最適化の中核にある。従来の手法では、この問題をコストモデルで導かれた二分木を個別に組み合わせた探索として用いていたが、高い計算複雑性と拡張性に悩まされることが多かった。コストモデルが異なる場合、クエリプランは計画の重畳を表すソフトな隣接行列に連続的に緩和可能であることを示す。この連続緩和は、隣接行列のGumbel-Softmaxパラメータ化とプランの妥当性を強制する微分可能な制約とともに、この緩和された空間内のプランの勾配に基づく探索を可能にする。学習したグラフニューラルネットワークをコストモデルとして、この勾配に基づくアプローチは、2つの異なるグラフデータセット上の従来の離散局所探索手法と比較して、同等で低コストなプランを見つけることができることを示した。さらに、古典的アプローチの二次的あるいは指数的ランタイムとは対照的に、このアプローチのランタイムはクエリサイズと線形にスケールすることが実証的に示される。勾配ベースのジョインオーダへの第一歩は,将来的にはより効率的かつ効率的なクエリオプティマイザを実現することができる,と私たちは考えています。

関連論文リスト

Sketched Sum-Product Networks for Joins [0.8999666725996978]
そこで我々はSum-Product Networksを提案する。我々は,Fast-AGMSとBound Sketchメソッドを実装した。
論文参考訳（メタデータ） (2025-06-16T22:13:48Z)
Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。この問題を解決するための3つのアプローチを開発する。
論文参考訳（メタデータ） (2024-10-31T13:48:46Z)
A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization [12.016449555335976]
我々はNP-hard Maximum Cut問題に特化しているオープンソースのベンチマークスイートMaxCut-Benchを提案する。我々は、このベンチマークを用いて、いくつかの一般的な学習ベースのアプローチの結果を体系的に相関づけたり、再現したりしようとする。以上の結果から, 学習者の数人は, ナイーブな欲求アルゴリズムを上回り得ず, タブサーチを一貫して上回っているのはそのうちの1人だけであることが示唆された。
論文参考訳（メタデータ） (2024-06-14T19:44:23Z)
JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
論文参考訳（メタデータ） (2023-07-21T17:00:06Z)
Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文参考訳（メタデータ） (2022-11-22T10:18:33Z)
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文参考訳（メタデータ） (2022-01-25T00:10:03Z)
Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文参考訳（メタデータ） (2022-01-05T13:37:27Z)
Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文参考訳（メタデータ） (2021-12-06T20:34:55Z)
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文参考訳（メタデータ） (2021-06-09T09:18:18Z)
Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
グラフ学習に基づく新しい教師なしマルチビュー特徴選択モデルを提案する。 1) 特徴選択過程において, 異なる視点で共有されたコンセンサス類似度グラフが学習される。各種データセットを用いた実験により,提案手法が最先端手法よりも優れていることを示す。
論文参考訳（メタデータ） (2021-04-11T03:25:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。