I'm having a big problem optimizing a particular query.

I have a table which we'll call "articles", that has 25 Million records in it, sorted into roughly 800 categories. When viewing each article, I have to be able to view the next 10 and previous 10 articles in that category.

The queries are below, but are taking 3 seconds or so to execute on average, which is killing performance. From looking at EXPLAIN and the slow query log, it appears that MySQL is examining several hundred thousand rows, presumably being rows that match up with the categoryId.

The relevant indexes I have on this table are:

primaryKey (primary key, of course)
categoryId (index)

And the queries are:

// Previous articles
SELECT * FROM articles WHERE primaryKey < 190221 AND categoryId = 123 ORDER BY primaryKey DESC LIMIT 0, 10;

// Next articles
SELECT * FROM articles WHERE primaryKey > 190221 AND categoryId = 123 ORDER BY primaryKey ASC LIMIT 0, 10;

Any help would be greatly appreciated, as it is killing the server right now, and I need to get it fixed tonight, if at all possible...

Thank you all so much!