結合するリレーションの数が少なければ最適な結合順序を選択することができますが、最適化ルーチンが使用できるバイナリ結合順序の候補が指数関数的に上昇すると、さまざまなアルゴリズムや経験則が、もっともコストの低い結合計画を決定するために考えられるすべての組合わせを1つずつ評価していくという過激な方式を採用しなければならない地点にまで急激に到達します。
結合順序の評価はクエリー最適化の1つの重要な側面ですが、これは統計の正確さに大きく依存します。 古い統計データやデモグラフィック データを使用すると、中間結果でカーディナリティの不正確な想定が行なわれる可能性があります。 このような不正確な想定により、結合計画の見積もりの間違いが、クエリーが行なう結合の数の関数として指数関数的に増大しながら波及します。
結合順序評価プロセスの概要
次のテーブルは、ある結合計画の生成過程で結合順序を評価する際に、最適化ルーチンが実行するプロセスを簡単に説明しています。
- 1結合先取り計画を作成する。
-
条件 結果 - 1結合先取り計画のコストがしきい値を超過する。
- しきい値より大きいリレーションが1つある。
- 問合わせが外部結合の要件を満たしていない。
5結合先取り計画を作成し、そのコストを評価する。 1～5つの結合先取り計画から、コストのかからない計画を保持する。 -
条件 結果 - 現在の計画のコストがしきい値を超過する。
- スター結合が必要とされる。
スター/スノーフレーク結合の最適化を使用する計画を作成する(そのような計画が見つかる場合)。その場合は、スター/スノーフレーク結合と結合先取り計画を比較し、コストのかからない計画を維持します。
先取り結合計画
クエリーのために最適な結合シーケンスを計画する場合、最適化ルーチンは「もしそうなったらどうするか」という方法を使用して、使用できるシーケンスがクエリー計画にとって比較的有用かどうか評価します。評価時には、さまざまな順序でリレーションを結合するときの最終的なコストを調べるために1つ以上の計画を先に参照するため、結合の最適化では、この「もしそうなったらどうするか」という方法は、一般的に先取りとも言われます。
結合順序分析の目的は、実行できるサブセットに対する結合の可能性の数を減らすことです。結合スペースの最適化ルーチンによる検索は、結合条件によって運用されます。この結果として、再帰的な欲張りアルゴリズムを使用して、接続されたリレーションを検索して評価します。この文脈では、欲張りという用語は、検索するときに、前のステップで判別したコスト決定の結果に基づいて、評価する次の論理式を生成することを意味します。検索ツリーの観点で見ると、欲張りアルゴリズムは必ずツリー下部から開始し、上に向かって機能していきます。
次に、先取り結合計画の簡単な説明を示します。
- 考慮している組合わせの中から最適な3通りまたはn通りの結合計画を見つけます。その際には、次のルールに従います。
- 深さ優先探索を使用する。
- 次の条件のいずれか1つが検出された場合は、結合計画をスキップする。
- 類似した属性またはより良い属性を持つ結果を送達する、コストの低い計画がある。
- 累積コストが現在の結合計画の候補のコストを超える。
- 接続されたリレーションの間の結合だけを考慮する。
- 接続されたリレーションをすべて結合した後に限り、接続されていないリレーションを結合する。
最適化ルーチンは、リレーションの可能なすべての組合わせを評価しません。それによって実現される最適化よりも、その労力のほうが大きいからです。例えば、10通りの結合には17.6×109の可能な結合があり、64通りの結合には1.2×10124の可能な結合があります。
主に結合条件によって実行される組合わせを進める際に、最適化ルーチンは最良の可能な結合計画を見落とす可能性もありますが、それは実務では通常生じることはありません。
- 現在の最良の結合計画を評価します。
条件 結果 最良の結合計画の最初の2つの結合について次の条件が見つかった場合 - 互いに接続されていない2つのリレーションに1つのリレーションが接続されている結合がある。
- 結合が積結合ではない。
接続されていない2つのリレーションが最初の結合で積結合され、その結果が3番目のリレーションに結合されるという、折衷結合を試みる。 結合計画の妥協案のほうが現在の最良の結合計画よりコストが低い。 最良の結合計画の最初の2つの結合を妥協案と置き換える。 妥協案はスター結合計画が可能になるように設計されています。
- 最良のn個の結合の最初の結合を具体的にリレーションで表わし、その具体化されたリレーションを次の条件で評価します。
- 先取り計画の数が完全な結合計画を作成するのに十分の数である。
- 結合計画の妥協案を使用しない。
条件 結果 一致する場合 最良の計画の残りの結合もコミットされる。 一致しない場合 新しく結合されたリレーションのプライマリ インデックスを使って、別のリレーションを最初の結合の結果と結合する場合、2番目の結合もコミットされる。 - 新しいリレーションの接続情報を述部に基づいて作成します。
- アクティブなリレーションが1つだけになるまでステップ1から4を繰り返します。
例: 結合計画の妥協案
次のリクエストについて考えてみます。
SELECT * FROM t1, t2, t3, t4 WHERE x1=x2 AND y1=y3 AND z1=y4 ;
次の図の最初の結合図は、この問合わせでのリレーション間の接続を示しています。
- t1は、条件x1=x2であるため、t2に接続される
- t1は、条件y1=y3であるため、t3に接続される
- t1は、条件z1=y4であるため、t4に接続される
ステップ2から、次の条件が当てはまれば、最適化ルーチンは折衷結合を作成しようとすることを知っています。接続されていない2つのリレーションはプロダクト ジョインであり、結果は3つ目のリレーションと結合されることになります。
- 最善の計画での最初の2つの結合には、相互に接続されていない2つのリレーションと接続される1つのリレーションが含まれる
- 結合が積結合ではない。
図の2番目の結合図は、t1とt2の結合を受けて生じるリレーションt1t2とt3の結合が、接続されていないリレーションt2とt3の折衷結合を受けて生じるリレーションt2t3とt1の結合と同じくらい性能が高くないことを示しています。
このため、図の3つ目の結合図に示されている通り、結合計画に折衷結合が選択されます。
例: n方向結合の1結合先取り処理
次の図は、6方向結合の結合スペースを最適化ルーチンで分析した結果を示しています。それぞれの結合の相対コストは、選択した結合シーケンス内に整数で示されます。
この関係については、次のテーブルではっきりと示されています。
| このバイナリでの結合対象 | かかる相対コスト | 結果として生成されるリレーション |
|---|---|---|
| A - B | 1 | AB |
| AB - C | 4 | ABC |
| D - F | 1 | DF |
| DF - E | 2 | DFE |
| ABC - DFE | 5 | ABCDEF |
次の図は、n方向結合の1結合先取り処理と、最適化ルーチンがそれぞれの相対コストに基づいて複数のシーケンスの中から1つの結合シーケンスを選択する方法を示しています。
リレーション間でのコストの関係については、次のテーブルにはっきりと示されています。
| このバイナリでの結合対象 | かかる相対コスト | 結果として生成されるリレーション |
|---|---|---|
| D - E | 1 | DE |
| D - F | 2 | DF |
| DE - F | 5 | DEF |
| DF - E | 2 | DEF |
| ABC - DFE | 5 | ABCDEF |
最適化ルーチンは、個々のバイナリ結合コストを合計して、評価対象となる結合コスト全体を生成し、コストが最小になる結合シーケンスを判別します。この例では、次の結合シーケンスのコストが判別されます。
((DE)F) = 1 + 5 = 6 ((DF)E) = 2 + 2 = 4
その結果、リレーションDとFが最初に結合し、それを受けて生じるリレーションDFとEを結合する第2の配列の方がコストのかからない結合であるため、結合計画として選択されます。