👋

[MySQL]もう一度学ぶインデックスとカーディナリティ

2022/07/15に公開

MySQL

SQL

tech

はじめに

こんにちは、M-Yamashitaです。

今回の記事は、インデックスとカーディナリティについての話です。

この執筆のきっかけは、私がある機能を作った際に、インデックスをうまく使えていないためにパフォーマンス低下を招いてしまったためです。当時、私はインデックスについてなんとなく知っていたものの、仕組みをあまり理解できていないために起きた問題でした。そのため、インデックスとは何なのか、またインデックスを使うときに出てくるカーディナリティとは何かについて説明します。

MySQLについてあまり詳しくないため、間違っている箇所等あれば指摘をお願いします。
なお、本記事ではMySQL 5.7の環境を前提とします。

この記事で伝えたいこと

インデックスの概要、およびインデックスに採用しているB-treeについて
複合インデックスの概要と注意点
カーディナリティの概要と注意点

前提

本記事では、以下customersテーブルを使用します。

CREATE TABLE `customers` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `first_name` varchar(255) DEFAULT NULL,
  `last_name` varchar(255) DEFAULT NULL,
  `region_id` int(11) DEFAULT NULL,
  `created_at` datetime(6) NOT NULL,
  `updated_at` datetime(6) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `index_customers_on_region_id` (`region_id`)
  KEY `index_customers_on_region_id_and_last_name` (`region_id`,`last_name`)
)

主キーはid、インデックスはregion_id、複合インデックスは(region_id, last_name)とします。

インデックスとは

インデックスの説明

MySQLの公式ドキュメントから引用します。

Indexes are used to find rows with specific column values quickly. Without an index, MySQL must begin with the first row and then read through the entire table to find the relevant rows. The larger the table, the more this costs. If the table has an index for the columns in question, MySQL can quickly determine the position to seek to in the middle of the data file without having to look at all the data. This is much faster than reading every row sequentially.

Most MySQL indexes (PRIMARY KEY, UNIQUE, INDEX, and FULLTEXT) are stored in B-trees.

まとめると

インデックスは特定のカラムを素早く検索することに使用される
インデックスを使うことでテーブルすべてのデータを見る必要がなくなる
ほとんどのMySQLのインデックスはB-treeに格納されている

となります。インデックスは本の索引のような役割と考えるとイメージしやすいと思います。

B-tree

インデックスの説明で出てきたB-treeとは、木構造で表されるデータ構造です。
B-treeのポイントとして以下の点があります

ノードとリーフにそれぞれ値を持っている
検索や挿入、削除にかかる計算量が、平均でも最悪の場合でもO(log n)

https://ja.wikipedia.org/wiki/B木

ノードとリーフに値を持っているため、B-treeでの検索では、検索対象の値をノードから順に探っていき、値が見つかった時点で検索を終了します。
また、計算量がO(log n)であることから、B-treeで持つ値の数nが100倍に増えたとしても、検索にかかる時間はlog 100nで済みます。そのため、テーブルスキャンのような線形検索よりも圧倒的に検索時間が少なくて済みます。

B-treeをイメージ図で表すと以下のようになります。これは、[1, 2, 3, 7, 9, 10, 12, 13, 14, 16, 17, 18, 20, 22, 23, 26, 27, 28]といった数値があるときに、B-treeとして表したときの図となります。

b-tree

B+tree

MySQLのインデックスは、実際にはB+treeを使用しています。B+treeは基本的にはB-treeと同じであり、計算量も同じですが、主に以下の違いがあります。

リーフでは、ツリーのポインターであるKeyと、それに対応するValueを持つ。
- MySQLではValueに主キーや、実際の行データを持つ。（後述のクラスター化インデックスとセカンダリインデックスを参照）
ノードではValueを持たず、Keyのみ持つ。
リーフは隣のリーフのポインターを持つ。

customersテーブルのregion_idのインデックスを例に考えてみます。
region_idが1~100までの値を持っている場合、B+treeのイメージ図で表すと以下のようになります。なお、この図でのdataにはcustomersテーブルの主キーが入ります。

b+tree

補足なぜB-treeではなくB+treeを使用しているのか？

B+treeの採用理由を考えるにあたり、まず、2分探索ではなくB-tree方式を採用した背景から説明します。この背景を基に、B+tree採用の理由を推測します。

なぜ2分探索ではなくB-tree方式をインデックスに採用したのか？

MySQLがリリースされた1994年は、SSDよりもHDDを使用してデータを読み込んでいた時代でした。このHDDの特性については、こちらの記事から引用します。

ハードディスクからデータを読み取る場合、あるサイズ単位の塊でデータを読み取ります。この塊をブロックと呼び、512バイトや1024バイトなどファイルシステム・設定によって様々です。

小さなデータを沢山読み取る必要がある場合、複数のブロックを読み取る必要があります。複数のブロックを読み取る必要があるということは、ハードディスクのヘッドの移動やディスクの回転などを伴うため、非常に遅くなってしまいます（メモリ読み込み時間やCPUの演算速度と比べて)

つまりハードディスクを効率的に扱うには、なるべくブロックの読み取り回数を少なくして機械駆動の部分を使わないことです。

またHDDとB-treeの相性についても、記事で触れられています。

m階のBTreeは1つのノードにm-1個の値を持つことができました。このノードを1ブロックに収まるようにすることで、BTreeを使った探索を行うときにブロックの読み取り回数を最小限に抑えることができます。

例えばハードディスクのブロックサイズが512バイトだった場合、int型(4バイト)の値を1ブロックに128個保存することができます。これはint型のカラムにIndexを貼ったい場合に129階のBTreeを構成できることを表します。 (実際は子ノードのブロック位置を保存する必要もあるので、128より少なくなります)
一方、二分探索木の場合は1つのノードに1つの値しか入れていません。同じブロックに入っているノードもありますが、探索する順序やIndexの構成によっては全て異なるブロックを読み取らないといけない可能性もあります。

このような理由によってBTreeはハードディスクと相性が良いと言われており、Indexの実現方法として採用されています。

これらをまとめると、

MySQL開発当時に主に使用されていたHDDを効率的に使用するためにB-tree方式を採用した

となります。

なぜB-treeではなくB+treeを採用したのか？

それでは本題です。なぜB+treeを採用しているのでしょうか？
この理由は、以下3つの点でB+treeがB-treeよりも優れているためだと思われます。

検索や挿入が簡単で速い
リーフが隣のリーフの位置を知っているので、シーケンシャルなアクセスにも向いている
1度のHDDの読み込みで多くのノードを読み込める

1や2の詳細については、以下記事のdifference between B-tree and B+ tree:項目の表に、記載があります。

この表では、リーフにデータを持っているため、検索や挿入が簡単で速いとあります。また、リーフが隣のリーフの位置を知っているLinkedList構造になっているので、シーケンシャルなアクセスに向いていることも記載されています。

3については、さきほどのHDDの特性を考慮すると、検索でHDDからノードを読み込む際、1ブロックに多くのデータを持っている方が望ましいと思われます。B+treeのノードはKeyしか持っていないため、1度のHDDの読み込みで、B-treeよりも多くのノードを読み込むことができます。

これらの理由から、B+treeを採用していると考えられます。

その他参考資料

https://christina04.hatenablog.com/entry/2017/05/17/190000

インデックスが使用される演算子

クエリを実行したとき、インデックスが使用される演算子については、MySQLの公式ドキュメントでは以下のように説明されています。

A B-tree index can be used for column comparisons in expressions that use the =, >, >=, <, <=, or BETWEEN operators. The index also can be used for LIKE comparisons if the argument to LIKE is a constant string that does not start with a wildcard character.

この説明から分かる通り、=, >、>=, <、<=, BETWEEN演算子をクエリで使っている場合は、インデックスが使用されます。またLIKEに関しては、最初の文字がワイルドカードで始まらない文字列であれば、インデックスが使用されます。

実際のクエリで考えてみます。以下のLIKEを使用したクエリの場合は、インデックスが使用されます。
（クエリはMySQLの公式ドキュメントに載っている例から引用しています。）

SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

逆に以下のようなクエリは、インデックスが使用されません。

SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE other_col;

使用されない理由としては以下のとおりです。

1つ目の%Patrick%を持つクエリは、最初がワイルドカードで始まっていること
2つ目のクエリについては文字列ではないため

LIKEにおいて、最初の文字がワイルドカードでない場合にインデックスが使用される理由については、さきほどのB+treeの構造によるものです。リーフがLinkedList構造になっているので、LIKEに使用した文字列の最初が固定されていれば、B+treeの特定のリーフから範囲検索できるためです。
逆に、ワイルドカードを文字列の最初に使ってしまうと、どのリーフを基準に検索すればよいか分からないため、インデックスが使用されません。その結果、テーブルスキャンになってしまう可能性があります。
参考:

クラスター化インデックスとセカンダリインデックス

クラスター化インデックス

MySQLが使用しているInnoDBでは、リーフに行データが格納された、クラスター化インデックスと呼ばれる特殊なインデックスを持っています。クラスター化インデックスは、主キーのインデックスの別名のようなものです。
つまり、「クラスター化インデックス＝主キーのインデックス」ということです。

customersテーブルを例にすると、customersテーブルの主キーはidとなっているので、customersテーブルのクラスター化インデックスは主キーidのインデックスとなります。

このクラスター化インデックスのイメージ図は以下のようになります。
リーフには、それぞれ主キーidの値と、それに対応した行データが入っています。

clustered_index

セカンダリインデックス

クラスター化インデックス以外のインデックスは、セカンダリインデックスと呼ばれます。つまり主キー以外のインデックスとなります。セカンダリインデックスのリーフには、セカンダリインデックスに指定されたカラムの値と、主キーが含まれています。

customersテーブルを例にすると、region_idのインデックスはセカンダリインデックスとなります。region_idが1~2000まで持っていたとき、このセカンダリインデックスを図として表すと、以下のようなイメージ図となります。

secondary_index

検索の仕組み

MySQLでの検索手順について、クックパッドのブログにありましたので引用します。
なお、この検索手順の説明はMySQL 5.6を前提としています。

MySQL がレコードを取得する際の主要な登場人物として、executor*3 と storage engine (e.g. InnoDB) がいます。

storage engine が InnoDB の場合は次のようにレコードを取得します。

executor が storage engine にレコードを要求する

storage engine (InnoDB) はセカンダリインデックスの木を辿ることで、取得すべきレコードのインデックスに含まれているカラム値と主キーの値を得る
・インデックスが使えない場合はクラスター化インデックスに含まれている全レコード情報を executor に返す

storage engine は 2 で得たデータのうち、インデックスに含まれているカラム値の情報を使って取得すべきレコードをフィルタリングする (Using index condition)
・インデックスに含まれている情報が使えない場合はスキップ

storage engine は 3 で得たデータの主キー情報を使ってクラスター化インデックスからレコードを取得する
・SELECT で指定されているカラムや WHERE で指定されているカラムの情報が全てインデックスに含まれている場合はスキップ (Using index)

storage engine は取得したレコード情報を executor に返す

executor は storage engine がフィルタリングできなかったレコードをフィルタリングする (Using where)
・storage engine 側で全てフィルタリングされている場合はスキップ

この検索の仕組みにおいて、主キーで検索した場合と、新規作成したインデックス（セカンダリインデックス）を使用した検索の場合を考えてみます。

主キーでの検索

さきほどの検索の仕組みを考慮すると、主キーでの検索はセカンダリインデックスを使用しないので、手順2において「インデックスが使えない場合はクラスター化インデックスに含まれている全レコード情報を executor に返す」となります。
その後の手順3ではフィルタリングする必要がないので、スキップとなります。手順4以降はそのまま実施されます。

そのため、主キーの検索の仕組みは「クラスター化インデックスから主キーを使用して検索する」となります。

サンプルクエリを基に説明します。

select * from customers where id = 20

このクエリを実行すると、クラスター化インデックスからid = 20となるデータを検索し、取り出します。
検索イメージ図は以下のとおりです。

search_by_pk_from_clustered_index

新規作成したインデックスを使用した検索

新規作成したインデックスの検索は、セカンダリクラスターとクラスター化インデックスを使用した検索となります。

サンプルクエリを基に説明します。

select * from customers where region_id = 1000

このクエリを実行すると、セカンダリインデックスから、region_id = 1000となるリーフを検索します。リーフには主キーが含まれているので、その主キーを使用し、クラスター化インデックスから該当のリーフを検索して取り出します。
検索イメージ図は以下のとおりです。

search_by_using_secondary_index

複合インデックスとは

複合インデックスは複数のカラムを組み合わせたインデックスのことです。
複合インデックスを使うことで得られるメリットについては、公式ドキュメントから引用します。

MySQL can use multiple-column indexes for queries that test all the columns in the index, or queries that test just the first column, the first two columns, the first three columns, and so on. If you specify the columns in the right order in the index definition, a single composite index can speed up several kinds of queries on the same table.

この説明では、複合インデックスで使用するカラムを正しい順番に指定し、使用することで、テーブルに対する複数のクエリを高速化できるとあります。

また、複合インデックスを使用するためには条件があります。こちらも公式ドキュメントから引用します。

If the table has a multiple-column index, any leftmost prefix of the index can be used by the optimizer to look up rows. For example, if you have a three-column index on (col1, col2, col3), you have indexed search capabilities on (col1), (col1, col2), and (col1, col2, col3).

MySQL cannot use the index to perform lookups if the columns do not form a leftmost prefix of the index. Suppose that you have the SELECT statements shown here:
SELECT * FROM tbl_name WHERE col1=val1;
SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2;

SELECT * FROM tbl_name WHERE col2=val2;
SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3;
If an index exists on (col1, col2, col3), only the first two queries use the index. The third and fourth queries do involve indexed columns, but do not use an index to perform lookups because (col2) and (col2, col3) are not leftmost prefixes of (col1, col2, col3).

公式ドキュメントにあるように、(col1, col2, col3)の複合インデックスを持っている場合、オプティマイザーは複合インデックスの一番左のカラムから順に使用します。
よって、(col1, col2, col3)の複合インデックスが使用されるのは、クエリの条件に以下3つのどれかがあるときです。

col1
col1, col2
col1, col2, col3

customersテーブルで考えると、以下2つのクエリは複合インデックスの(region_id, last_name)が使用されます。

SELECT * FROM customers WHERE region_id = 1000;
SELECT * FROM customers WHERE region_id = 1000 AND last_name = 'Cormier';

逆に以下のクエリのように、複合インデックスの順に沿わないカラムを使用したクエリでは、複合インデックスは使用されません。

SELECT * FROM customers WHERE last_name = 'Cormier';

また、複合インデックスのカラムすべてが入っている場合でも、以下クエリのOR検索のように、クエリ実行時に使用するカラムが複合インデックスの順番通りになっていない場合、複合インデックスは使用されません。このクエリでは、last_nameの検索だけを行うパターンがあるためです。

SELECT * FROM customers WHERE region_id = 1000 OR last_name = 'Cormier';

カーディナリティとは

公式ドキュメントから引用します。

cardinality
The number of different values in a table column. When queries refer to columns that have an associated index, the cardinality of each column influences which access method is most efficient.

この説明からわかる通り、カラム内に存在する異なる値の数のことをカーディナリティと呼びます。またカーディナリティはクエリ実行速度に影響を与えるものとなります。

カラム内に存在する異なる値の数について、例を使って説明します。
あるテーブルに都道府県を表すprefecturesカラムがあるとします。prefecturesカラムに東京、大阪のみ入っている状態ならば、その時点でのカーディナリティは2となります。またprefecturesカラムに、47個すべての都道府県が入っていれば、カーディナリティは47となります。

このカーディナリティが高いカラムをインデックスとすることで、クエリの実行速度を改善できる可能性があります。

ただし、カーディナリティが高いカラムのインデックスを持っていても、そのカラムの値の分布が極端に偏っている場合、オプティマイザーがそのインデックスを使用しないことがあります。

customersテーブルを例に考えてみます。インデックスに指定されているregion_idカラムにおいて、値の分布を極端にするために、customersテーブルを以下の状態にします。

100万件のレコードを持つ
このうち99万件のレコードは、region_idカラムの値がすべて10000
残り1万件のレコードは、region_idカラムの値が1 ~ 9999となる

ANALYZE TABLEをしたところ、このときのカーディナリティは9988となっていました。（ANALYZE TABLEは見積もりなので若干のズレは仕方ないです）カーディナリティは高いように思えます。
このcustomersテーブルに対し、region_id >= 9999の条件を使用したクエリを、EXPLAINで確認してみます。

mysql> EXPLAIN SELECT * FROM customers WHERE region_id >= 9999;
+----+-------------+-----------+------------+------+------------------------------+------+---------+------+--------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys                | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+-----------+------------+------+------------------------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | customers | NULL       | ALL  | index_customers_on_region_id | NULL | NULL    | NULL | 995242 |    50.00 | Using where |
+----+-------------+-----------+------------+------+------------------------------+------+---------+------+--------+----------+-------------+

typeがALLとなっているので、インデックスを使用した検索ではなく、テーブルスキャンが選択されています。この理由は、レコードの大部分を占めている値で絞り込む場合、広範囲の検索が必要となるので、オプティマイザーがテーブルスキャンの使用が良いと判断したためと思われます。

逆に、region_id <= 9999の条件を使用したクエリを確認してみます。

mysql> EXPLAIN SELECT * FROM customers WHERE region_id <= 9999;
+----+-------------+-----------+------------+-------+------------------------------+------------------------------+---------+------+-------+----------+-----------------------+
| id | select_type | table     | partitions | type  | possible_keys                | key                          | key_len | ref  | rows  | filtered | Extra                 |
+----+-------------+-----------+------------+-------+------------------------------+------------------------------+---------+------+-------+----------+-----------------------+
|  1 | SIMPLE      | customers | NULL       | range | index_customers_on_region_id | index_customers_on_region_id | 5       | NULL | 18242 |   100.00 | Using index condition |
+----+-------------+-----------+------------+-------+------------------------------+------------------------------+---------+------+-------+----------+-----------------------+

この場合、条件に合うレコードが少なく、オプティマイザーはインデックス使用が良いと考えたため、インデックスを使用されているようです。

そのため、インデックス対象のカラムを選ぶ際は、カーディナリティが高く、値が偏りなく分散しているカラムが良いと言えます。

参考記事

参考本

達人に学ぶDB設計徹底指南書

おわりに

この記事では、インデックスとカーディナリティについて説明しました。
B+treeの仕組み、インデックスの使い所を記事にまとめることで理解し直せました。個人的にインデックスに使うカーディナリティは高ければ高いほどいいとだけ単純に思っていましたが、レコードの分布次第によるということを学べて良かったと思います。
この記事が誰かのお役に立てれば幸いです。