# 結合順序最適化 ## 定義 結合順序最適化(Join Order Optimization)とは、複数テーブルを結合するクエリにおいて、実行コストが最小になる結合木(join tree)の形と結合順序を選ぶ最適化問題である。互いに独立した3つの部分問題からなる。(1) 述語の形(等値・不等式・複雑述語)と行数閾値に応じた結合実装の選択(HASH_JOIN/NESTED_LOOP_JOIN/PIECEWISE_MERGE_JOIN/IE_JOIN。等値結合が典型的なのでHASH_JOINが主力実装)、(2) n+1個のテーブルを結合するn個の二項結合の木の形の探索(木の形の数はn番目のカタラン数C_nに従い急増し、C_10=16,796)、(3) 各結合でどちらの入力をbuild側・probe側に置くかの選択(build_side_probe_sideヒューリスティック)。[[DuckDB]]は(2)の全探索を避けるため、Moerkotte & Neumann(SIGMOD 2008)のハイパーグラフ対応動的計画法DPhypを`join_order`パスとして実装している(Source: [[@2026__DiDi__Query Rewriting and Optimization]], p.19-24)。 ## 横断的知見 - 今後の取り込みで、複数ソース間の関係を追記する。 ## 未解決の問い - DPhypのハイパーグラフ表現は、一般的な結合グラフ(サイクルを含む多対多結合条件)に対してどこまでスケールするか。カタラン数の急増(C_10=16,796)を考えると、大規模結合(n>15程度)での実務的な打ち切り・ヒューリスティック切り替えの閾値は何か。 - build_side_probe_sideヒューリスティックの具体的な判定基準(行数・カーディナリティ推定の精度への依存度)はどこまで公開情報から追えるか。 - 他のDBMS(PostgreSQL・Calcite VolcanoPlanner等)の結合順序探索アルゴリズム(動的計画法・貪欲法・遺伝的アルゴリズム)との比較でDPhypの位置づけはどうなるか。 ## 関連 - ソース: [[@2026__DiDi__Query Rewriting and Optimization]] - 概念: [[クエリオプティマイザ]] / [[クエリ非相関化]] - エンティティ: [[DuckDB]] / [[Torsten Grust]] / [[Universität Tübingen]] ## 出典 - [[@2026__DiDi__Query Rewriting and Optimization]](結合実装選択の決定木・DPhyp動的計画法によるjoin_orderパスの一次ソース、p.19-24)