Ti suggerisco di leggere questo articolo:

Come implementare la paginazione di un recordset MySQL con un ordinamento casuale della query