このページは機械翻訳したものです。

8.2.1.8 ネストした結合の最適化

結合を表す構文では、ネストした結合を使用できます。 次の説明は、セクション13.2.10.2「JOIN 句」に説明する結合構文について言及しています。

table_factor の構文は SQL 標準と比較して拡張されています。 後者は table_reference のみを受け付け、かっこ内のそれらのリストは受け付けません。 これは、table_reference 項目のリストの各カンマを内部結合と同等とみなす場合、保守的な拡張です。 例:

SELECT * FROM t1 LEFT JOIN (t2, t3, t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

次と同等です:

SELECT * FROM t1 LEFT JOIN (t2 CROSS JOIN t3 CROSS JOIN t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

MySQL では、CROSS JOIN は INNER JOIN と構文的に同等であり、相互に置換できます。 標準 SQL では、それらは同等ではありません。 INNER JOIN は ON 句と一緒に使用します。CROSS JOIN はそうでない場合でも使用できます。

一般に、内部結合操作のみを含む結合式内のかっこは無視できます。 次の結合式について考えてみます:

t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL)
   ON t1.a=t2.a

左のカッコおよびグループ化操作を削除すると、その結合式は次の式に変換されます:

(t1 LEFT JOIN t2 ON t1.a=t2.a) LEFT JOIN t3
    ON t2.b=t3.b OR t2.b IS NULL

まだ、2 つの式は同等ではありません。 これを確認するには、テーブル t1、t2、t3 が次の状態であるとします。

• テーブル t1 には行 (1)、(2) が含まれます

• テーブル t2 には行 (1,101) が含まれます

• テーブル t3 には行 (101) が含まれます

この場合、最初の式は行 (1,1,101,101)、(2,NULL,NULL,NULL) を含む結果セットを返し、2 番目の式は行 (1,1,101,101)、(2,NULL,NULL,101) を返します。

mysql> SELECT *
       FROM t1
            LEFT JOIN
            (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL)
            ON t1.a=t2.a;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL | NULL |
+------+------+------+------+

mysql> SELECT *
       FROM (t1 LEFT JOIN t2 ON t1.a=t2.a)
            LEFT JOIN t3
            ON t2.b=t3.b OR t2.b IS NULL;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL |  101 |
+------+------+------+------+

次の例では、外部結合操作が内部結合操作と一緒に使用されています。

t1 LEFT JOIN (t2, t3) ON t1.a=t2.a

その式は次の式に変換できません。

t1 LEFT JOIN t2 ON t1.a=t2.a, t3

指定されたテーブル状態では、次の 2 つの式は異なる行セットを返します。

mysql> SELECT *
       FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL | NULL |
+------+------+------+------+

mysql> SELECT *
       FROM t1 LEFT JOIN t2 ON t1.a=t2.a, t3;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL |  101 |
+------+------+------+------+

したがって、外部結合演算子を含む結合式のかっこを省略すると、元の式の結果セットが変わることがあります。

正確に言えば、左外部結合操作の右オペランドと右結合操作の左オペランドのかっこを無視することはできません。 言い換えれば、外部結合操作の内部テーブル式のかっこを無視することはできません。 ほかのオペランド (外部テーブルのオペランド) のかっこは無視できます。

次の式:

(t1,t2) LEFT JOIN t3 ON P(t2.b,t3.b)

属性 t2.b および t3.b に対する任意のテーブル t1,t2,t3 および任意の条件 P のこの式と同等です:

t1, t2 LEFT JOIN t3 ON P(t2.b,t3.b)

結合式 (joined_table) での結合操作の実行順序が左から右にならない場合は、ネストされた結合について説明します。 次のクエリーを考慮します。

SELECT * FROM t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b) ON t1.a=t2.a
  WHERE t1.a > 1

SELECT * FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a
  WHERE (t2.b=t3.b OR t2.b IS NULL) AND t1.a > 1

それらのクエリーは次のネストした結合が含まれるとみなされます。

t2 LEFT JOIN t3 ON t2.b=t3.b
t2, t3

最初のクエリーでは、ネストされた結合は左結合操作で形成されます。 2 番目のクエリーでは、内部結合操作を使用して形成されます。

最初のクエリーでは、カッコを省略できます: 結合式の文法構造によって、結合操作の実行順序が同じになります。 2 番目のクエリーでは、かっこを省略できますが、それらがなくてもここの結合式は一義的に解釈できます。 拡張構文では、理論的にはクエリーは解析されますが、2 番目のクエリーの (t2, t3) にカッコが必要です: LEFT JOIN および ON は式 (t2,t3) の左右のデリミタの役割を果たすため、クエリーの構文構造は明確なままです。

前の例でこれらの点を説明します。

• 内部結合のみを含む (外部結合を含まない) 結合式の場合は、カッコを削除して、左から右に結合を評価できます。 実際には、テーブルは任意の順序で評価できます。

• 一般に、外部結合、または内部結合と混在した外部結合の場合には、同じことが当てはまりません。 かっこの削除によって、結果が変わることがあります。

ネストした外部結合を含むクエリーは内部結合を含むクエリーと同じパイプライン方式で実行されます。 正確には、Nested Loop 結合アルゴリズムのバリエーションが利用されます。 ネステッドループ結合でクエリーを実行するアルゴリズムを思い出します (セクション8.2.1.7「Nested Loop 結合アルゴリズム」 を参照)。 3 つのテーブルに対する結合クエリー T1,T2,T3 が次の形式であるとします:

SELECT * FROM T1 INNER JOIN T2 ON P1(T1,T2)
                 INNER JOIN T3 ON P2(T2,T3)
  WHERE P(T1,T2,T3)

ここでは、P1(T1,T2) と P2(T3,T3) が何らかの結合条件 (式での) で、P(T1,T2,T3) はテーブル T1,T2,T3 のカラムに対する条件です。

Nested Loop 結合アルゴリズムでは、このクエリーを次のように実行します。

FOR each row t1 in T1 {
  FOR each row t2 in T2 such that P1(t1,t2) {
    FOR each row t3 in T3 such that P2(t2,t3) {
      IF P(t1,t2,t3) {
         t:=t1||t2||t3; OUTPUT t;
      }
    }
  }
}

t1||t2||t3 という表記法は、t1、t2 および t3 の行のカラムを連結して構築された行を示します。 次の例の一部では、テーブル名が表示される NULL は、そのテーブルの各カラムに NULL が使用される行を意味します。 たとえば、t1||t2||NULL は、t3 のカラムごとに行 t1 および t2 のカラムと NULL を連結して構築された行を示します。 このような行は、NULL で補完されていると言われます。

ここで、ネストされた外部結合を含むクエリーについて考えてみます:

SELECT * FROM T1 LEFT JOIN
              (T2 LEFT JOIN T3 ON P2(T2,T3))
              ON P1(T1,T2)
  WHERE P(T1,T2,T3)

このクエリーでは、ネステッドループパターンを変更して次のものを取得します:

FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t2 in T2 such that P1(t1,t2) {
    BOOL f2:=FALSE;
    FOR each row t3 in T3 such that P2(t2,t3) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f2=TRUE;
      f1=TRUE;
    }
    IF (!f2) {
      IF P(t1,t2,NULL) {
        t:=t1||t2||NULL; OUTPUT t;
      }
      f1=TRUE;
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}

一般に、外部結合操作の最初の内部テーブルのネストしたループでは、ループの前にオフにされ、ループのあとにチェックされるフラグが導入されます。 フラグは、外部テーブルの現在行で、内側オペランドを表すテーブルからの一致が見つかったときにオンにされます。 ループサイクルの最後でフラグがまだオフの場合は、外部テーブルの現在行で一致が見つかりませんでした。 この例では、行が内部テーブルのカラムの NULL 値で補完されます。 結果の行は、出力の最終チェックまたは次のネストしたループに渡されますが、行が、埋め込まれたすべての外部結合の結合条件を満たしている場合に限られます。

この例では、次の式でテーブルされる外部結合テーブルが埋め込まれています:

(T2 LEFT JOIN T3 ON P2(T2,T3))

内部結合を含むクエリーの場合、オプティマイザは次のように、ネステッドループの異なる順序を選択できます:

FOR each row t3 in T3 {
  FOR each row t2 in T2 such that P2(t2,t3) {
    FOR each row t1 in T1 such that P1(t1,t2) {
      IF P(t1,t2,t3) {
         t:=t1||t2||t3; OUTPUT t;
      }
    }
  }
}

外部結合を使用するクエリーの場合、オプティマイザは、外部テーブルのループが内部テーブルのループより前にある順序のみを選択できます。 つまり、外部結合を含むクエリーでは、1 つだけのネスト順序しか使用できません。 次のクエリーでは、オプティマイザは 2 つの異なるネストを評価します。 両方のネストで、T1 は外部結合で使用されているため、外側のループで処理される必要があります。 T2 と T3 は内部結合で使用されているため、その結合は内側のループで処理される必要があります。 ただし、結合は内部結合であるため、T2 と T3 はどちらの順序でも処理できます。

SELECT * T1 LEFT JOIN (T2,T3) ON P1(T1,T2) AND P2(T1,T3)
  WHERE P(T1,T2,T3)

あるネストによって T2 が評価され、次に T3 が評価されます:

FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t2 in T2 such that P1(t1,t2) {
    FOR each row t3 in T3 such that P2(t1,t3) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f1:=TRUE
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}

もう一方のネストでは、T3 を評価してから、T2 を評価します:

FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t3 in T3 such that P2(t1,t3) {
    FOR each row t2 in T2 such that P1(t1,t2) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f1:=TRUE
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}

内部結合の Nested Loop アルゴリズムについて説明した際に、クエリー実行のパフォーマンスに与える影響が大きい場合があるという詳細については省きました。 いわゆる「プッシュダウン」 条件については説明しませんでした。 たとえば、WHERE 条件 P(T1,T2,T3) を論理積標準形によって表現できるとします。

P(T1,T2,T2) = C1(T1) AND C2(T2) AND C3(T3).

この場合、MySQL では、内部結合を使用したクエリーの実行に次のネステッドループアルゴリズムが実際に使用されます:

FOR each row t1 in T1 such that C1(t1) {
  FOR each row t2 in T2 such that P1(t1,t2) AND C2(t2)  {
    FOR each row t3 in T3 such that P2(t2,t3) AND C3(t3) {
      IF P(t1,t2,t3) {
         t:=t1||t2||t3; OUTPUT t;
      }
    }
  }
}

等位項 C1(T1)、C2(T2)、C3(T3) がそれぞれ、もっとも内側のループから、評価可能なもっとも外側のループまで押し出されることがわかります。 C1(T1) がきわめて制限の強い条件である場合、このコンディションプッシュダウンによって、テーブル T1 から内側ループに渡される行数が大幅に少なくなることがあります。 結果として、クエリーの実行時間が大幅に短縮される可能性があります。

外部結合を含むクエリーでは、外部テーブルの現在行で内部テーブルに一致があることが見つかったあとにのみ、WHERE 条件がチェックされます。 そのため、内側のネストしたループからのプッシュ条件の最適化は、外部結合を含むクエリーには直接適用できません。 ここでは、一致が発生したときにオンになるフラグで保護される条件付きプッシュダウン述語を導入する必要があります。

外部結合を使用した次の例を思い出してください:

P(T1,T2,T3)=C1(T1) AND C(T2) AND C3(T3)

この例では、保護されたプッシュダウン条件を使用するネステッドループアルゴリズムは次のようになります:

FOR each row t1 in T1 such that C1(t1) {
  BOOL f1:=FALSE;
  FOR each row t2 in T2
      such that P1(t1,t2) AND (f1?C2(t2):TRUE) {
    BOOL f2:=FALSE;
    FOR each row t3 in T3
        such that P2(t2,t3) AND (f1&&f2?C3(t3):TRUE) {
      IF (f1&&f2?TRUE:(C2(t2) AND C3(t3))) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f2=TRUE;
      f1=TRUE;
    }
    IF (!f2) {
      IF (f1?TRUE:C2(t2) && P(t1,t2,NULL)) {
        t:=t1||t2||NULL; OUTPUT t;
      }
      f1=TRUE;
    }
  }
  IF (!f1 && P(t1,NULL,NULL)) {
      t:=t1||NULL||NULL; OUTPUT t;
  }
}

一般に、プッシュダウン述語は P1(T1,T2) や P(T2,T3) などの結合条件から抽出できます。 この場合、プッシュダウン述語は、対応する外部結合操作によって生成される NULL が補完された行の述語のチェックを妨げるフラグによっても保護されます。

同じネストされた結合内のある内部テーブルから別のテーブルへのキーによるアクセスは、WHERE 条件から述語によって誘導された場合は禁止されます。