Я только что провел несколько тестов на MySQL 4.0, у нас есть таблица с более чем 1 миллионом записей.
SELECT COUNT(*) FROM MyTable;
~ 1 миллион занял 22мс
SELECT COUNT(*) FROM MyTable WHERE Role=1;
~ 800 000 заняло 3,2 с
SELECT COUNT(*) FROM MyTable WHERE Role=2;
~ 20 заняло 12 мс
Столбец Роль в этом случае был проиндексирован, и он подключался к MySQL удаленно.
Я думаю, что ваша таблица сообщений должна стать очень большой, чтобы время запросов действительно становилось проблемой. Я также думаю, что это предварительная оптимизация, чтобы поместить кеш в таблицу тем. Создайте его без него на данный момент и , если это станет проблемой, его довольно легко обновить, чтобы изменить.