Percona 5.5 "forget" index

Hi,
could somebody explain why the following happens?

EXPLAIN
SELECT m.*, md.toUserID, md.toStatus, md.toLogin, md.createdBy , IF(m.type = 4 OR m.type = 3, count(md.toUserID), 1) as numRecipients , u.createdBy, u.lastLogin, u.gender, u.lastPaymentDate, u.lastCustomMessageDate, u.birthDate, u.city, u.profileImg
FROM users_messages m
JOIN users_messages_dest md USING (messageID)
LEFT JOIN users u ON toUserID = userID
WHERE m.fromUserID = 11111 AND m.fromStatus = 10
GROUP BY m.messageID
ORDER BY m.messageID DESC
LIMIT 0, 36;

±—±------------±------±-------±----------------------±--------------±--------±-------------------±-----±------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
±—±------------±------±-------±----------------------±--------------±--------±-------------------±-----±------------+
| 1 | SIMPLE | m | ref | PRIMARY,fk_fromUserID | fk_fromUserID | 3 | const | 128 | Using where |
| 1 | SIMPLE | md | ref | PRIMARY | PRIMARY | 4 | dating.m.messageID | 3 | |
| 1 | SIMPLE | u | eq_ref | PRIMARY | PRIMARY | 3 | dating.md.toUserID | 1 | |
±—±------------±------±-------±----------------------±--------------±--------±-------------------±-----±------------+

After a few hours it changes to this:
[COLOR=#32353A]EXPLAIN
SELECT m.*, md.toUserID, md.toStatus, md.toLogin, md.createdBy , IF(m.type = 4 OR m.type = 3, count(md.toUserID), 1) as numRecipients , u.createdBy, u.lastLogin, u.gender, u.lastPaymentDate, u.lastCustomMessageDate, u.birthDate, u.city, u.profileImg
FROM users_messages m
JOIN users_messages_dest md USING (messageID)
LEFT JOIN users u ON toUserID = userID
WHERE m.fromUserID = 111111 AND m.fromStatus = 10
GROUP BY m.messageID
ORDER BY m.messageID
DESC LIMIT 0, 36 ;
[COLOR=#32353A]
[COLOR=#32353A]
[COLOR=#32353A]
[COLOR=#32353A]
[COLOR=#32353A]
[COLOR=#32353A]
[COLOR=#32353A]

After a server restart. The problem is gone for the next few hours. Then it happens again.

Regards,
Thomas

Did you tried with INDEX HINT ? as per http://dev.mysql.com/doc/refman/5.5/en/index-hints.html

Yes I tried with USE and FORCE INDEX but it doesn’t change anything…

It seems that table join order has changed. Did you tried with STRAIGHT_JOIN ? where left table is read before the right table. You can check for details in manual http://dev.mysql.com/doc/refman/5.5/en/join.html