MySql, I'm not sure if my indexes are correct or if I can improve the speed of my query?

My query is selecting on a date and a numeric key range, I'm not sure if I can improve on this, but I thought I'd ask. I'm hoping to improve the speed.

I'm actually running two very similar queries, one to do a c开发者_StackOverflowount and one to get the records with a limit

SELECT count(Pads.PadID) AS CountOfPadID FROM Pads WHERE ((RemoveMeDate=
'2001-01-01 00:00:00') AND (catid between 0 and 11)) 
ORDER BY VersionAddDate DESC;

SELECT PadID, CatID, IconSoureURL, OsStr, ProgramName, PageName, ProgramVersion, 
left(English450,650) as English450, English45, ProgHomeURL, DownloadURL, License,
ReleaseStatus FROM Pads WHERE RemoveMeDate='2001-01-01 00:00:00' AND catid 
between 0 and 11 ORDER BY VersionAddDate DESC LIMIT 0,20;

Yes the range can change, it could be 100 to 111

My first query takes 0.6 seconds and oddly the second query is quite quick even with SQL_NO_CACHE.

Heres the explain results from the first query.

Heres my current indexes

Both your queries return same data, may be different orders. But they touch same data on disk/table space/ may be same indexes too (Can you please put explain for query 2). First query actually warms caches for you, it will get data in memory and so second query is fast.

Can we make it faster?, probably its very fast already, its looking only 3 records, so index is perfect. First query may be was done on cold caches/bufferspools. Next time while doing benchmarking warm the caches first by running few random queries and check.

As suggested by @The-Scrum-Meister you can remove index RemoveMeDate, it will speed up your inserts and if its getting used now will reduce some pressure on memory.

Check if you need to tune the server/storage engine itself to fully utilize hardware available and make server fast.