I have a very simple query that is running extremely slowly despite being indexed.

My table is as follows:

mysql> show create table mytable
CREATE TABLE `mytable` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `start_time` datetime DEFAULT NULL,
  `status` varchar(64) DEFAULT NULL,
  `user_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `ix_status_user_id_start_time` (`status`,`user_id`,`start_time`),
  ### other columns and indices, not relevant
) ENGINE=InnoDB AUTO_INCREMENT=115884841 DEFAULT CHARSET=utf8

Then the following query takes more than 10 seconds to run:

select id from mytable USE INDEX (ix_status_user_id_start_time) where status = 'running';

There are about 7 million rows in the table, and approximately 200 of rows have status running.

I would expect this query to take less than a tenth of a second. It should find the first row in the index with status running. And then scan the next 200 rows until it finds the first non-running row. It should not need to look outside the index.

When I explain the query I get a very strange result:

mysql> explain select id from mytable USE INDEX (ix_status_user_id_start_time) where status = 
'running';
+----+-------------+---------+------------+------+------------------------------+------------------------------+---------+-------+---------+----------+-------------+
| id | select_type | table   | partitions | type | possible_keys                | key                          | key_len | ref   | rows    | filtered | Extra       |
+----+-------------+---------+------------+------+------------------------------+------------------------------+---------+-------+---------+----------+-------------+
|  1 | SIMPLE      | mytable | NULL       | ref  | ix_status_user_id_start_time | ix_status_user_id_start_time | 195     | const | 2118793 |   100.00 | Using index |
+----+-------------+---------+------------+------+------------------------------+------------------------------+---------+-------+---------+----------+-------------+

It is estimating a scan of more than 2 million rows! Also, the cardinality of the status index does not seem correct. There are only about 5 or 6 different statuses, not 344.

Other info

1. There are somewhat frequent insertions and updates to this table. About 2 rows inserted per second, and 10 statuses updated per second. I don't know how much impact this has, but I would not expect it to be 30 seconds worth.

2. If I query by both status and user_id, sometimes it is fast (sub 0.1s) and sometimes it is slow (> 1s), depending on the user_id. This does not seem to depend on the size of the result set (some users with 20 rows are quick, others with 4 are slow)

Can anybody explain what is going on here and how it can be fixed?

I am using mysql version 5.7.33