Re: MySQL 5.1 does not seem to be using the index that I expect it to.

[Rick James]

> but it's key_len is just 8 (indicating that it is not using the trigger_time or id, right?
No. The 8 applies only to the WHERE. Even if it uses the index for the ORDER BY, there is no clue in the key_len; it will stay 8. (Alas.)
BIGINT takes 8 bytes. When it was NULLable, the key_len said 9 (an extra byte for the nullness flag).

> The explain plan for recipient_id 128 (3789 rows) uses the unexpected index, recipient_id__status__trigger_time__id, but it's key_len is also just 8
* In this case, `status` is in the way of using the index for the ORDER BY.
* Your theory about cardinality is interesting. But I'm not convinced. You might try some other recipient_ids.

Another theory is that it looks around at what index blocks happened to be cached at the moment, and (in some cases) picks the index based on not having to hit the disk. (I know of no way to prove or disprove this theory.)

> Why is the key_len equal to 8 in both cases (indicating that the optimizier is using only the recipient_id part (of the multi-part index)?
That's my conclusion.

> Why wouldn't the optimizier use the trigger_time and the id (in addition to the recipient_id)?
That's the mystery we have been chasing!

> Why does the second query depend upon a filesort?
Aha! That says that the first query _did_ use the index for the ORDER BY. But the second one did not.

Hmmm... that brings up another thought. "Filesort" is not the extreme evil that it is made out to be. It could be that the optimizer downplayed the cost of "filesort" by thinking "it's only 3789 rows".

(You are managing to talk me into your theory.)

> examine 5160 rows when there are in fact only 3789 rows
5160 is just a crude estimate based on some statistics about distribution key values, or whatever. That number is not very far off. I've seen a lot worse.

Bottom line. When you had 64552 rows, it did the 'right' thing. When you had 3789 rows, it did a "good enough" thing.

BTW, I have seen as many as 6 different EXPLAIN plans for the 'same' query. (The queries varied only in constants.) The scary case is when the same query (including constants) gets a different EXPLAIN plan without much changing. Or when the performance changes by orders of magnitude.