Efficient pagination with MySQL

I'm trying to speed up pagination of data on my site. I'd like to use the following query, but when I do an EXPLAIN it says it needs to scan over 40,000 rows:

SELECT `Item`.`id`, `User`.`id` 
FROM `items` AS `Item` 
LEFT JOIN `users` AS `User` 
    ON (`Item`.`submitter_id` = `User`.`id`) 
WHERE `Item`.`made_popular` < "2010-02-08 22:05:05" 
  AND `Item`.`removed` != 1 
ORDER BY `Item`.`made_popular` DESC 
LIMIT 26

But if I add a lower bound for the "made_popular" field it only needs to scan 99 rows (the number of items between those two dates).

SELECT `Item`.`id`, `User`.`id`
FROM `items` AS `Item` 
LEFT JOIN `users` AS `User` 
    ON (`Item`.`submitter_id` = `User`.`id`) 
WHERE `Item`.`made_popular` < "2010-02-08 22:05:05" 
    AND `Item`.`made_popular` > "2010-02-07 22:05:05" 
    AND `Item`.`removed开发者_开发技巧` != 1 
ORDER BY `Item`.`made_popular` DESC 
LIMIT 26

Both queries use the index I have on the "made_popular" column. In both cases shouldn't it only need to scan 26 rows, assuming there are no "removed" items? I guess the solution could be to go with the second query and add a lower bound that is probably low enough to give me 26 items, but it seems odd that I should have to do a workaround like that.

---

but when I do an EXPLAIN it says it needs to scan over 40,000 rows:

It is often to misunderstand what rows means. It means approximate amount of rows that could be used to return the result regardless LIMIT clause.

So you shouldn't worry in this case - mysql stops fetching data right after it reaches LIMIT amount.