MySQL: медленный путь индекса BTREE (размер таблицы: 723704015 строк)

У меня большая база данных, и одна таблица, в частности, постоянно работает медленно, несмотря на наличие соответствующего индекса (фактически, fk) в столбце. Честно говоря, столбец имеет низкую мощность (всего 5 возможных значений и не распределяются равномерно), но выполнение LIMIT 1 все еще составляет 9+ секунд, но Только при выборе на конкретном пути btree.

Вот таблица:

CREATE TABLE `locking_scripts` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `script_type_id` int(10) unsigned NOT NULL DEFAULT 1,
  `transaction_output_id` int(10) unsigned NOT NULL,
  `script` blob NOT NULL,
  `address_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `locking_scripts_uq` (`transaction_output_id`),
  KEY `locking_scripts_address_id_fk` (`address_id`),
  KEY `locking_scripts_type_id_fk` (`script_type_id`),
  CONSTRAINT `locking_scripts_address_id_fk` FOREIGN KEY (`address_id`) REFERENCES `addresses` (`id`),
  CONSTRAINT `locking_scripts_output_id_fk` FOREIGN KEY (`transaction_output_id`) REFERENCES `transaction_outputs` (`id`),
  CONSTRAINT `locking_scripts_type_id_fk` FOREIGN KEY (`script_type_id`) REFERENCES `script_types` (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=748705501 DEFAULT CHARSET=utf8mb4;

Рассматриваемый столбец - script_type_id. Содержимое этой соответствующей таблицы:

+----+------------------------+
| id | type                   |
+----+------------------------+
|  2 | CUSTOM_SCRIPT          |
|  3 | PAY_TO_PUBLIC_KEY      |
|  4 | PAY_TO_PUBLIC_KEY_HASH |
|  5 | PAY_TO_SCRIPT_HASH     |
|  1 | UNKNOWN                |
+----+------------------------+

table status для двух таблиц:

+-------------------+--------+---------+------------+-----------+----------------+--------------+-----------------+--------------+-----------+----------------+---------------------+---------------------+------------+--------------------+----------+----------------+---------+
| Name              | Engine | Version | Row_format | Rows      | Avg_row_length | Data_length  | Max_data_length | Index_length | Data_free | Auto_increment | Create_time         | Update_time         | Check_time | Collation          | Checksum | Create_options | Comment |
+-------------------+--------+---------+------------+-----------+----------------+--------------+-----------------+--------------+-----------+----------------+---------------------+---------------------+------------+--------------------+----------+----------------+---------+
| locking_scripts   | InnoDB |      10 | Dynamic    | 726718877 |             70 |  51335135232 |               0 |  34351300608 |   7340032 |      748705501 | 2018-10-25 01:31:20 | 2018-11-18 15:30:40 | NULL       | utf8mb4_general_ci |     NULL |                |         |
| script_types      | InnoDB |      10 | Dynamic    |         5 |           3276 |        16384 |               0 |        16384 |         0 |              6 | 2018-10-24 22:22:43 | NULL                | NULL       | utf8mb4_general_ci |     NULL |                |         |
+-------------------+--------+---------+------------+-----------+----------------+--------------+-----------------+--------------+-----------+----------------+---------------------+---------------------+------------+--------------------+----------+----------------+---------+

Я выполняю следующий запрос:

SELECT id FROM locking_scripts WHERE script_type_id = 1 LIMIT 1;

... для выполнения которого требуется около 9.5s. Профиль этого запроса:

+------+-------------+-----------------+------+----------------------------+----------------------------+---------+-------+-----------+----------+-------------+
| id   | select_type | table           | type | possible_keys              | key                        | key_len | ref   | rows      | filtered | Extra       |
+------+-------------+-----------------+------+----------------------------+----------------------------+---------+-------+-----------+----------+-------------+
|    1 | SIMPLE      | locking_scripts | ref  | locking_scripts_type_id_fk | locking_scripts_type_id_fk | 4       | const | 363359438 |   100.00 | Using index |
+------+-------------+-----------------+------+----------------------------+----------------------------+---------+-------+-----------+----------+-------------+

Профилировщик говорит, что использует индекс (честно говоря, он должен отфильтровать 363 359 438 строк, но с LIMIT 1 он должен работать довольно быстро, поскольку он отказывает при первом совпадении). Однако интересно то, что этот запрос выполняется вдвое быстрее:

SELECT id FROM locking_scripts WHERE script_type_id NOT IN (2, 3, 4, 5) LIMIT 1

... Что требует для выполнения 4.5s. (Хотя это все еще ужасно долгое время.) У меня есть другие таблицы аналогичного размера, и выбор LIMIT 1 из набора с аналогичным индексом происходит практически мгновенно.

Для полноты объяснение «более быстрой» версии выглядит следующим образом:

+------+-------------+-----------------+-------+----------------------------+----------------------------+---------+------+-----------+----------+--------------------------+
| id   | select_type | table           | type  | possible_keys              | key                        | key_len | ref  | rows      | filtered | Extra                    |
+------+-------------+-----------------+-------+----------------------------+----------------------------+---------+------+-----------+----------+--------------------------+
|    1 | SIMPLE      | locking_scripts | range | locking_scripts_type_id_fk | locking_scripts_type_id_fk | 4       | NULL | 363359442 |   100.00 | Using where; Using index |
+------+-------------+-----------------+-------+----------------------------+----------------------------+---------+------+-----------+----------+--------------------------+

У меня заканчиваются идеи, чтобы объяснить, почему я вижу такой результат. Если у кого-то есть понимание, я был бы признателен. Спасибо.

Дополнительная информация, по комментариям:

План выполнения для SELECT *:

EXPLAIN FORMAT=JSON SELECT * FROM locking_scripts WHERE script_type_id = 1 LIMIT 1;

{
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "locking_scripts",
      "access_type": "ref",
      "possible_keys": ["locking_scripts_type_id_fk"],
      "key": "locking_scripts_type_id_fk",
      "key_length": "4",
      "used_key_parts": ["script_type_id"],
      "ref": ["const"],
      "rows": 363359438,
      "filtered": 100
    }
  }
}

План выполнения для SELECT * ... NOT IN ():

EXPLAIN FORMAT=JSON SELECT * FROM locking_scripts WHERE script_type_id NOT IN (2, 3, 4, 5) LIMIT 1;

{
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "locking_scripts",
      "access_type": "range",
      "possible_keys": ["locking_scripts_type_id_fk"],
      "key": "locking_scripts_type_id_fk",
      "key_length": "4",
      "used_key_parts": ["script_type_id"],
      "rows": 363359442,
      "filtered": 100,
      "index_condition": "locking_scripts.script_type_id not in (2,3,4,5)"
    }
  }
}