This is based on a customer testcase.

I wasn't able to construct an actual testcase so far, but I was able to get the invalid query plan by tampering with rows/cost estimates in the debugger.

The problem looks like this:

EXPLAIN 

SELECT 

  non_idex_col 

FROM 

  t2

WHERE 

  key1part1 = 1500 and key1part2 IN (5, 60, 133, 387) AND 

  pk1 = 700000

ORDER BY

  pk2 DESC LIMIT 1;

+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+

| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |

+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+

|    1 | SIMPLE      | t2    | index | PRIMARY,key1  | PRIMARY | 6       | NULL |   26 | Using where |

+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------+

The plan uses a full index scan, even if there is a potential ref (or range) access over the PRIMARY key: pk1 = 700000. Costs and selectivity numbers are irrelevant - if we pick to do a full index scan, then range on that index will not be slower.

The optimizer actually has this logic and was expected to use range access. It even typically does. Getting the above query plan requires some peculiar relationship between costs of range/ref accesses through key1 and primary key.