Если MyISAM, то COUNT(). Если InnoDB, то всё чуть
сложней, но и там т-щи к единому мнению пока не пришли. В целом, применительно к InnoDB базам я склоняюсь к решению на триггерах, которые при добавлении/удалении записей будут обновлять некоторое значение в отдельной табличке.