はじめに
Railsでは、次のようなコードを日常的に書きます。
Contract.where(company_id: company.id)
このコードは「Railsがデータベースから契約データを取ってくる処理」と読めます。データが取得できていれば動作としては正しいので、それ以上を考える機会は多くありません。
しかし、インデックスの仕組みを知ると、同じコードから別の問いが出てきます。company_id にインデックスが貼られていなければ、MySQLは contracts テーブルの行を先頭から最後まで確認します。データが100件のうちは問題になりませんが、100万件に増えれば100万行を読みます。
インデックスは、検索時に読む行数を減らす仕組みです。その代わりに、データを書き込むたびにインデックスを更新するコストと、保存するためのディスク容量を払います。したがってインデックスは全カラムに貼るものではなく、頻繁かつ重要な検索条件にだけ貼る設計判断になります。
以下では、この判断の根拠となるMySQLとInnoDBの関係、インデックスの内部構造であるB+tree、書き込み側で払うコスト、実務での判断手順の順に説明します。
MySQLとInnoDB、B+treeの関係
インデックスに関わる用語には3つの階層があります。
| 用語 | 役割 |
|---|---|
| MySQL | データベースを操作するシステム全体。SQLを受け取り、実行計画を立てる |
| InnoDB | MySQLの中で、データを実際に保存・管理するストレージエンジン。MySQLのデフォルト |
| B+tree | InnoDBがインデックスの内部構造として使っているデータ構造 |
MySQLは、SQLの解釈と、ディスクへのデータの読み書きを別の部品に分けています。実際にデータを保存・管理する部品をストレージエンジンと呼び、MySQLではInnoDBが標準で使われます。
Contract.where(company_id: company.id) をRailsから投げると、MySQLは「このSQLをどう実行するか」を考えます。そして contracts テーブルがInnoDBで管理されていれば、MySQLは「InnoDBのインデックスを使ってデータを取ろう」と判断します。そのInnoDBが、インデックスの中身としてB+treeを持っています。
B+treeとは何か
MySQLの公式ドキュメントは、InnoDBのインデックスをB-treeインデックスと呼びます。ただし内部で実際に使われている構造はB+treeです。
B+treeは、中間のノードをキーだけにして木を低く保ち、最下層のノード同士を横につなぐことで、等価検索と範囲検索の両方を速くしたデータ構造です。B-treeという別の木構造を、データベース向けに改良したものにあたります。
前提として、木構造は、1つの出発点から枝分かれしていく形でデータを並べる方法です。出発点を根、枝分かれの先端を葉、その間を中間ノードと呼びます。木構造を使うと、全件を先頭から順に見ていく代わりに、根から枝を1つ選んで降りていくだけで済みます。1段降りるごとに探す範囲が大きく減るため、探索が速くなります。B+treeでは、どのデータを探しても根から葉までの距離が同じになるように、高さが偏らない形が保たれます。
B-treeとの違いは、実データを置く場所と、葉ノード同士のつながりの2点です。
違い1: 実データをどこに置くか
B-treeは、根ノードや中間ノードを含めたすべてのノードに、キーと実データの両方を格納します。
B+treeは、中間ノードには探索のガイドとなるキーだけを持たせ、実データは最下層の葉ノードにのみ格納します。
中間ノードから実データを追い出すと、1つのノードにより多くのキーを詰め込めます。1ノードあたりのキーが増えれば、同じ件数を扱うのに必要な木の段数は減ります。木が低くなるほど、根から葉に到達するまでにディスクを読む回数が減るため、検索が速くなります。
違い2: 葉ノード同士がつながっているか
B-treeでは、葉ノード同士がつながっていません。そのため「17以上38以下」のような範囲検索では、木を何度も登り降りして該当ノードを訪問し直す必要があります。
B+treeでは、最下層のすべての葉ノードが、それぞれ隣の葉ノードの位置を持っていて、数珠つなぎに並んでいます。この並べ方を連結リストと呼びます。範囲検索のとき、まず下限である17の葉ノードまで一度降りたら、あとは葉のつながりを横にたどるだけで38以下のデータを回収できます。
この連結のおかげで、BETWEEN や不等号による範囲検索、ORDER BY によるソート済みデータの取得、GROUP BY、そして一覧を一定件数ずつに区切って取り出すページネーションが、高速に処理できます。
InnoDBでは、テーブル自体がB+treeである
InnoDBでは、インデックスだけがB+treeなのではなく、テーブルそのものもB+tree構造で保持されています。行を1件に特定するためのカラム、Railsのモデルであれば id にあたる主キーの順にデータが並んだB+treeがあり、その葉ノードに行データの実体が入っています。
そのため company_id のようなインデックスを追加すると、MySQLは既存のテーブルに検索用の目印を付けるのではなく、company_id をキーとしたB+treeをもう1つ作ります。この「もう1つ作る」という点が、次の章のトレードオフを生みます。
インデックスは貼れば貼るほど良いわけではない
インデックスを追加すると、次のトレードオフが生まれます。
| 項目 | 影響 |
|---|---|
| 検索速度 | 速くなる（読む行数が全行から木の高さぶんに減るため） |
| 書き込み速度 | 遅くなる（更新対象のB+treeが増えるため） |
| ディスク容量 | 増える（B+treeの実体を保存するため） |
書き込みが遅くなるのは、インデックスの更新もしないといけないからです。作られたB+treeは、テーブルのデータが変わるたびに整合性を保たなければなりません。INSERT・UPDATE・DELETE のたびに、テーブル本体の更新に加えて、インデックスの更新も発生します。
このトレードオフを踏まえると、「インデックスを貼らない」という判断もできるようになります。
インデックスを理解していると何が変わるか
Contract.where(company_id: company.id) に company_id のインデックスがなければ、MySQLは contracts テーブルの行を先頭から最後まで確認して、条件に合う行を探します。この動作をフルテーブルスキャンと呼びます。テーブルの行数が少ないうちは影響が表面化しませんが、100万件になればMySQLは100万行を読みます。
インデックスがあれば、company_id をキーとしたB+treeの根から葉へ降りるだけで該当行にたどり着けます。読む量が、テーブルの全行から木の高さぶんに変わります。
この違いを知っていると、性能の問題に当たったとき、Ruby側のコードを速くする方法を探すだけでなく、原因がデータベース側にある可能性を検討できるようになります。
テーブル設計の場面でも、インデックスの知識は判断を変えます。必要なカラムを並べた時点で設計完了とせず、「このデータは実際どういう条件で取得されるのか」を考えるようになります。設計者がインデックスまで意識すれば、テーブル設計と実際のユースケースがつながります。
実務でどう判断するか
インデックスを追加すべきか迷ったときは、読み取りで得られるメリットと、書き込みで払うコストを比べたうえで、頻繁かつ重要な検索パターンにだけ貼ると判断します。具体的には、次の順に確認します。
どの検索条件が多いか
↓
その検索は実際に遅いか
↓
既存のインデックスで効いているか
↓
効いていなければ追加を検討する
貼らない判断が成り立つ例が、監査目的でデータを保存し、書き込みは頻繁に起きるが参照はめったにされないテーブルです。ログ・履歴・イベント系のテーブルがこれに当たります。こうしたテーブルにインデックスを貼ると、めったに使われない検索を速くするために、頻繁に発生する書き込みを毎回遅くすることになります。
EXPLAINでインデックスの使用状況を確認する
上のフローの「既存のインデックスで効いているか」は、想像ではなく実行計画で確認します。実行計画とは、MySQLがそのSQLをどの順序で、どのインデックスを使って処理するつもりかを示した手順書のことで、EXPLAIN で表示できます。
Railsのログに出力されているSQLを取り出し、そのSQLに EXPLAIN を付けて実行すると、インデックスが使われているかを確認できます。RailsのRelationからは、explain を呼ぶだけで実行できます。
Contract.where(company_id: company.id).explain
結果は type と key の2つの列で判断できます。key が NULL で type が ALL なら、インデックスが使われずにテーブル全体を走査しています。この場合はインデックスの追加を検討します。
おわりに
インデックスを理解する前と後で変わるのは、知識の量よりも、コードを見たときに浮かぶ問いです。Contract.where(company_id: company.id) という1行に対して、「取得できるかどうか」だけでなく、「どう取得しているのか」「データが増えても同じ速度で動くのか」を考えるようになります。
普段書いているクエリに EXPLAIN を付けて、インデックスが実際に使われているかを確認するところから始められます。