結合

原文URL: http://www.unofficialmysqlguide.com/joins.html
翻訳者: taka-h (@takaidohigasi)

MySQLは、Nested Loop アルゴリズムを使用して結合(join)を実行します。MySQLは競合となるデータベースで利用可能なハッシュあるいはソートマージといったアルゴリズムはサポートしませんので、いくつかの分析/データウェアハウスのクエリーには適しません。しかしながら、MySQLのオプティマイザには、Nested Loopアルゴリズムの最悪のケースを緩和するためのいくつかのバッファリング戦略があります。

explain-example-23

Nested Loop結合

例23は、Country、City、CountryLanguageの3テーブルの結合例です。このクエリーを実行する全工程は次のようになります。

オプティマイザは最初に駆動表(Country)を決定し、同時にその他のテーブル(City、CountryLanguage)結合に利用するインデックスを決めなければなりません。
実行は最初のテーブル(Country)から始まり、1度に1行ずつ確認します。フィルター条件(Country.Continent='Asia')を満たす各行に対して、次のテーブル(City)内の検索が行われます。
Cityテーブル内の条件に一致した各行に対して、最後のテーブル(CountryLanguage)内の検索が行われます。CountryLanguageテーブルでは追加の条件(IsOfficial=1)が適用されます。

Nested Loopアルゴリズムは、結合を開始する前に処理を省くことができれば一番うまく動作します。つまり「最善のケース」は駆動表に選択度の高い述部があるときである、といえます。

述部が複数のテーブルに分散しており、全てのテーブルが結合される必要がうまれる前にインデックスが処理を十分に取り除けない場合、最悪のケースとなりえます。このような状況では、通例スキーマの非正規化をおこないます。

駆動表に冗長に保持している列を付与し非正規化することにより、複合インデックスが追加可能となり、他のテーブルにJOINしたりアクセスする前にフィルタリング可能となります。

例23: 3テーブルに対するNested Loop結合

EXPLAIN FORMAT=JSON
SELECT
  Country.Name as Country, City.Name as Capital, Language
FROM
  City
  INNER JOIN Country ON Country.Capital=City.id
  INNER JOIN CountryLanguage ON CountryLanguage.CountryCode=Country.code
WHERE
  Country.Continent='Asia' and CountryLanguage.IsOfficial='T';
{
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "3.42"
    },
    "nested_loop": [
      {
        "table": {
          "table_name": "Country",
          "access_type": "const",
          "possible_keys": [
            "PRIMARY"
          ],
          "key": "PRIMARY",
          "used_key_parts": [
            "Code"
          ],
          "key_length": "3",
          "ref": [
            "const"
          ],
          "rows_examined_per_scan": 1,
          "rows_produced_per_join": 1,
          "filtered": "100.00",
          "cost_info": {
            "read_cost": "0.00",
            "eval_cost": "0.20",
            "prefix_cost": "0.00",
            "data_read_per_join": "264"
          },
          "used_columns": [
            "Code",
            "Name",
            "Capital"
          ]
        }
      },
      {
        "table": {
          "table_name": "City",
          "access_type": "const",
          "possible_keys": [
            "PRIMARY"
          ],
          "key": "PRIMARY",
          "used_key_parts": [
            "ID"
          ],
          "key_length": "4",
          "ref": [
            "const"
          ],
          "rows_examined_per_scan": 1,
          "rows_produced_per_join": 1,
          "filtered": "100.00",
          "cost_info": {
            "read_cost": "0.00",
            "eval_cost": "0.20",
            "prefix_cost": "0.00",
            "data_read_per_join": "72"
          },
          "used_columns": [
            "ID",
            "Name"
          ]
        }
      },
      {
        "table": {
          "table_name": "CountryLanguage",
          "access_type": "ref",
          "possible_keys": [
            "PRIMARY",
            "CountryCode"
          ],
          "key": "PRIMARY",
          "used_key_parts": [
            "CountryCode"
          ],
          "key_length": "3",
          "ref": [
            "const"
          ],
          "rows_examined_per_scan": 12,
          "rows_produced_per_join": 6,
          "filtered": "50.00",
          "cost_info": {
            "read_cost": "1.02",
            "eval_cost": "1.20",
            "prefix_cost": "3.42",
            "data_read_per_join": "240"
          },
          "used_columns": [
            "CountryCode",
            "Language",
            "IsOfficial"
          ],
          "attached_condition": "(`world`.`CountryLanguage`.`IsOfficial` = 'T')"
        }
      }
    ]
  }
}

INNER JOIN

INNER JOINはその意味上からある行が結合テーブルの左、右両方にある必要があります。これを念頭に置くと、MySQLは2つのテーブルをどちらの順にでも結合できることを意味します。オプティマイザにはコストが最小となる順序を選択する役割があります。

LEFT JOINおよびRIGHT JOIN

LEFT JOINは結合の右側の行が任意であり必須ではありません(すなわちRIGHT JOINは左側が必須ではありません)。結合において片側が必須ではないため、データが存在する方から実行を開始します。結合順が決められるため、オプティマイザはINNER JOINの際には考慮していたとりうる順序(実行計画)を考慮することができません。結果的にLEFT JOINは比較的遅いということにつながります。

Condition Fanout Filter

MySQL 5.7から、オプティマイザは駆動表以外の絞込みの効果を考慮しています。condition_filteringは3つめ以降のテーブルの結合順をより良くするために利用されます。

condition filterはヒストグラムに適しており、これを利用しないと、偏りがある、あるいは不均一なデータ分布のときに、より単純なヒューリスティックアルゴリズムで不正確な見積もりとなりえます。condition_filterはインデックスから利用できる統計(これはもうすこしコストがかかります)も利用しています。

Tips

MySQL 5.7ではデータの偏りがある場合condition fanout filterにより多数の性能上のリグレッションがありました。MySQL 8.0では結合条件の考慮にヒストグラムを追加することを検討しています。