Желательно, конечно, одним запросом. Если не получится красиво на MySQL, придется делать несколько запросов и хранить результаты в кеше, потому что выборка по одной рубрике получается около 30-120 миллисекунд аж.
Примерная структура таблиц:
Рейтинг для таблицы рубрик в этой же таблице. И для наименований рейтинг в колонке таблице наименований.
items
— id
cat_id
title
rating
cats
— id
title
rating