Además hay que tener en cuenta que el tiempo de ejecución no sólo se lo toma la base de datos... sino también la aplicación (el PHP en este caso)...
En teoría, un script de paginación (como el que utilizas) te ayuda también a reducir este tiempo de ejecución. Paginator hace lo posible por utilizar la función COUNT() de mysql... lo cual reduce el tiempo de ejecución de la consulta (y mientras más registros sean, más se nota)... pero además se te devuelve sólo un "trozo" del resultset (el que mostrarás en cada página) y esto también ayuda en la reducción del tiempo de ejecución de la aplicación.
Pero lo ideal es que trates de optimizar tu diseño de BD, como dijo Cluster, porque los tiempos de las consultas dependen sobretodo de eso.
Saludos
