Как посчитать предметы по категориям?

Хочу сделать фильтрацию товаров на сайте. Примерно так:

Department
- lassics (13,395)
- Literary (111,399)
- History (68,606)
...

Format
- HTML (3,637)
- PDF (8)
- Audio CD (443)
...

Language
- English (227,175)
- German (10,843)
- French (10,488)
...

Как посчитать товары по категориям? Отдельный SQL-запрос для каждой категории был бы слишком медленным, потому что товаров и категорий слишком много. Я предлагаю кэширование тоже не вариант.

Может быть, имеет смысл использовать EXPLAIN-запросы MySQL (хотя они не всегда дают адекватную информацию)? Или, может быть, использовать поисковую систему sphinx для подсчета?... Как лучше всего это сделать? Спасибо.