Consulta: Optimizar tiempo de respuesta

[miglos]

Saludos a todos!
Tengo un problema que espero me den alternativas de solución.

Debo registrar las llamadas que hacen los cllientes a una central telefonica, inicialmente se registraban entre 12 a 15 llamadas diarias, ahora esta cantidad se ha duplicado, por lo cual se hace mas pesada la consulta, y en los proximos 2 meses habra otro incremento similar. Actualmente cuento con 4700 registros aprox. y ya noto cierta lentitud al mostrar los resultados de las consultas.

Las tablas estan indexadas por los campos a los que se hace referencia en las consultas. Inicialmente mostraba las llamadas de todos los meses, ahora he hecho un filtro para que solo me muestre las llamadas del mes en curso y un combo para que se seleccione el mes y año si es que se quiere ver las llamadas de meses anteriores, ¿esto en que ayuda a agilizar la consulta y mostrar los resultados en pantalla? ¿debería guardar las llamadas de meses anteriores en otra tabla? ¿Alguna sugerencia o información adicional que deba meniconar?
La versión de MySQL es 4.1.21 y de PHP 4.4.4.

Gracias de antemano.