Documentation Home
MySQL 5.6 リファレンスマニュアル
Download this Manual
PDF (US Ltr) - 26.8Mb
PDF (A4) - 26.9Mb
HTML Download (TGZ) - 7.1Mb
HTML Download (Zip) - 7.2Mb


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

結合を表す構文では、ネストした結合を使用できます。次の説明は、セクション13.2.9.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 JOININNER JOIN と構文上同等です (それらは相互に置き換え可能です)。標準 SQL では、それらは同等ではありません。INNER JOINON 句と一緒に使用します。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 つの式は同等ではありません。これを確認するには、テーブル t1t2t3 が次の状態であるとします。

  • テーブル 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)

は次の式と同等です。

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

任意のテーブル t1,t2,t3 と属性 t2.b および t3.b に対する任意の条件 P の場合。

結合式 (join_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 JOINON が式 (t2,t3) の左と右の区切り文字の役割を果たすため、クエリーの構文構造が一義的になります。)

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

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

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

ネストした外部結合を含むクエリーは内部結合を含むクエリーと同じパイプライン方式で実行されます。正確には、Nested Loop 結合アルゴリズムのバリエーションが利用されます。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 は、t1t2、および t3 のカラムを連結させて行が構築されることを意味します。次のいくつかの例では、行名が表示される場所の NULL は、その行の各カラムに NULL が使用されることを意味します。たとえば、t1||t2||NULL は、行 t1t2 のカラムと、t3 の各カラムの NULL を連結させて行が構築されることを意味します。

ここで、ネストした外部結合のあるクエリーを考慮しましょう。

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

このクエリーでは、Nested Loop パターンを変更して、次を取得します。

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 つの異なるネストを評価します。

SELECT * T1 LEFT JOIN (T2,T3) ON P1(T1,T2) AND P2(T1,T3)
  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) {
    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;
    }
  }
}

および:

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;
    }
  }
}

両方のネストで、T1 は外部結合で使用されているため、外側のループで処理される必要があります。T2T3 は内部結合で使用されているため、その結合は内側のループで処理される必要があります。ただし、結合は内部結合であるため、T2T3 はどちらの順序でも処理できます。

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

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

この場合、MySQL は実際に内部結合を含むクエリーの実行に、次の Nested Loop スキーマを使用します。

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)

保護されたプッシュダウン条件を使用した Nested Loop スキーマは次のようになります。

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 条件からの述語によって引き起こされている場合に、禁止されます。(この例では、条件付きキーアクセスを使用できますが、この手法はまだ MySQL 5.6 に採用されていません。)