echa un vistazo a las siguientes entradas de blog:
1) COUNT(***) vs COUNT(col)
2) Consejos fáciles de rendimiento de MySQL
3) Conteo rápido (*) para InnoDB
por cierto, que motor usas?
select count(*) FROM
( select 1 FROM _table_ WHERE _conditions_ LIMIT 300 ) AS result
al principio, minimiza el conjunto de resultados y luego cuenta el resultado; aún escaneará el conjunto de resultados, pero puede limitarlo (una vez más, funciona cuando la pregunta a la base de datos es "hay más o menos de 300 filas aquí), y si la base de datos contiene más de 300 filas que cumplen la condición de que la consulta es más rápida
Resultados de las pruebas (mi tabla tiene 6,7 millones de filas):
1) SELECT count(*) FROM _table_ WHERE START_DATE > '2011-02-01'
devuelve 4,2 millones durante 65,4 segundos
2) SELECT count(*) FROM ( select 1 FROM _table_ WHERE START_DATE > '2011-02-01' LIMIT 100 ) AS result
devuelve 100 durante 0,03 segundos
A continuación se muestra el resultado de la consulta de explicación para ver qué está pasando allí:
EXPLAIN SELECT count(*) FROM ( select 1 FROM _table_ WHERE START_DATE > '2011-02-01' LIMIT 100 ) AS result