Bonjour,

Mettons nous en situation (purement théorique) : un forum possédant 100 000 topics, on souhaite en afficher 20 par page.
On utilise classiquement :

SELECT xxx FROM yyy LIMIT 0,20

Mais lorsque l'on avance dans les pages on arrive à des requêtes du genre :

SELECT xxx FROM yyy LIMIT 60000,20

Ce qui est extrêmement lourd car la requête va parcourir les 60000 premiers enregistrement avant de nous renvoyer les données que nous souhaitons recevoir.

Toujours dans cette situation, nous avons affaire à une table où très souvent des topics sont supprimés, donc utiliser des requêtes de la sorte serait suicidaire :

SELECT xxx FROM yyy WHERE yyy.id BETWEEN 60000 AND 60020

Ma question est donc la suivante : Dans ce cas précis, existe il des solutions pour optimiser ce genre de traitements ?
D'avance merci pour vos réponses.

Citation : flow10000

Bonjour,
Ce qui est extrêmement lourd car la requête va parcourir les 60000 premiers enregistrement avant de nous renvoyer les données que nous souhaitons recevoir.

Es-tu sûr de ce que tu avances ? À mon avis les SGBD utilisent des algorithmes optimisés pour ça, tables de hachage, quick-sort, heap... ça doit dépendre des SGDB, mais accéder directement à la 60 000ème entrée n'est certainement pas très dur.

Je pense la même chose que BigGy.

Une base de données doit surement posséder des algorithmes assez puissants dans ce genre de situation, au point que tu ne verrais pas la différence entre un BETWEEN 0 AND 20 et un BETWEEN 60000 AND 60020.

Citation

Es-tu sûr de ce que tu avances ? À mon avis les SGBD utilisent des algorithmes optimisés pour ça, tables de hachage, quick-sort, heap... ça doit dépendre des SGDB, mais accéder directement à la 60 000ème entrée n'est certainement pas très dur.

Hmmm c'est ce que j'ai pu lire sur developpez.com et autres (je n'ai pas les liens des sources sous la main désolé).

Citation : guk92

Une base de données doit surement posséder des algorithmes assez puissants dans ce genre de situation, au point que tu ne verrais pas la différence entre un BETWEEN 0 AND 20 et un BETWEEN 60000 AND 60020.

Heu oui je sais que BETWEEN 0 AND 20 et BETWEEN 60000 AND 60020 ne font pas de différence, je parle du LIMIT moi.

Enfin tout ça pour dire que j'aimerais une réaction d'un mec vraiment au courant de ces choses là.
D'avance merci à celui qui passerait par là !

Tu as oublié l'ordre : si tu veux paginer, il faut définir un ordre.

Par exemple, une requête typique de forum : lister une page de posts, en triant les posts dans l'ordre d'insertion (on utilise l'id, c'est plus simple qu'une date). Mettons qu'il y a 10 posts par page et qu'on affiche la page 10, on saute les 90 premiers posts et on affiche les 10 suivants.

SELECT * FROM posts WHERE topic_id=? ORDER BY post_id LIMIT 90,10  -- mysql
SELECT * FROM posts WHERE topic_id=? ORDER BY post_id LIMIT 10 OFFSET 90  -- vrai sql

Ce genre de requête ne pose pas trop de problème pour les topics normaux (quelques dizaines de posts) mais il y a toujours l'occasionnel topic à flood qui a des centaines de pages. On rencontre ce type de requête dans pas mal d'autres applications... donc je mets des topics et des posts pour l'exemple, mais ça peut être n'importe quoi.

Citation : BigGy

Es-tu sûr de ce que tu avances ? À mon avis les SGBD utilisent des algorithmes optimisés pour ça, tables de hachage, quick-sort, heap... ça doit dépendre des SGDB, mais accéder directement à la 60 000ème entrée n'est certainement pas très dur.

La BDD a plusieurs façons de gérer ça :

1) Si tu n'as pas d'index sur (topic_id, post_id), elle prend l'index sur topic_id (en espérant qu'il y en ait un...), chope les posts qui ont topic_id=?, les trie, jette les 90 premiers, garde les 10 qui nous intéresse, et jette tous les résultats suivants.

- MySQL trie tout
- postgres remarque qu'aucun résultat au-delà du 100ème n'est intéressant donc il utilise une méthode de tri spéciale, avec un buffer de 100 lignes uniquement, qui économise de la RAM
- les deux doivent regarder tous les posts pour extraire les ids avant de les trier

Bien sûr, sur un topic à flood, c'est lent.

2) Si tu as un index sur (topic_id, post_id) alors l'index est utilisé pour l'ORDER BY, donc il n'y a plus de tri. Il suffit de parcourir l'index dans l'ordre, en sautant les 90 premières lignes, et renvoyer les 10 suivantes.

Mais il faut toujours sauter les lignes qui ne nous intéressent pas.

> accéder directement à la 60 000ème entrée n'est certainement pas très dur

Ce n'est pas faisable (révise la façon dont fonctionne un index btree).

Donc oui, c'est lent aussi.

Solution

Si on n'a pas un forum mais par exemple un moteur de recherche avec moultes options de recherche et de tri, pas d'optimisation particulière (on laisse faire la BDD).

Pour un forum, deux options.

1) la méthode du sandwich

- on a stocké le nombre de posts de chaque topic dans la table topics (c'est obligatoire de toutes façons...)
- on remarque que la plupart du temps on n'accède qu'à la première ou à la dernière page (surtout pour un topic à flood où tout le monde s'en branle des pages du milieu)

Donc quand on demande la page X, on regarde le nombre de posts dans le topic, donc on sait si la page est avant ou après le "milieu" du topic.

Si la page est plus près du début, on fait ORDER BY post_id ; si la page est plus proche de la fin, on fait ORDER BY post_id DESC et on ajuste le LIMIT et l'OFFSET pour retomber comme il faut. Les posts arrivent dans l'ordre inverse, il suffit de les mettre dans un array de de les retourner avant de les afficher.

Du coup, les pages les plus rapides sont la première et la dernière, et la plus lente celle du milieu.

2) la numérotation

On met un trigger qui numérote chaque post dans son topic. C'est pas compliqué, il suffit d'un lock (facultatif si la FK sur topics en tient lieu) et un SELECT max(numero_post)+1 FROM topics WHERE topic_id=?.

Donc ça devient :

SELECT * FROM posts WHERE topic_id=? AND numero_post BETWEEN 91 AND 100 ORDER BY numero_post

Là, l'accès est instantané pour toutes les pages (avec un index sur (topic_id,numero_post) bien sûr) mais si on delete un post, il faut remettre à jour tous les numéros, c'est chiant. Solution plus simple : on laisse les posts supprimés en les remplaçant par un petit message (comme sur le SdZ) ce qui garde la numérotation.

J'ai implémenté les 2...

méthode 1 : sur un topic avec 6000 posts on est à quelques millisecondes pour la première et la dernière page (2 ms de SQL et 4 ms de php, ça rame)

mais gros inconvénient de la méthode 1, si un mec clique sur la page du milieu d'un gros topic, il faut quand même parcourir la moitié de l'index, et comme tout le monde s'en branle des pages du milieu des topics à flood, les données ne sont pas du tout en cache, donc ça donne une bonne rafale d'accès disque (ici 3s... lol)
après c'est en cache donc ça va...

et gros avantage de la méthode 2 : comme l'accès est indexé directement, même si c'est pas en cache, au pire c'est quelques seeks dans l'index et un accès direct à la table des posts donc il n'y a pas ce problème.

Il faut bien examiner les perfs de requête SQL quand les données ne sont pas en cache... pour éviter les surprises fâcheuses (genre ton serveur implose quand la taille de la BDD dépasse la RAM, vu et re-vu...)

Aussi il faut que la table des posts soit organisée (sur le disque) par (topic_id,post_id) pour que 1 seul accès disque ramène tous les posts d'une page de topic. Sous postgres on utilisera la commande CLUSTER, sous MySQL/MyISAM (lol) OPTIMIZE TABLE ORDER BY, et sous mySQL/InnoDB on pleurera vu que c'est pas possible à moins de définir (topic_id,post_id) comme clé primaire, ce qui serait quand même moche XDDDD

Très intéressant, merci

très instructif en effet, merci lord!
Je laisse le topic en non résolu si toutefois quelqu'un voulait compléter/ajouter des choses à ce que tu as dit.

Je remonte en espérant que Lord Casque Noir passera par là...

Citation : Lord Casque Noir

On met un trigger qui numérote chaque post dans son topic. C'est pas compliqué, il suffit d'un lock (facultatif si la FK sur topics en tient lieu) et un SELECT max(numero_post)+1 FROM topics WHERE topic_id=?.

Donc ça devient :

SELECT * FROM posts WHERE topic_id=? AND numero_post BETWEEN 91 AND 100 ORDER BY numero_post

Là, l'accès est instantané pour toutes les pages (avec un index sur (topic_id,numero_post) bien sûr) mais si on delete un post, il faut remettre à jour tous les numéros, c'est chiant. Solution plus simple : on laisse les posts supprimés en les remplaçant par un petit message (comme sur le SdZ) ce qui garde la numérotation.

Au cas ou lorsque je delete un post je souhaite le supprimer de la base, il faut que je remette à jour les numéros, il y à une solution simple pour faire ça ? (par simple je parle d'une solution peu couteuse en terme de ressources server...)
Sachant que ça arriverait très fréquemment...


merci!

Ce que tu peux faire c'est mettre NULL dans le contenu du post par exemple et ne pas afficher quand le contenu vaut NULL. Après, si tu tiens vraiment à les supprimer réèllement de ta base (si tu as beaucoup de posts supprimés et que ton espace disque est compté) tu peux effectuer des tâches CRON aux heures creuses de visites de ton site une fois par jour, semaine ou mois par exemple. (Un genre de défragmentation de la table quoi )

pour remettre à jour les numéros, tu peux faire par exemple :

UPDATE posts SET post_number = post_number-1 
WHERE topic_id = $topic_id AND post_id > $id_du_post_supprimé

mais il faudra modifier autant de lignes qu'il y a de posts après le post supprimé, donc ça peut vite chiffrer ...

Oui voilà le problème est que je gagnerais du temps à l'affichage des post mais j'en perdrai lors des delete...

Citation : BigGy

Ce que tu peux faire c'est mettre NULL dans le contenu du post par exemple et ne pas afficher quand le contenu vaut NULL

Hmmm mais le problème c'est que je risque de delete vraiment beaucoup de posts et je risque de me retrouver avec des pages contenant seulement 2 commentaires au lieu de 20 c'est relativement moche.. :s

Citation : flow10000

Oui voilà le problème est que je gagnerais du temps à l'affichage des post mais j'en perdrai lors des delete...

À toi de voir si tu as plus de posts supprimés que de posts affichés

Citation : flow10000

Citation : BigGy

Ce que tu peux faire c'est mettre NULL dans le contenu du post par exemple et ne pas afficher quand le contenu vaut NULL

Hmmm mais le problème c'est que je risque de delete vraiment beaucoup de posts et je risque de me retrouver avec des pages contenant seulement 2 commentaires au lieu de 20 c'est relativement moche.. :s

Je comprends pas là, tu veux les supprimer de toute façon tes posts non ?

tiens, un autre truc, si t'affiches 20 posts par page par exemple, tu créé une table topics_pagination( topic_id, no_page, post_id ) qui donne l'id du premier post de chaque page, comme ça l'affichage est tout aussi instantané, et t'as 20x moins de lignes à update pour décaler les posts après une suppression.

au fait, pourquoi tu comptes supprimer autant de posts ?

Citation : Lord Casque Noir

tiens, un autre truc, si t'affiches 20 posts par page par exemple, tu créé une table topics_pagination( topic_id, no_page, post_id ) qui donne l'id du premier post de chaque page, comme ça l'affichage est tout aussi instantané, et t'as 20x moins de lignes à update pour décaler les posts après une suppression.

au fait, pourquoi tu comptes supprimer autant de posts ?

pas bête...
Je suis preneur de toutes vos idées/astuces de la sorte.
Je compte supprimer autant de post car je travail sur un forum où l'on pourra poster en anonyme..