Index

現在のMySQLはB+tree構造でデータを保存しています。
B+treeのイメージはこんな感じです。

Indexを使えば、検索するデータに辿り着くまでO(log(n))がかかることが分かります。
逆に、queryによってこのindexを使わなくなると、検索量がO(n)になって、
データが大きくなるにづれ、検索に非常に時間がかかることがあります。

実験

例えばこういうテーブルがあります

CREATE TABLE table (
    a varchar(255),
    b varchar(255),
    KEY 'a' ('a'),
    KEY 'b' ('b'),
);

mysql> explain select * from table where a LIKE "abc%";
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------+
| id | select_type | table     | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | table     | NULL       | range | a             | a    | 1022    | NULL |    1 |   100.00 | Using index condition |
+----+-------------+-----------+------------+-------+---------------+------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.03 sec)

mysql> explain select * from table where a LIKE "%abc";
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | table     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 49175 |    11.11 | Using where |
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
1 row in set, 1 warning (0.03 sec)

mysql> explain select * from table where a LIKE "%abc%";
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table     | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | table     | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 49175 |    11.11 | Using where |
+----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+
1 row in set, 1 warning (0.03 sec)

暗号化されたデータで検索する場合

Create Table: CREATE TABLE `dummy_table` (
  `dummy_key` varchar(10) DEFAULT NULL,
  KEY `dummy_key` (`dummy_key`)
)

mysql> explain select uuid from dummy_table where AES_DECRYPT(UNHEX(dummy_key), UNHEX('hash_key')) = 'dummy_value';
+----+-------------+-------------+------------+-------+---------------+-----------+---------+------+--------+----------+--------------------------+
| id | select_type | table       | partitions | type  | possible_keys | key       | key_len | ref  | rows   | filtered | Extra                    |
+----+-------------+-------------+------------+-------+---------------+-----------+---------+------+--------+----------+--------------------------+
|  1 | SIMPLE      | dummy_table | NULL       | index | NULL          | dummy_key | 163     | NULL | xxxxxx |   100.00 | Using where; Using index |
+----+-------------+-------------+------------+-------+---------------+-----------+---------+------+--------+----------+--------------------------+

dummy_keyを使って検索する場合、関数をかけてもindexが使われました。

結論を言うと

indexを使う検索
前方一致

indexを使わない検索
後方一致部分一致

LIKEを使う場合、前方一致を活用できるかどうかは検索時間の最適化に関わっています。