hash-indexを試して遊んでみた。

# hash-index

MySQLのIndexには`B-Tree Index`が用いられていることは有名ですが、先日社内の輪読会にて`Hash Index`という`Index`も存在していることを知りました。
`<=`,`>=`などの範囲検索には使えませんが、`=`, `<=>`といった単純な値の比較であればかなり早いとのことなので、これら2つを比べてみることにしました。

ref: https://dev.mysql.com/doc/refman/5.7/en/index-btree-hash.html

## tl;dr

MySQLのデフォルトストレージエンジンであるInnoDBでは`Hash Index`をサポートしていないので、本当に試してみたに過ぎませんが 笑。

## 準備

### Environment
mysql v5.7.31
Docker v19.03.12

### Storage Engine

以下を参考にすると、InnoDBは`Hash Index`をインデックスとしてサポートしていない様子。
https://dev.mysql.com/doc/refman/5.7/en/create-index.html

| ストレージエンジン | 許可されるインデックスタイプ |
| --- | --- |
| `InnoDB` | `BTREE` |
| `MyISAM` | `BTREE` |
| `MEMORY`/`HEAP` | `HASH`、`BTREE` |
| `NDB` | `HASH`、`BTREE` |

ということで`Hash Index`が利用可能なストレージエンジンである`MEMORY`と`NDB`が使えないか見ていきます。

```sql
mysql> show engines;
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| Engine             | Support | Comment                                                        | Transactions | XA   | Savepoints |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| InnoDB             | DEFAULT | Supports transactions, row-level locking, and foreign keys     | YES          | YES  | YES        |
| MRG_MYISAM         | YES     | Collection of identical MyISAM tables                          | NO           | NO   | NO         |
| MEMORY             | YES     | Hash based, stored in memory, useful for temporary tables      | NO           | NO   | NO         |
| BLACKHOLE          | YES     | /dev/null storage engine (anything you write to it disappears) | NO           | NO   | NO         |
| MyISAM             | YES     | MyISAM storage engine                                          | NO           | NO   | NO         |
| CSV                | YES     | CSV storage engine                                             | NO           | NO   | NO         |
| ARCHIVE            | YES     | Archive storage engine                                         | NO           | NO   | NO         |
| PERFORMANCE_SCHEMA | YES     | Performance Schema                                             | NO           | NO   | NO         |
| FEDERATED          | NO      | Federated MySQL storage engine                                 | NULL         | NULL | NULL       |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
9 rows in set (0.00 sec)
```

`show engines`にて`MEMORY`の存在を確認できたので、こちらを用いて検証していきます。

### Create Table

実際に検証用のテーブルを作っていきます。

```sql
drop table if exists todo;
create table todo(
	id int not null auto_increment,
	num_column int not null,
	str_column char(10) not null,
	primary key (id) 
) engine memory;

# Hash Index
create index num_h_index using hash on todo (num_column);
create index str_h_index using hash on todo (str_column);
# B-Tree Index
create index num_b_index using btree on todo (num_column);
create index str_b_index using btree on todo (str_column);
```

今回は、整数値と文字列に関する検証が出来れば十分と考えたので`num_column`と`str_column`を作成しています。
`Index`もそれぞれのcolumnに対して`B-Tree Index`と`Hash Index`のものを作成しています。

### Dummy Data

検索にある程度の負荷を掛けるためにダミーのデータを作成していきます。ちなみに個人的には`CROSS JOIN`を使ってのデータ増幅オシャレだと思ってるんですがどうでしょうか。え? そんなことない...?

```sql
INSERT INTO todo (num_column, str_column) VALUES 
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10))),
	(CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10)));

INSERT INTO todo (num_column, str_column) SELECT CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10)) from todo cross join todo as todo2 where todo2.id between 1 and 9;
INSERT INTO todo (num_column, str_column) SELECT CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10)) from todo cross join todo as todo2 where todo2.id between 1 and 9;
INSERT INTO todo (num_column, str_column) SELECT CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10)) from todo cross join todo as todo2 where todo2.id between 1 and 9;
INSERT INTO todo (num_column, str_column) SELECT CEIL(RAND() * 10), CONCAT(SUBSTRING(MD5(RAND()), 1, 10)) from todo cross join todo as todo2 where todo2.id between 1 and 9;
```

`INSERT ... CROSS JOIN ...`を実行するたびにデータが10倍になるので結構気持ちよかったりします。`MEMORY`ですと34万件ほどでテーブルがいっぱいになるので、今回は10万件ほどのダミーレコードを生成しています。`num_column`には1~10のランダムな数字、`str_column`にはランダムな10文字の文字文を入れています。(データを見る限り、完全にランダムな文字列では無いみたいですが)


## 計測

### SQL

基本的なものが検証できれば良いので、以下の4つを今回の検証SQLとしています。

```sql
SELECT * FROM todo WHERE num_column = 1;
SELECT * FROM todo WHERE num_column BETWEEN 1 and 5;
SELECT * FROM todo WHERE str_column like 'a%';
SELECT * FROM todo WHERE str_column like '%a';
```

### Explain

#### `SELECT * FROM todo WHERE num_column = 1;`

まずは`Hash Index`のほうが早いと予想される単一の値のSQLですね。

```sql
mysql> explain SELECT * FROM todo use index(num_h_index) WHERE num_column = 1;
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+-------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key         | key_len | ref   | rows  | filtered | Extra |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+-------+----------+-------+
|  1 | SIMPLE      | todo  | NULL       | ref  | num_h_index   | num_h_index | 4       | const | 10000 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+-------+----------+-------+
1 row in set, 1 warning (0.00 sec)
```

```sql
mysql> explain SELECT * FROM todo use index(num_b_index) WHERE num_column = 1;
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+-------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key         | key_len | ref   | rows  | filtered | Extra |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+-------+----------+-------+
|  1 | SIMPLE      | todo  | NULL       | ref  | num_b_index   | num_b_index | 4       | const | 10722 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+-------------+---------+-------+-------+----------+-------+
1 row in set, 1 warning (0.00 sec)
```

実行計画を見てみると検索範囲を示すrowsの値が`10722`と`10000`なのでほぼほぼ同程度の量のデータを検索すると考え、検索量の差はないと判断。後は実行速度ですね。

#### `SELECT * FROM todo WHERE num_column BETWEEN 1 and 5;`

次に`WHERE`句において、検索範囲を範囲指定した場合です。

```sql
mysql> explain SELECT * FROM todo WHERE num_column BETWEEN 1 and 5;
+----+-------------+-------+------------+-------+-------------------------+-------------+---------+------+-------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys           | key         | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-------+------------+-------+-------------------------+-------------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | todo  | NULL       | range | num_h_index,num_b_index | num_b_index | 4       | NULL | 50288 |   100.00 | Using where |
+----+-------------+-------+------------+-------+-------------------------+-------------+---------+------+-------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
```

やはり範囲検索であると`B-Tree Index`が使用されるようですね。`use index`句にて`Hash Index`を指定も試してみましたが、そもそも使用されずフルテーブルスキャンとなってしまいました。

#### `SELECT * FROM todo WHERE str_column like 'a%';`

数字の次は文字列の部分一致ですね。最初に前方一致から見ていきます。

```sql
mysql> explain SELECT * FROM todo WHERE str_column like 'a%';
+----+-------------+-------+------------+-------+-------------------------+-------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys           | key         | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+-------------------------+-------------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | todo  | NULL       | range | str_h_index,str_b_index | str_b_index | 10      | NULL | 5900 |   100.00 | Using where |
+----+-------------+-------+------------+-------+-------------------------+-------------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
```

`B-Tree Index`が使用され、rowsの数が5900と良い感じに検索範囲が絞れています。`B-Tree`は`trie`と似たデータ構造を持つはずなのでPrefixでの前方一致には効果があるのだと思われます。

そういえばそもそも`B-Tree`って具体的にはどんなデータ構造だっけと調べてみると以下(↓)のようなサイトも発見しました。
https://www.cs.usfca.edu/~galles/visualization/BTree.html

ヌルヌル動くの面白いです。

#### `SELECT * FROM todo WHERE str_column like '%a';`

最後に文字列の後方一致も見ていきます。

```sql
mysql> explain SELECT * FROM todo WHERE str_column like '%a';
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | todo  | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 100000 |    11.11 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+--------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
```

おっと、いきなり`B-Tree Index`が効かなくなりましたね。`B-Tree`が`trie`と似たデータ構造を持つとするとSuffixでの検索には全く用いることが出来ないということでしょうか。

となると文字列に`Index`を貼った際には前方一致の検索のほうが早いということになります。本題とは逸れますが、前方一致と比べてどれぐらいの速度の違いが出るのかに期待ですね。

### Profiler

最後にそれぞれのSQLの実行時間を見ていきます。計測には`profiling`用いて行います。具体的なSQLは以下のものになります。

```sql
SET profiling = 1;
SELECT * FROM todo use index(num_h_index) WHERE num_column = 1;
SELECT * FROM todo use index(num_b_index) WHERE num_column = 1;
SELECT * FROM todo WHERE num_column BETWEEN 1 and 5;
SELECT * FROM todo WHERE str_column like 'a%';
SELECT * FROM todo WHERE str_column like '%a';
SHOW PROFILES;
```

計測は平均値が大事なので、上記のSQLを複数回実行して結果を平均化します。適当に10回程度実行すれば今回は十分でしょう。

```bash
for _ in `seq 1 10`; do
mysql -uroot -proot -D mysqldb -e "\
SET profiling = 1; \
SELECT * FROM todo use index(num_h_index) WHERE num_column = 1; \
SELECT * FROM todo use index(num_b_index) WHERE num_column = 1; \
SELECT * FROM todo WHERE num_column BETWEEN 1 and 5; \
SELECT * FROM todo WHERE str_column like 'a%'; \
SELECT * FROM todo WHERE str_column like '%a';SHOW PROFILES; \
" | tail -n 5 >> result
done 
```

平均値を出す。

```bash
for i in `seq 1 5`; do
cat result | grep ^$i | awk '{ sum+=$2; cnt++ } END { print sum / cnt }'
done
```
結果。

```bash
0.0036558   # SELECT * FROM todo use index(num_h_index) WHERE num_column = 1;
0.00511643  # SELECT * FROM todo use index(num_b_index) WHERE num_column = 1;
0.021532    # SELECT * FROM todo WHERE num_column BETWEEN 1 and 5;
0.00296707  # SELECT * FROM todo WHERE str_column like 'a%';
0.00719143  # SELECT * FROM todo WHERE str_column like '%a';SHOW PROFILES;
```

`=`の検索条件による`Hash Index`と`B-Tree Index`の速度差ですが、やはりというべきか`Hash Index`のほうが多少優れています。

`B-Tree Index`を使用した前方一致検索と、そうでない後方一致検索には速度に明確な違いが見て取れます。2.3倍ほどでしょうか。しかし検索量に20倍程度の違いがあることを考えると、差分が少ない気もしますね。まぁ、他にオーバーヘッドが存在しているものと思われます。

## まとめ
`=`や`<=>`といった単純な比較を行うSQLにおいては`Hash Index`のほうが多少早い。また文字列検索は、`B-Tree Index`の構造上前方一致のほうが速度が出やすい。
繰り返しになりますが、InnoDBでは`Hash Index`をサポートしていないので蛇足です 笑。

この記事を読んで「面白かった」「学びがあった」と思っていただけた方、よろしければ Twitter や facebook、はてなブックマークにてコメントをして頂けると嬉しいです。
また [DeNA 公式 Twitter アカウント @DeNAxTech](https://twitter.com/DeNAxTech) では、 Blog記事だけでなく色々な勉強会での登壇資料も発信してます。こちらもぜひフォローして頂けると...!
<a href="https://twitter.com/DeNAxTech?ref_src=twsrc%5Etfw" class="twitter-follow-button" data-size="large" data-lang="ja" data-show-count="false">Follow @DeNAxTech</a><script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>