LoginSignup
17
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

DeNA 20 新卒Advent Calendar 2020

Day 2
@K-junin株式会社ディー・エヌ・エー

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

Last updated at Posted at 2020-12-01

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が使えないか見ていきます。

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

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

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を使ってのデータ増幅オシャレだと思ってるんですがどうでしょうか。え? そんなことない...?

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としています。

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ですね。

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)

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句において、検索範囲を範囲指定した場合です。

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%';

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

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';

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

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は以下のものになります。

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回程度実行すれば今回は十分でしょう。

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

平均値を出す。

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

結果。

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 では、 Blog記事だけでなく色々な勉強会での登壇資料も発信してます。こちらもぜひフォローして頂けると...!
Follow @DeNAxTech

17
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
17
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?