最適化ルーチンの結合計画 - Advanced SQL Engine - Teradata Database

Teradata Vantage™ - SQLリクエストおよびトランザクション処理

Product
Advanced SQL Engine
Teradata Database
Release Number
17.10
Published
2021年7月
Language
日本語
Last Update
2021-09-23
dita:mapPath
ja-JP/uqf1592445067244.ditamap
dita:ditavalPath
ja-JP/wrg1590696035526.ditaval
dita:id
B035-1142
Product Category
Software
Teradata Vantage

リレーションを結合するための最適な方法を選択することは、テーブルのアクセス方法を選択することと同様に問合わせのパフォーマンスにとって重要です。

リレーションを結合するための方法は数多くあります。最適化ルーチンが結合を行なうために最終的に選択する方法は、結合を行なうときの比較や、結合するリレーションの見積もりカーディナリティ、結合対象のシステムの構成など、複数の要因によって異なります。

この節では、複数レベルでの結合処理について説明します。

結合計画の構成要素

結合計画には、以下の中核的な要素が関係します。
  • 結合方式の選択。

    多くの場合、同じ結合の作成に使用できるいくつかの選択可能な方式があります。例えば、必ずではないものの通常は、マージ結合を使用する方が積結合よりもコストが低くなります。結合方式の選択は多くの場合、問合わせの処理の全体コストに大きな影響を与えます。

  • 最適な結合位置の決定。

    結合する行の移動方法が異なると、コスト面でかなり異なることがあります。例えば、結合操作内のリレーションのサイズによっては、リレーションの1つをコピーする方が、それを再分散するよりも低コストの場合があります。

  • 最適な結合順序の決定。

    リレーションが結合される順序は、結合コストにかなりの影響を与える場合があります。この文脈では、テーブルは別のテーブルではなくスプールと結合できます。テーブルという用語は、最も総称的な意味で使用され、論理的な用語のrelationはしばしば、任意のテーブル、ビュー、またはスプールの代用として使用されます。

  • 最適なスプール形式の決定。

    Teradataは、コストに応じて、通常形式またはメモリ内形式を選択できます。コスト モデルは、メモリ内スプールの実働を含む、さまざまなパラメータを使用します。場合によっては、最適化ルーチンが通常のテーブルをメモリ内スプール形式のテーブルに変換します。

以下のテーブルは、結合計画により導入されるいくつかの用語を概説しています。

用語の種類 定義
バインド 異なるリレーションの2つの列間の同等制約。

通常はインデックスに対する条件があるかどうかを判別するために使用されます。

(t1.a= t2.a)
交差 異なるリレーションに関する式を持つ述部。

交差用語は、column_name=expressionという形式の条件に対して生成できます。これは半交差用語と呼ばれます。

最適化ルーチンは、半交差用語を、インデックスに対して指定される場合に制約として使用できます。

変換(列)と列が同じようにハッシュされている場合、フォーム変換(列) = 式を同じ目的で使用できます。

(t1.a= t2.a+1)
存在する EXISTS条件を指定する述部。  
明示権限 定数に定義される述部。

通常はインデックスに対する条件があるかどうかを判別するために使用されます。

(t1.a=1)
マイナス MINUS条件を指定する述部。  
その他 文字どおり、他のいずれのカテゴリにも属さない用語のグループ。
一連の「その他」の用語には、以下が含まれます。
  • 不等式用語。
  • リレーションの同じセットまたはリレーションの非同一セットについての等式用語。
  • AND演算用語。
  • OR演算用語。
  • それ以外の用語(例えば、2つを超えるリレーションについて表現した用語)。

変換(列) = 定数条件に対して、その他の用語を生成できます。変換(列)と(列)ハッシュが同じ場合、その他の用語は明示的な用語を指します。

例えば、変換により実行される操作が、列の単純な名称変更である場合などです。この場合、「その他」の用語は、制約がインデックス列に指定されているかどうかを判別するために使用されます。

 
外部結合 外部結合用語。  

結合の計画時に最適化ルーチンが最初に探すものは接続条件ですが、これは外部問合わせとサブクエリーを接続する述部です。以下はすべて、接続条件の例です。

(t1.x, t1.y) IN (SELECT t2.a, t2.b FROM t2)
--> (t1.x IN spool1.a AND (t1.y IN spool1.b)

(t1.x, t1.y) IN (SELECT t2.a, constant FROM t2)
--> (t1.x IN spool1.a) AND (t1.y=spool1.constant)

(t1.x, constant) NOT IN (SELECT t2.a, t2b FROM t2)
--> (t1.x NOT IN spool1.a) AND (constant NOT IN spool1.b)
さらに、最適化ルーチンは条件を分析して、結合操作におけるリレーション間の接続を決定します。
  • 次のいずれかの条件が検出されれば、2つのリレーションの間には直接接続が存在します。
    • 2つのリレーションの間の従属情報を満たす、AND演算されたバインド、その他、交差、外部結合、またはマイナス用語。
    • 外部リレーションと接続する、相関関係のないサブクエリーEXIST条件のスプール。
  • 単一リレーションにAND演算されたその他または明示的用語は、リレーションに後付けされます。
  • どのリレーション上にもない用語はリレーションに後付けされます。
  • Subquery および単一リレーションを参照するOR演算用語は、複合用語としてそのリレーションに関連付けられます。
  • Subquery と複数のリレーションを指定するOR演算用語で参照されるすべてのリレーションは、複合セットに後付けされます。
  • 一部の結合条件で指定されるすべてのリレーションは、接続済みとマークされます。
  • 例えば以下のように、結合前にリレーションがスプールされる場合に、選択および射影が実行されると想定します。
    SELECT t1.x1
    FROM t1, t2
    WHERE y1=1
    AND   x1= x2;
  • 一連の入力リレーション内のすべてのリレーションに関する以下の情報を検出します。
    • 射影の適用後のその行サイズ。
    • 選択条件の適用後のそのカーディナリティ。
    • 直前に決定された行サイズおよびカーディナリティに基づいてそれを読み取るためのコスト。
    • その出力行コスト。
    • プライマリ インデックス(プライマリ インデックスがある場合)。
    • 次に示すような、接続されたリレーションのセット。
      SELECT t1.x1
      FROM t1, t2
      WHERE y1=1
      AND   x1= x2;
  • 一連の入力リレーション内のすべての基本テーブル リレーションに関する以下の情報を検出します。
    • リレーション行のサイズ。
    • リレーションのカーディナリティ。
    • 選択条件リスト。
    • 射影リスト。
    • 考え得る最善のアクセス パス(アクセス計画機能への呼出しを使用する)。
  • 一連の入力リレーション内のすべてのスプール リレーションに関する以下の情報を検出します。
    • スプールのカーディナリティ。
    • 選択条件リスト。
    • その割当てリスト。
    • そのスプール番号。

結合処理の方式

結合の対象となるテーブルに定義されているインデックスの種類によって、またそれらのインデックスの統計情報が使用できるかどうかによって、次のいずれかをはじめとする結合方式を使用して最適化ルーチンが結合を処理します。
  • プロダクト ジョイン
  • ハッシュ結合
  • マージ結合
  • 入れ子結合
  • 排他結合
  • 包含結合
  • 行ID結合
  • 相関結合
  • Minus all結合

これらの各結合方式の詳細については、結合戦略と結合方式およびそれに続くページを参照してください。

結合できるテーブルまたは単一テーブル ビューの数の制限

自己結合を除き、問合わせブロック当たり128個までのテーブルまたは単一テーブル ビューを結合できます。クエリー ブロックごとに結合できるテーブルおよび単一テーブル ビューの最大数は、DBS制御レコードのMaxJoinTablesパフォーマンス フィールドの値(範囲は最小64から最大128)によって決まります。詳細については、Teradata Vantage™ - データベース ユーティリティ、B035-1102を参照してください。

ゆるやかに定義すると、問合わせブロックとは、最適化ルーチンが結合計画を作成するときの単位です。次のリストには、頻出する問合わせブロックがいくつか示されています。
  • 非相関サブクエリー
  • 派生テーブル
  • 複雑なビュー
  • UNIONおよびINTERSECT演算の一部

相関名を使用した参照も含め、リレーションを参照するたびに、128のテーブルの制限がカウントされます。この制限には、部分カバーを処理するための、基本テーブルに対するハッシュ結合インデックスの結合または単一テーブル結合インデックスの結合など、暗黙的な結合も含まれます。

例えば、相関のない1つのサブクエリーを使用したクエリーについて考えてみます。サブクエリーは128個のテーブルに制限され、外部クエリーは127個のテーブルに制限されているため、外部クエリーの128番目のテーブルは、結合する必要のある内部クエリーがスプールされた結果になります。

相関のないサブクエリーが、相関のない他のサブクエリーへの外部クエリーであった場合、一番深いサブクエリーは128個のテーブルの参照に制限され、外部クエリーは127に制限されます(127個に内部クエリーの結果を加えたもの)。また、親の外部クエリーは127と内部クエリーの結果を加えたものに制限されます。

要約すると、中間スプール リレーションを含めて、結合できるテーブルの数は、問合わせブロック当たり128に制限されますが、問合わせを最適化する過程で参照されるテーブルの累積数は、128よりもかなり大きくすることができます。

結合計画を作成する過程で、最適化ルーチンはいくつの問合わせブロックを作成して処理するかという制御方法を決定する方法はありませんが、問合わせが最大128のテーブルの結合の制限を超過したために終了する場合でも、ここにリストした要因はすべて評価対象となる候補と言えます。

結合と定義域についての推奨事項

必ず、同一定義域で定義された列のテーブルとビューを結合する必要があります。

結合列が同一定義域で定義されていない場合、システムは、結合を処理する前に、それぞれの値を共通のデータ型に変換する必要があります(暗黙データ型変換については、<Teradata Vantage™ - データ タイプおよびリテラル、B035-1143>を参照)。変換プロセスは、リソースを大量に消費するため、パフォーマンスには負荷がかかります。

DISTINCT型のユーザー定義データ型(UDT)は、定義域を定義する良い方法で、これはまた有用なタイプ設定を実現しますが、UDT設計者が明示的にタイプ変換のコーディングをしない限り、暗黙のタイプ変換が起きる可能性はなくなります。

この積極的な面は、UDT列に対して制約を定義できないという消極的な面によってバランスが取られます。この制限的要因が理由で、DISTINCT型のUDTが定義域を定義するための良い方法であるかどうかは、いくつかの要因のバランスを取るという問題であり、いずれかを選ぶ場合はどの方法が開発環境で定義域の定義に最適であるかという問題です。

UDTについては、<Teradata Vantage™ - SQL外部ルーチン プログラミング、B035-1147>および<Teradata Vantage™ - SQLデータ定義言語-構文規則および例、B035-1144>を参照してください。定義域を定義するためのUDTの使用に関しては、<Teradata Vantage™ - データベースの設計、B035-1094>を参照してください。

大規模な結合に必要な構文解析プログラム メモリの容量

1つのリクエストで32を超えるリレーションの結合を計画する場合は、DBS制御ユーティリティを使用して、MaxParseTreeSegsフィールド(パフォーマンス グループ内)の値を、コード生成用の構文解析プログラム メモリに割り当てられている構文解析ツリー メモリ セグメントのデフォルト値より大きくします。DBS制御ユーティリティの詳細については、<Teradata Vantage™ - データベース ユーティリティ、B035-1102>を参照してください。

MaxParseTreeSegsフィールドは、SQLリクエストを解析する際に構文解析プログラムが割り当てる構文解析ツリー メモリ セグメントの最大数を定義します。データベースにより、必要に応じて構文解析ツリーのセグメントが動的に割り当てられるため、このフィールドによって不要なメモリが事前に割り当てられることはありません。

結合コストの評価

最適化ルーチンはコスト ベースであるので、使用可能な結合方法の相対コストを評価し(結合戦略と結合方式を参照)、2つのリレーションを結合するための最低コストを判別します。

例として、等式プロダクト ジョインを考えてみましょう。この場合、小さいほうのリレーションは全AMP上にコピーされ、次いで小さいほうのリレーション内のすべての行は大きいほうのリレーションのすべての行と比較されます。結合を実行する比較の合計数は、小さいほうのリレーションの行数と、大きいほうのリレーションの行数との積になります。

小さいリレーションの見積もりカーディナリティが5行の場合、右リレーションの各行は5つの比較を行なうと推定されます。見積もりが500行の場合、推定される比較数は500です。これは2桁の相違です。前者は最もコストが少ない方法ですが、後者の場合は、別の結合方法の方がコストが少なくて済みます。

結合の順序付けは、これらの結合に使用する方法の選択とは別個のプロセスであることに注意してください。最適化ルーチンが結合の順序を評価する方法については、結合の順序の確認を参照してください。

n方向結合の計画

結合で3つ以上のリレーションが指定されると、最適化ルーチンは、リレーションの結合を一連のバイナリ結合と見なし、最もコスト効率が良い結合順序を判別します。最適化ルーチンは、単一ステップでのn方向結合を使用した、リレーションのサブセットの結合を検討する場合もあります。

例えば、次のような複数テーブルへのリクエストを送ったと仮定します。

SELECT ...
FROM A, B, C, D
WHERE ...;

最適化ルーチンでは、次の3つの図のような結合計画を生成します。最適化ルーチンは、列統計を使用して、生成された候補の中から最もコストのかからない結合計画を選ぶため、生成される計画は統計の数値の正確さに完全に依存しています。


3つの結合計画の例

結合を行なう前に、列射影および行選択が行なわれる場合があります。選択基準が提供されない場合には、すべての行と列が結合処理に関係します。

重複したり再分散したりしなければならない行と列の数は少なくしておく方が有利です。しかし、結合を基本テーブルから直接行なうことができる場合は、2つの行が結合に適しているかどうかを判別した後、列射影と行選択を結合ステップで実行する方が効率的な場合があります。

結合順序検索ツリー

問合わせ最適化ルーチンは、ツリーを利用して、最適な結合順序を構築および分析します。商用リレーショナル データベース最適化ルーチンでもっとも頻繁に使用されている結合検索ツリーのタイプは、左に向かって深くなるツリーと枝の多いツリーです。

左に向かって深くなる検索ツリー

左に向かって深くなる検索ツリーを使用して、可能な結合順序を分析する場合、次の計算式に示されているように、生成される可能性の数は比較的少なくなります。nは結合するリレーションの数です。


結合順序の数の式

4つのリレーションの結合の場合、左に向かって深くなる検索ツリーを使用した結合順序の数は4の階乗(つまり、24)のみになります。左に向かって深くなる結合ツリーは、多くの商用リレーショナル システムで使用されていますが、可能な結合シーケンスをさらに多く生成でき、より良い結合計画を検出しやすくする別の方法があります。

次の図は、下から上に向かって読み取り、4つのリレーションを結合するために左に向かって深くなる結合ツリーを示しています。



枝の多い検索ツリー

枝の多いツリーは、さらに多くの結合順序の組合わせを生成することに適した方法です。同時に、生成される組み合わせの数を制限できるので、最適化ルーチンは複数の経験則を使用して、検索スペースを絞り込みます。例えば、スター結合を除き、制約のない結合の場合、枝の多い検索ツリーになる可能性は考慮されません。

この方法は、制約のない結合の絞込みを無視し、結合の可能性がはるかに多い順序を生成し、左に向かって深くなるツリーの方法よりも評価対象範囲が広くなります。枝の多いツリーには、複数の結合を並行して実行する機能もあります。例えば、次の4つのリレーションの場合を考えてください。

((A JOIN B) JOIN (C JOIN D)

(A JOIN B)(C JOIN D)は、同時に処理するためにディスパッチできます。左に向かって深くなるツリーだけを使用するシステムでは、このような並行した結合を実行できません。

4個のリレーションの場合を考えてみましょう。 4つのリレーションの順列の数は4、すなわち24で済みます。 リレーションの名前がa、b、c、dの場合、これらの24個の順列は次のようになります。

abcd, abdc, acbd, acdb ... dcba

システムは一度に2つのリレーションしか結合できないため、24の順列を考えられる限りのバイナリ結合順序にさらにパーティション化しなければなりません。そうすると、次のようになります。

abcd => (((ab)c)d)
        ((ab)(cd))
        (a(b(cd)))
        ((a(bc))d)
        ((a(b(cd))
            .
            .
            .

など。

次の図は、リレーションa、b、c、dをバイナリ結合したときに考えられるシーケンスの1つです。この記述については、次の点に注意する必要があります。
  • 図は下から上に向かって読むこと。
  • 中間の結合の結果は、テーブルではなくてリレーションと見なされること。

図で示しているプロセスは、次のように説明できます。

  1. テーブルaとテーブルbを結合し、中間リレーションabを作成します。
  2. テーブルcとテーブルdを結合し、中間リレーションcdを作成します。
  3. リレーションabとリレーションcdを結合し、最終的な結合結果であるリレーションabcdを作成します。


最適化ルーチンは、テーブルのデモグラフィックと環境コストに応じて、次のような結合シーケンスを生成することもあります。

  1. テーブルaとテーブルbを結合し、中間リレーションabを作成します。
  2. リレーションabとテーブルcを結合し、中間リレーションabcを作成します。
  3. リレーションabcとテーブルdを結合し、最終的な結合結果であるリレーションabcdを作成します。

最適化ルーチンは、計画を探索する点で非常に処理能力が高く、有効性が実地で証明されているたくさんの経験則を使用してコスト高の計画をコスト処理の初期の段階で考慮対象から除外するようにし、結合計画検索領域を最適化します。