Пробуем. Все замеры на таблице с 5000 записей, рандомным cid от 1 до 10, id primary, на cid индекс.

На PostgreSQL можно запрашивать

SELECT a.*
FROM somedata AS a
WHERE a.id IN (
	SELECT b.id
	FROM somedata AS b
	WHERE b.cid = a.cid
	ORDER BY b.id DESC
	LIMIT 5
)
ORDER BY a.cid DESC, a.id DESC

Но запрос медленный (0.125 сек), и время выполнения растёт прямо пропорционально кол-ву записей и категорий. MySQL вообще не поддерживает LIMIT во вложенных запросах, идём дальше. Мастерим страшного монстра:

SELECT a.*
FROM somedata AS a
WHERE a.id IN (
	SELECT id
	FROM somedata AS b
	WHERE b.cid = a.cid AND (SELECT COUNT(*) FROM somedata AS c WHERE c.id >= b.id AND c.cid = b.cid) <= 5
)
ORDER BY a.cid DESC, a.id DESC

Он, конечно, справился, получены верные данные, но выполнение такого запроса заняло… 15.87 сек. Не хотеть, правда? :)

Самым производительным оказалось эстетически уродливое уродливое решение. Склеиваем в PHP запросы для каждой категории в единый с помощью UNION:

(SELECT * FROM somedata WHERE cid = 1 ORDER BY id DESC LIMIT 5)
UNION
(SELECT * FROM somedata WHERE cid = 2 ORDER BY id DESC LIMIT 5)
UNION
(SELECT * FROM somedata WHERE cid = 3 ORDER BY id DESC LIMIT 5)

и т.д. до cid = 10, и о чудо: запрос выполняется на MySQL за 0.002 сек, выдавая нужный результат.

Хотя, возможно я упустил какое-то очевидное решение с приемлемой производительностью. Если найдёте – расскажите нам :)

Используйте если нет возможности использовать PostgreSQL или ставить Sphinx — используйте для поиска по сайту Google Search API.