【SQL】JOIN(Nested loop join)の仕組みを理解し、インデックスで高速化する

SQLのJOINで利用される代表的な結合方法にはNested loop join（NLJ、ネステッドループ結合）、Merge join（マージ結合、ソートマージ）、Hash join（ハッシュ結合、ハッシュ値マッチング）の3種類があります。1 2 このうちNested loop joinはJOINの最も基本的なアルゴリズムで、多くのRDBMSで利用可能です。

今回はインデックスを活用したNested loop joinの高速化について紹介します。

MySQLは5.7.34を利用しています。

なお、本記事の検証はMySQL 5.7時点のものですが、MySQL 8.0以降の状況については後述の「MySQL 8.0以降のハッシュ結合（Hash Join）対応」を参照してください。

Nested loop joinのしくみについて

Nested loop joinを利用したテーブルの結合の手順は以下の通りです。

1行ずつレコードが取り出される外側テーブルのことを『駆動表（外表、外部表）』、結合対象のレコードが検索される内側テーブルのことを『内部表（内表）』と呼びます。

Nested loop joinの流れを図で表現すると以下のようになります。

駆動表のレコード数をm、内部表のレコード数をnとした場合、Nested loop joinでは単純計算するとm x n回レコードの結合検証が行われます。

Nested loop joinを高速化するアプローチ

Nested loop joinを高速化するには2つのアプローチが考えられます。

前者はSQL自体を改善するアプローチです。

WHEREなどで結合対象のレコード数を絞り込むことで結合検証の回数(m x n)を減らし、Nested loop joinの高速化を図ります。

今回は後者のインデックスを活用したNested loop joinの高速化について紹介します。

インデックスを利用したNested loop joinの高速化

Nested loop joinの処理の中でインデックスによる高速化が期待できる箇所は以下の2点です。

駆動表にインデックスを作成することで、結合対象を検索する際に駆動表のフルテーブルスキャンが不要になります。イメージ図は以下の通りです。

内部表にインデックスを作成することで、結合時に駆動表1レコードごとで行っていた内部表のフルテーブルスキャンが不要になります。イメージ図は以下の通りです。

インデックスによるNested loop joinのチューニング例

1対多で紐づくusersテーブルとbooksテーブルを結合し、userのageが30のbooksレコードを取得するSQLをチューニングしてみます。

説明の便宜上、STRAIGHT_JOINを利用してusersテーブルを駆動表、booksテーブルを内部表に固定しています。

SELECT STRAIGHT_JOIN b.* FROM users u, books b WHERE u.id = b.user_id AND u.age = 30;

なお、usersテーブルおよびbooksテーブルにはPrimary key以外にインデックスは作成されていないとします。

インデックス作成前

インデックスが作成されていない場合、EXPLAINの結果は以下のようになります。

JOINの場合は駆動表、内部表の順番でEXPLAINに表示されるため、今回の場合はusersテーブルが駆動表、booksテーブルが内部表となります。

> EXPLAIN SELECT STRAIGHT_JOIN b.* FROM users u, books b WHERE u.id = b.user_id AND u.age = 30\G;

*************************<strong> 1. row </strong>*************************
           id: 1
  select_type: SIMPLE
        table: u
   partitions: NULL
         type: ALL
possible_keys: PRIMARY
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 996364
     filtered: 10.00
        Extra: Using where
*************************<strong> 2. row </strong>*************************
           id: 1
  select_type: SIMPLE
        table: b
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2980163
     filtered: 10.00
        Extra: Using where; Using join buffer (Block Nested Loop)
2 rows in set, 1 warning (0.00 sec)

1. rowは駆動表から結合対象のレコードを検索するクエリ、2. rowは結合条件を満たす内部表のレコードを検索するクエリです。

typeに表示されているALLはフルテーブルスキャンが実行されていることを意味します。

typeにALLが表示されるクエリは改善が必要です。

keyがNULLなので当該クエリではインデックスは利用されていないことがわかります。

EXPLAINの読み方の詳細解説はMySQLのEXPLAINの読み方とチューニング時のチェックポイントで紹介しています。

結合対象のレコード検索の高速化

検索条件はu.age = 30ですので、usersテーブルのageに対してインデックスを作成すれば駆動表のフルテーブルスキャンをせずに済みます。

usersテーブルのageにインデックスを作成後、再度EXPLAINを実行すると結果は以下のようになります。

> EXPLAIN SELECT STRAIGHT_JOIN b.* FROM users u, books b WHERE u.id = b.user_id AND u.age = 30\G;

*************************<strong> 1. row </strong>*************************
           id: 1
  select_type: SIMPLE
        table: u
   partitions: NULL
         type: ref
possible_keys: PRIMARY,index_users_on_age
          key: index_users_on_age
      key_len: 5
          ref: const
         rows: 22196
     filtered: 100.00
        Extra: Using index
*************************<strong> 2. row </strong>*************************
           id: 1
  select_type: SIMPLE
        table: b
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2980163
     filtered: 10.00
        Extra: Using where; Using join buffer (Block Nested Loop)
2 rows in set, 1 warning (0.00 sec)

駆動表のレコードの絞り込みをする1. rowのクエリにおいて、keyにindex_users_on_ageが表示されたので、インデックスが利用されていることがわかります。

インデックスが利用されるようになったため、1番目のクエリのtypeがALLからref（ユニークではないインデックスによる等価検索）に変更されました。

結合条件を満たすレコード検索の高速化

結合条件はu.id = b.user_idですので、booksテーブルのuser_idに対してインデックスを作成すれば内部表のフルテーブルスキャンをせずに済みます。

booksテーブルのuser_idにインデックスを作成後、再度EXPLAINを実行すると結果は以下のようになります。

> EXPLAIN SELECT STRAIGHT_JOIN b.* FROM users u, books b WHERE u.id = b.user_id AND u.age = 30\G;

*************************<strong> 1. row </strong>*************************
           id: 1
  select_type: SIMPLE
        table: u
   partitions: NULL
         type: ref
possible_keys: PRIMARY,index_users_on_age
          key: index_users_on_age
      key_len: 5
          ref: const
         rows: 22196
     filtered: 100.00
        Extra: Using index
*************************<strong> 2. row </strong>*************************
           id: 1
  select_type: SIMPLE
        table: b
   partitions: NULL
         type: ref
possible_keys: index_books_on_user_id
          key: index_books_on_user_id
      key_len: 5
          ref: rails6_api_mysql8_development.u.id
         rows: 3
     filtered: 100.00
        Extra: Using index condition
2 rows in set, 1 warning (0.00 sec)

結合条件でインデックスが利用されるようになったため、2番目のクエリのtypeがALLからrefにかわりました。

MySQL 8.0以降のハッシュ結合（Hash Join）対応

MySQLは伝統的にNested Loop Join（およびその変種であるBlock Nested Loop, BNL）のみをサポートしてきました。

本記事のEXPLAIN結果に表示されているUsing join buffer (Block Nested Loop)はBNLのフォールバック動作で、内部表にインデックスが無い場合に駆動表のレコードをまとめてバッファに乗せて結合する方式です。

MySQL 8.0以降は、これまでBNLでフォールバックしていたケースに対してハッシュ結合（Hash Join）が選択されるようになりました（MySQL 8.0 リファレンス - ハッシュ結合最適化）。

バージョン	変化
MySQL 8.0.18	Hash Join機能の導入。等価結合かつ両側にインデックスがない場合に選択
MySQL 8.0.20	BNL（Block Nested Loop）が無効化され、内部表にインデックスがない結合は基本的にHash Joinに置き換わる

EXPLAIN FORMAT=TREEでは以下のような表示になります。

EXPLAIN FORMAT=TREE SELECT b.* FROM users u JOIN books b ON u.id = b.user_id WHERE u.age = 30;

-> Inner hash join (b.user_id = u.id)  (cost=...)
    -> Table scan on b
    -> Hash
        -> Index lookup on u using index_users_on_age (age=30)

Inner hash joinという表記が出ていればHash Joinが選択されています。

結合アルゴリズム別のインデックス戦略

結合アルゴリズムによって、インデックスを作成すべき箇所と効果が変わります。

結合アルゴリズム	特徴	インデックスの効き方
Nested Loop Join	駆動表の各行に対し内部表を都度検索	内部表の結合キーにインデックスが効く。無いと内部表をm回スキャンすることになり致命的に遅い
Hash Join	内部表（小さい側）をハッシュテーブル化し、駆動表をプローブ	インデックスは原則不要。等価結合でメモリに収まる範囲なら大量行の結合でも高速
Sort Merge Join	両側を結合キーでソートして突き合わせ	両側の結合キーにインデックスがあるとソート処理を省略できる。範囲結合にも対応

実装上の選択指針:

• 小→大のJOIN・選択的なWHERE句あり → NLJ + 内部表インデックスが最も効く。本記事の例はこのケース
• 大→大のJOIN・選択的な絞り込みなし → Hash Joinが有利。MySQL 8.0以降は自動で選択される
• 両側がソート済み（PK同士のJOINなど） → Sort Merge Joinが有利だが、MySQLは標準ではサポートしない（PostgreSQL/Oracleはサポート）

「インデックスを作っても結合が速くならない」と感じる場合、選択されているアルゴリズムがNested Loop Join以外（特にHash Join）になっている可能性があります。

EXPLAIN FORMAT=TREEで実際のアルゴリズムを確認したうえでチューニング方針を決めるとよいです。

まとめ

Twitter(@nishina555)やってます。フォローしてもらえるとうれしいです！

参考

• 実例で学ぶ、JOIN (NLJ) が遅くなる理屈と対処法
• SQLチューニング入門 入門編
• チューニング ～ SQLチューニングを実施する ～