MySQL query sometimes runs slow, sometimes fast

I am having problem with this simple MySQL query:

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

where sender table has multi millions of rows.

When I run this on SequelPro, it runs really slow for the first time, ~4 seconds or more, and the next execution it run really fast, ~0.018 seconds. However, if I run again after couple of minutes, it will do the same thing again.
I tried to use SQL_NO_CACHE, and it still gives me the same result.
The DB engine is innoDB, and the DB is MySQL Percona XtraDB cluster. Here is the explain results:

			|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 |

“sent” is an index of multi-column of (recipient, status). Does anyone has any idea to fix this problem?

Thank you.

Can you post “SHOW CREATE TABLE message” ?

Here is the “SHOW CREATE TABLE message”

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; 

Any idea what’s wrong?

Try using MySql Table Partitioning features.