Какой формат шаблона выбрать для использования в нем php переменных?

doc — это бинарный формат, никак не xml; docx — zip-контейнер, содержащий xml-файлы.

Помогите составить mysql select запрос, подробности под катом

MySQL вроде же не поддерживает LIMIT во вложенных запросах?

Как выбрать одним запросом 5 последних записей каждой категории в MySQL?

Протестировал ваш метод с теми же 5к строк и cid 1-10, получилось ~0.047 с. Видимо это действительно самый оптимальный вариант.