A priori je vois 2 types de pagination différents:

• Tu récupères tous les résultats dans ton script php et ne conserve que ceux qui t'intéressent en fonction de la page demandée (en y accédant via un mysql_data_seek par ex). Inconvénient : ça devient lourd quand ta requete retourne qques milliers d'enregistrements.
• Tu ne récupères que les enregistrements de la page demandée (via un LIMIT dans la requete). Inconvénient : obliger de faire d'abord une requete count (sinon impossible de connaitre le nombre de pages, de résultats).

Actuellement j'utilise la première méthode mais avec mysql4 et le query cache je me disais que la 2e méthode deviendrait peut être plus intéressante (car le count ne serait plus effectué à chaque fois).
 
Bref si avez des avis dessus ou d'autres solutions...

Tu aurais du faire la deuxième depuis le début. De toute façon, la query SELECT count(*) FROM table est une requète optimisée DEPUIS mysql 3, elle ne compte pas tous les enregistrements, mais juste un registre.

mais si je fais un SELECT count(*) FROM mabase WHERE blabla AND blabla AND blabla OR blabla
 
il va bien etre obligé de faire la requete, non ?

il va te retourner une valeur et pas plusieurs milliers.
Et côté utilisation CPU, c'est vraiment minime.
Ton "select * from ..." sans LIMIT sera énormément plus lourd même en contant le temps d'exécution du select avec le LIMIT.
En plus, tu gagnes beaucoup de bande passante réseau en fesant comme ça.
Bref, t'as vraiment pas à hésiter.

si j'hésite car mysql et apache sont sur le meme serveur donc j'ai pas de pb de bp. et honnêtement si je me souviens bien de mes tests, j'obtenais des résultats meilleurs avec la première méthode (logique puisque mysql ne parcourt mes 4000 enregistrements qu'une seule fois)

C'est quand même bizare, mais bon, après tout, il est possible que certains cas soient étonant.
T'avais mis des index au moins sur ta table par ce que si t'en avait mis, j'en suis tout à fait surpris.

pas d'index. c'est un autre problème d'ailleurs ça parce que j'ai une requete moyennement complexe et pas moyen de faire un index et qu'il soit utilisé pour la requete (qd je fais un explain, mysql me dit bien qu'il pourrait l'utiliser mais ne l'utilise pas).

 
Tu les stockent où tes 4000 enregistrement pour les autres affichages ?

Moi, je sais pas si mysql utilise mes index mais je les crée pour les colones les plus utiliuser au niveau des conditions. Comme ça, si mysql l'utilise, on gagne du temps et sinon, j'aurais fait les chôses proprement.

 
une seule fois par page je voulais dire.