Click here to view and discuss this page in DocCommentXchange. In the future, you will be sent there automatically.

SQL Anywhere 11.0.1 (日本語) » SQL Anywhere サーバ - SQL の使用法 » クエリ処理 » クエリの最適化と実行 » クエリ実行アルゴリズム » アルゴリズムの種類

 

ジョイン・アルゴリズム

SQL Anywhere では、クエリ・オプティマイザが選択できるさまざまなジョインの実装がサポートされています。ジョイン・アルゴリズムはそれぞれ特性が異なるので、適しているクエリや実行環境が異なります。

アクセス・プランでのジョインの順序は、元の SQL 文でのジョインの順序に対応している場合としていない場合があります。クエリ・オプティマイザによって、最も低い実行コストに基づいて、各クエリに最適なジョイン方式が選択されます。場合によっては、特定の文に計算されたジョイン数を増加または減少する複合文にクエリ書き換え最適化が使用されます。

SQL Anywhere では、 3 種類のジョイン・アルゴリズムがサポートされていて、この 3 種類にはそれぞれさらに変形があります。

  • ネスト・ループ・ジョイン   最も単純なアルゴリズムは、ネスト・ループ・ジョインです。左側のローごとに右側がスキャンされ、ジョイン条件に基づいて一致するローが検索されます。通常は、右側のローは、全体的な実行コストを削減するために、インデックスを使用してアクセスされます。このシナリオは、一般に「インデックス・ネスト・ループ・ジョイン」と呼びます。

    ネスト・ループ・ジョインには、LEFT OUTER ジョインと FULL OUTER ジョインをサポートする変形があります。ネスト・ループ・ジョインは、セミジョイン (ほとんどの場合、EXISTS サブクエリの処理に使用) にも使用できます。

    ネスト・ループ・ジョインは、ジョイン条件の特性に関係なく使用できます。ただし、不等号条件のジョインは、計算の効率が悪い可能性があります。

    ネスト・ループ FULL OUTER ジョインは、どのサイズの入力に対して実行しても高コストなので、クエリ・オプティマイザでは、他のジョイン・アルゴリズムが不可能な場合にのみ最後の手段として選択されます。

  • マージ・ジョイン   マージ・ジョインでは、ジョイン属性に基づいて 2 つの入力がソートされている必要があります。クエリ・オプティマイザでこの方法が選択されるには、ジョイン条件に 1 つ以上の等号述部が必要です。基本のアルゴリズムは、2 つの入力の単純なマージです。2 つのジョイン属性の値が異なる場合は、左側または右側のどちらか値が小さい方の次のローに移ります。複数のローが一致する場合は、バックトラックが必要である場合があります。

    マージ・ジョインには、LEFT OUTER ジョインと FULL OUTER ジョインをサポートする変形があります。FULL OUTER ジョインのマージ・ジョインは、ネスト・ループ FULL OUTER ジョインよりも効率的です。

    基本のマージ・ジョイン・アルゴリズムは、SQL の集合演算子 EXCEPT と INTERSECT のサポートにも使用されます。これらの変形は、アクセス・プラン内では明示的に EXCEPT アルゴリズムまたは INTERSECT アルゴリズムと呼ばれます。

  • ハッシュ・ジョイン   ハッシュ・ジョインは、SQL Anywhere データベース・サーバでサポートされている最も多用途のジョイン方法です。ハッシュ・ジョイン・アルゴリズムは、2 つの入力のうち小さい方のイン・メモリ・ハッシュ・テーブルを作成してから、大きい方の入力を読み込みます。次に、イン・メモリ・ハッシュ・テーブルを調査して一致するローを検索します。

    ハッシュ・ジョインには、LEFT OUTER ジョイン、FULL OUTER ジョイン、セミジョイン、非セミジョインをサポートする変形があります。また、SQL Anywhere では、再帰 UNION クエリ式が使用されているときに再帰 INNER ジョインと再帰 LEFT OUTER ジョイン用のハッシュ・ジョインの変形がサポートされます。

    ハッシュ内部ジョイン、左外部ジョイン、セミジョイン、非セミジョインのアルゴリズムは並列実行できます。

    アルゴリズムによって構築されたイン・メモリ・ハッシュ・テーブルが使用可能なメモリに収まらない場合は、ハッシュ・ジョイン・アルゴリズムによって入力が分割され (大きな入力の場合は再帰的に)、各分割に対して別々にジョインが実行されます。ジョイン属性が特定の値であるローの格納に十分なキャッシュ・メモリがない場合、可能であれば、各ハッシュ・ジョインは、文のメモリ消費割り当て量を使いつくさないように中間結果を廃棄してから、インデックスベースのネスト・ループ方式に動的に切り替わります。

    ハッシュ・ジョインには、SQL のクエリ式 EXCEPT と INTERSECT をサポートする変形もあります。これらの変形は、アクセス・プラン内では明示的に EXCEPT アルゴリズムまたは INTERSECT アルゴリズムと呼ばれます。


HashJoin アルゴリズム (JH、JHSP、JHFO、JHAP、JHO、JHPO)
RecursiveHashJoin アルゴリズム (JHR)
RecursiveLeftOuterHashJoin アルゴリズム (JHRO)
HashSemijoin アルゴリズム (JHS)
HashAntisemijoin アルゴリズム (JHA)
MergeJoin アルゴリズム (JM、JMFO、JMO)
NestedLoopsJoin アルゴリズム (JNL、JNLFO、JNLO)
NestedLoopsSemijoin アルゴリズム (JNLS)
NestedLoopsAntisemijoin アルゴリズム (JNLA)