How to count items per category?

I want to make a filtering of products on a site.
Something like this:

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)
 ...
 

How to count products per category? A separate SQL-query for each category would be too slow because there are too many products and categories. I suggest caching is not an option too.

Maybe it makes sense to use MySQL EXPLAIN queries (though it not always provide adequate information)? Or maybe using sphinx search engine for counting?... What is the best way to do this? Thanks.

---