Pagination sans limit ni offset

TL;DR: La pagination c’est bien™, le faire avec des paramètres limit/offset c’est mal™.

C’est très simple à expliquer : Si les données sont mises à jour entre deux requêtes d’une même pagination, au mieux vous manquez des données et en visualisez d’autres en double, au pire vous corrompez tous vos calculs.

Hypermedia

La solution magique c’est que vos API retournent un nombre limité de résultats avec des liens dans les entêtes, probablement un rel=next pour les données suivantes et/ou un rel=prev pour les données précédentes. Le client n’a qu’à suivre les liens.

En pratique

OK, je triche parce que je n’explique rien, alors je vais prendre un exemple : Un hypothétique client Twitter sur une hypothétique API Twitter (je m’autorise donc à ne pas préciser ce qui se fait sur les API actuelles).

Lorsque Twitter vous retourne les 100 derniers tweets de votre timeline avec les identifiants 3245 à 3566, il peut vous renvoyer deux liens dans les entêtes :

Un rel=last qui mène en fait vers l’exacte requête que vous avez faite mais avec en plus un paramètre since_id=3566. Quand vous voudrez rafraichir votre timeline, il vous suffira de suivre le lien. Il vous retournera les nouveaux messages jusqu’au 3566 non compris, mais jamais ceux que vous avez déjà reçu.
Un rel=prev qui mène vers l’exacte même requête que vous avez faite, mais avec en plus un paramètre max_id=3245. Quand vous voudrez aller chercher les messages plus anciens, il vous suffira de suivre le lien.

Si vous suivez un rel=prev après avoir suivi un rel=last vous finirez avec un lien qui contient et un since_id et un max_id, vous assurant de combler les trous que vous avez dans votre timeline, sans jamais renvoyer un message en double ni en oublier.

Si vous souhaitez faire une synchronisation complète, il suffit de stocker tous les liens rel=prev que vous recevez dans une liste, et d’aller les suivre un à un à la fréquence que vous souhaitez. Vous pouvez avoir un autre fil d’exécution en parallèle qui suit le rel=last de temps en temps (il n’y en aura qu’un seul à la fois, vous en aurez un nouveau à chaque fois que vous suivez le précédent).

Bon, dans la vraie vie vous aurez généralement un rel=next (messages juste suivants) plutôt qu’un rel=last (derniers messages), mais Twitter est particuliers : Ça va si vite qu’en général la priorité est d’avoir les derniers messages à date, quitte à générer des trous dans la timeline qui seront comblés plus tard.

Twitter est aussi facile parce qu’on trie toujours pas date, et que l’identifiant unique de chaque message est toujours ordonné lui aussi. Ailleurs on utilisera peut être la date de dernière modification comme pivot pour gérer la pagination. L’important est que le critère de tri soit cohérent avec la donnée utilisée comme pivot

Publié

17 février 2015

dans

Développement informatique

par

Éric

Étiquettes :

Commentaires

5 réponses à “Pagination sans limit ni offset”

mat

17 février 2015

Bénéfice sympa en terme de perf pour la plupart des bases de données (mon exemple est en SQL mais s’applique aussi à pas mal de bases NoSQL) :
SELECT * FROM foo LIMIT 10 OFFSET 100 demande à la base d’aller jusqu’au 100ème élément pour ensuite en chopper 10 (autrement dit, d’en chopper 110 mais d’ignorer les 100 premiers – super coûteux!).

SELECT * FROM foo WHERE id < since_id ORDER BY id DESC LIMIT 10 demande à la base d'aller jusqu'à l'id since_id dont la position peut être récupérée immédiatement (en admettant que ça soit la clé primaire) pour ensuite chopper les 10 id suivants dans l'ordre.

Tout n'est pas rose, ça demande d'avoir des id incrémentaux (et de pas boucher les trous en cas d'effacement), mais c'est souvent le cas.

http://use-the-index-luke.com/no-offset

Répondre
1. Éric
  
  18 février 2015
  
  Même sans id incrémental, tu peux souvent utiliser une date de mise à jour, ou un autre champ qui respecte l’ordre de tri souhaité.
  
  Sinon en général pas besoin de boucher les trous en cas d’effacement : Si tu vas chercher les 100 à 110, c’est quasiment toujours que tu es déjà allé cherché les les 90 à 100, donc tu connais l’id du 100ème, même s’il y a des trous.
2. mat
  
  18 février 2015
  
  Je disais justement qu’il ne faut *pas* boucher les trous, ou alors on retombe dans le même problème et on manque des données.
  
  Et oui, effectivement on peut aussi utiliser n’importe quel autre champ (ou même combinaison de champs) sur lequel on trie vu qu’il sera généralement indexé (sinon c’est pas malin de trier dessus de toutes façons).
nyro

20 février 2015

Idée très sympa et bien expliquée.
Mais si on utilise une date de mise à jour et qu’un élément et mis à jour entre 2 requêtes, on va se retrouver avec des doublons ou des éléments manquants, non ?

Répondre
1. Éric
  
  20 février 2015
  
  En gros, si pour l’instant tes documents sont dans l’ordre ABCD, que tu les récupères 1 à 1 :
  
  * Au départ : ordre=ABCD, récupéré=Ø
  * Tu récupères le premier élément : ordre=ABCD, récupéré=A
  * Tu récupères l’élément suivant : ordre=ABCD, récupéré=AB
  * On modifie C : ordre CABD, récupéré=AB
  * Tu récupères l’élément suivant : ordre=CABD, récupéré=ABD
  * Il n’y a plus d’élément suivant à récupérer
  
  Effectivement, il te manque C et E, mais ça aurait aussi été le cas si tu avais fait la requête à partir de A un chouiat plus tard.
  
  Si tu suis le rel=start de mon exemple pour aller chercher les mises à jours récentes, tes prochaines requêtes vont être :
  
  * Premier élément : récupéré=E, anciens=ABD
  * Élément suivant : récupéré=EC, anciens=ABD
  
  Quand il n’y a plus d’éléments suivants, tu peux donc coller les deux jeux de données et avoir ECABD. Tu as toujours le risque que de nouveaux éléments soient arrivés ou modifiés en parallèle. Charge à toi d’aller encore suivre le rel=start.
  
  En gros tu n’as jamais fini et il faut faire une boucle jusqu’à ne plus rien avoir de neuf, mais c’est normal si ton jeu de données n’arrête pas de bouger.
  
  *
  
  Après tout est question de priorité. Si tu as besoin d’avoir un jeu complet à un instant T, quitte à ce qu’il soit vieux, tu trieras probablement par date de création et non par date de modification. C’est le cas si par exemple tu veux récupérer la liste de tout le personnel d’une société.
  
  À l’inverse, si ta priorité est de jouer avec les données récentes (ou si l’historique est infini) tu trieras plutôt par date de modification, quitte à avoir des « trous » temporairement dans tes données. C’est généralement le cas d’un lecteur RSS ou d’une synchronisation d’événements.
  
  Par contre dans les deux cas, tu as avantage à utiliser le système décrit. Le seul cas où l’offset est intéressant, c’est si le jeu de données sélectionné n’est pas modifié entre deux requêtes.