Logica para paginar con stored procedures

[flaviovich]

Hola amigos,
tengo un SP (stored procedure) en mysql 5.1, el cual me permite extraer informacion segun los parametros recibidos, entre los cuales tengo 2 que son para limitar la cantidad de registros (para la paginacion).
Mi duda es que no se si crear el mismo SP sin los 2 parametros para la paginacion ya que necesito primero saber la cantidad total de registros para poder saber cuantas paginas tendre.
Debo decir que no tengo mucha experiencia en mysql/php y tal vez no lo este haciendo de la forma correcta.
Espero sus recomendaciones!