Well, if SELECT COUNT(*) is too slow for you, you could store the count in a separate table (just one record really) and update that number whenever a record is inserted or deleted. You may even be able to do that automatically with stored procedures and triggers.
