dê uma olhada nos seguintes posts do blog:
1) COUNT(***) vs COUNT(col)
2) Dicas fáceis de desempenho do MySQL
3) Contagem rápida(*) para InnoDB
btw, qual motor você usa?
EDITADO: Sobre técnica para acelerar a contagem quando você precisa apenas saber se há alguma quantidade de linhas. Desculpe, apenas estava errado com a minha pergunta. Então, quando você precisa apenas saber, se houver, por exemplo, 300 linhas por condição específica, você pode tentar a subconsulta:
select count(*) FROM
( select 1 FROM _table_ WHERE _conditions_ LIMIT 300 ) AS result
primeiro você reduz o conjunto de resultados e depois conta o resultado; ele ainda verificará o conjunto de resultados, mas você pode limitá-lo (mais uma vez, funciona quando a pergunta para o banco de dados é "está aqui mais ou menos de 300 linhas) e se o banco de dados contiver mais de 300 linhas que satisfaçam a condição de que a consulta seja mais rápida
Resultados dos testes (minha tabela tem 6,7 milhões de linhas):
1)
SELECT count(*) FROM _table_ WHERE START_DATE > '2011-02-01' retorna 4,2 milhões por 65,4 segundos
2)
SELECT count(*) FROM ( select 1 FROM _table_ WHERE START_DATE > '2011-02-01' LIMIT 100 ) AS result retorna 100 por 0,03 segundos
Abaixo está o resultado da consulta de explicação para ver o que está acontecendo lá:
EXPLAIN SELECT count(*) FROM ( select 1 FROM _table_ WHERE START_DATE > '2011-02-01' LIMIT 100 ) AS result
