> explain select * from msg where to_id = USER_ID and status='new';
select_type | table | type | possible_keys | key | key_len | ref | rows | Extra
------------+----------+------+-----------------+-----------------+---------+-------+------+------------
SIMPLE | msg | ref | idx_toid_status | idx_toid_status | 3 | const | 893 | Using where
> explain select count(*) from msg where to_id = USER_ID and status='new';
select_type | table | type | possible_keys | key | key_len | ref | rows | Extra
------------+----------+------+-----------------+-----------------+---------+-------+------+-------------------------
SIMPLE | msg | ref | idx_toid_status | idx_toid_status | 3 | const | 893 | Using where; Using index
> select count(*) from msg where to_id = USER_ID and status='new';
count(*)
---------
1133
В том то и дело, чтобы применить способ которые подходит, необходимо представлять какие способы есть :)