gistfile1.txt

mysql> desc covers;
+----------------------+--------------+------+-----+---------+----------------+
| Field                | Type         | Null | Key | Default | Extra          |
+----------------------+--------------+------+-----+---------+----------------+
| id                   | int(11)      | NO   | PRI | NULL    | auto_increment | 
| page_id              | int(11)      | YES  | MUL | NULL    |                | 
| item_id              | int(11)      | YES  | MUL | NULL    |                | 
| performed            | tinyint(1)   | YES  |     | 0       |                | 
| cover_file_name      | varchar(255) | YES  |     | NULL    |                | 
| cover_content_type   | varchar(255) | YES  |     | NULL    |                | 
| cover_file_size      | int(11)      | YES  |     | NULL    |                | 
| cover_updated_at     | datetime     | YES  |     | NULL    |                | 
| cover_url            | varchar(255) | YES  | MUL | NULL    |                | 
| created_at           | datetime     | YES  |     | NULL    |                | 
| updated_at           | datetime     | YES  |     | NULL    |                | 
| temp_cover_file_name | varchar(255) | YES  |     | NULL    |                | 
| cover_uploaded       | tinyint(1)   | YES  |     | 0       |                | 
+----------------------+--------------+------+-----+---------+----------------+

точно здесь требуются 3 индекса?
попробуй сделать explain при отсутствии индексов

те же Percona говорят, что поиск по полю, котором может быть null - может занимать больше времени

т.е. пустая строка предпочтительнее нежели NULL