I noticed a slow query coming from the afe frontend:

mysql> SELECT DISTINCT count(`afe_host_queue_entries`.`id`) from `afe_host_queue_entries` INNER JOIN `afe_jobs` ON (`afe_host_queue_entries`.`job_id` = `afe_jobs`.`id`) WHERE (`afe_host_queue_entries`.`host_id` = 3919  AND `afe_host_queue
_entries`.`id` >= 140777458  AND `afe_host_queue_entries`.`started_on` >= '2017-09-07 15:46:25'  AND `afe_host_queue_entries`.`complete` = 1  AND `afe_host_queue_entries`.`started_on` <= '2017-09-08 02:04:25' );
+--------------------------------------+
| count(`afe_host_queue_entries`.`id`) |
+--------------------------------------+
|                                   61 |
+--------------------------------------+
1 row in set (28.53 sec)

Wow! Considering there are started_on, complete, and host_id indices on the HQE table, why is this so slow? Well, it turns out MySQL is trying to use two of them at once:

mysql> explain SELECT DISTINCT count(`afe_host_queue_entries`.`id`) from `afe_host_queue_entries` INNER JOIN `afe_jobs` ON (`afe_host_queue_entries`.`job_id` = `afe_jobs`.`id`) WHERE (`afe_host_queue_entries`.`host_id` = 3919  AND `afe_ho
st_queue_entries`.`id` >= 140777458  AND `afe_host_queue_entries`.`started_on` >= '2017-09-07 15:46:25'  AND `afe_host_queue_entries`.`complete` = 1  AND `afe_host_queue_entries`.`started_on` <= '2017-09-08 02:04:25' );
+------------------------+-------------+-------------------------------------------------------------------------------------+
| table                  | type        | Extra                                                                               |
+------------------------+-------------+-------------------------------------------------------------------------------------+
| afe_host_queue_entries | index_merge | Using intersect(host_queue_entries_host_id,host_queue_enties_complete); Using where |
| afe_jobs               | eq_ref      | Using index                                                                         |
+------------------------+-------------+-------------------------------------------------------------------------------------+


After disabling index intersection temporarily:

mysql> SELECT DISTINCT count(`afe_host_queue_entries`.`id`) from `afe_host_queue_entries` INNER JOIN `afe_jobs` ON (`afe_host_queue_entries`.`job_id` = `afe_jobs`.`id`) WHERE (`afe_host_queue_entries`.`host_id` = 3919  AND `afe_host_queue
_entries`.`id` >= 140777458  AND `afe_host_queue_entries`.`started_on` >= '2017-09-07 15:46:25'  AND `afe_host_queue_entries`.`complete` = 1  AND `afe_host_queue_entries`.`started_on` <= '2017-09-08 02:04:25' );
+--------------------------------------+
| count(`afe_host_queue_entries`.`id`) |
+--------------------------------------+
|                                   61 |
+--------------------------------------+
1 row in set (0.07 sec)


I found a nice blog post explaining what index merging is here: https://www.percona.com/blog/2012/12/14/the-optimization-that-often-isnt-index-merge-intersection/