MySQL запрос иногда выполняется медленно, иногда быстро

У меня проблема с этим простым запросом MySQL:

select sender as id from message where status=1 and recipient=1

где таблица отправителей имеет несколько миллионов строк.

Когда я запускаю это в SequelPro, в первый раз он работает очень медленно, ~ 4 секунды или более, а при следующем запуске он работает очень быстро, ~ 0,018 секунды. Однако, если я запустлю снова через пару минут, он снова сделает то же самое.

Я пытался использовать SQL_NO_CACHE, и он все еще дает мне тот же результат.

Механизм БД — это innoDB, а БД — это кластер MySQL Percona XtraDB.
Вот объяснение результатов:

|id|select_type|table  |type|possible_keys         |key |key_len|ref            |row   |Extra
| 1|SIMPLE     |message|ref |recipient,status, sent|sent|12     |const,const    |2989   |NULL

«отправлено» является индексом из нескольких столбцов (получатель, статус).
У кого-нибудь есть идеи, чтобы решить эту проблему?

Спасибо.

добавленной (из комментария)

CREATE TABLE 'message' (
'id' int(20) NOT NULL AUTO_INCREMENT,
'sender' bigint(20) NOT NULL,
'recipient' bigint(20) NOT NULL,
'status' int(5) NOT NULL,
'date' timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
PRIMARY KEY ('id'),
KEY 'id' ('id'),
KEY 'recipient' ('recipient'),
KEY 'sender' ('sender'),
KEY 'date' ('date'),
KEY 'status' ('status'),
KEY 'sent' ('status','recipient')
) ENGINE=InnoDB AUTO_INCREMENT=90224500 DEFAULT CHARSET=latin1;