Beh la soluzione e' sempre il limit x,y .

Io farei una cosa del genere :
Codice PHP:

$currPage 
abs($_GET["page"]);

$counts 20 //Righe per pagina

$pageFrom = ($counts*$currPage) :
$pageto $pageFrom+$counts ;

// Incrementiamo di 1 se nn siamo sulla prima pagina per evitare la ripetizione 
//dell'ultimo ris della pag prec
if( $pageFrom!=0)
   
$pageFrom++;

$q "select * from users order by nome asc limit ".$pageFrom.",".$pageTo." " ;

etc.....