We tried ANALYZE TABLE first, before even submitting the bug report, did not help. Here's more information about the table structure: mysql> SELECT type, COUNT(type) FROM suggestion GROUP BY type; +--------+-------------+ | type | COUNT(type) | +--------+-------------+ | user | 12954761 | | group | 12431541 | | board | 1395314 | | newbie | 11091696 | | dating | 4094086 | +--------+-------------+ 5 rows in set (4 min 52.40 sec) mysql> SELECT rejected, COUNT(rejected) FROM suggestion GROUP BY rejected; +----------+-----------------+ | rejected | COUNT(rejected) | +----------+-----------------+ | y | 1725700 | | n | 40241894 | +----------+-----------------+ 2 rows in set (4 min 38.46 sec) mysql> SELECT flags, COUNT(flags) FROM suggestion GROUP BY flags; +-------+--------------+ | flags | COUNT(flags) | +-------+--------------+ | 0 | 41959046 | | 1 | 8152 | | 2 | 567 | | 3 | 99 | +-------+--------------+ 4 rows in set (9 min 39.81 sec) mysql> select count(*) from suggestion where user_id=7723036; +----------+ | count(*) | +----------+ | 143 | +----------+ 1 row in set (0.01 sec) mysql> show keys from suggestion; +------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | +------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ | suggestion | 0 | PRIMARY | 1 | user_id | A | 1322871 | NULL | NULL | | BTREE | | | | suggestion | 0 | PRIMARY | 2 | type | A | 4703541 | NULL | NULL | | BTREE | | | | suggestion | 0 | PRIMARY | 3 | obj_id | A | 42331875 | NULL | NULL | | BTREE | | | | suggestion | 1 | user_id | 1 | user_id | A | 1175885 | NULL | NULL | | BTREE | | | | suggestion | 1 | user_id | 2 | rejected | A | 1209482 | NULL | NULL | | BTREE | | | | suggestion | 1 | type | 1 | type | A | 2 | NULL | NULL | | BTREE | | | | suggestion | 1 | type | 2 | created | A | 3848352 | NULL | NULL | | BTREE | | | | suggestion | 1 | rejected | 1 | rejected | A | 2 | NULL | NULL | | BTREE | | | | suggestion | 1 | rejected | 2 | type | A | 938 | NULL | NULL | | BTREE | | | | suggestion | 1 | rejected | 3 | created | A | 4703541 | NULL | NULL | | BTREE | | | +------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ 10 rows in set (0.00 sec) There are usually only a few items, betwen 100 and 200 per user_id, so an access by user_id is always the best strategy if it's known and static, like in that case. The funny thing about that bug is, according to the original query plan trace I posted above, the query planner KNOWS that the cost of using the type index is vastly higher than the cost for the other index - and chooses it anyway - as if the "low_limit" recheck code does not compare the original cost against its cost again and assumes, that an optimization for low LIMITS is always best.