Page trop lourde, trop de resultats !

Bonjour,

J'ai un souci auquel je n'ai jamais eu a faire face c'est à dire charger un bon millier de resultats !

Je m'explique, je suis en train de monter un annuaire.
J'ai un peu moins de 1300 entrees dans ma base.
j'ai donc une page annuaire qui n'affiche que par 20 resultats en page par page.

malgré ca, ma page met environ 8sec pour se charger !!!

voici ma requete :

select
L.tous_mes_champs, (SUM(N.note_critere1)+SUM(N.note_critere2)+SUM(N.note_critere3)+SUM(N.note_critere4)+SUM(N.note_critere5))/(select COUNT(*) from table_commentaires N where N.id_lieu=L.id and N.valide='oui') as NoteTotale, 
V.ville_id, V.ville_nom_reel as nomVille, V.ville_slug, V.ville_departement 
from annuaire L 
join villes V 
on
L.id_ville=V.ville_id left 
join
table_commentaires N on N.id_lieu=L.id	
where
L.valide='oui' 
group by
L.id 
order by L.nom asc

vous me direz en voyant ca que je charge toute ma base !!
oui et c'est bien mon souci...

en fait, les lieux que je charge sont notés (tri incorporé dans la requete), mais je fais aussi un tri en fonction de leur taux de remplissage (ca je ne sais sais absolument pas comment l'incorporer dans ma requete !!!
du coup je fais un premier tri avec le requete du dessus. Je balance tout dans un array, et dans ce array, je calcule le taux de remplissage que j'integre au array dans le premier while, et apres je fais un foreach avec mes filtres et tris...

et le page par page joue sur l'affiche du array.

du coup, comment pourrais-je contourner ce probleme et ne pas charger a chaque affichage toute ma table ???

merci d'avance !!
et bon weekend a tous