Carnet de notes

Pagi­na­tion sans limit ni offset

in

TL;DR: La pagi­na­tion c’est bien™, le faire avec des para­mè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 pagi­na­tion, au mieux vous manquez des données et en visua­li­sez d’autres en double, au pire vous corrom­pez tous vos calculs.

Hyper­me­dia

La solu­tion magique c’est que vos API retournent un nombre limité de résul­tats avec des liens dans les entêtes, proba­ble­ment 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’ex­plique rien, alors je vais prendre un exemple : Un hypo­thé­tique client Twit­ter sur une hypo­thé­tique API Twit­ter (je m’au­to­rise donc à ne pas préci­ser ce qui se fait sur les API actuelles).

Lorsque Twit­ter vous retourne les 100 derniers tweets de votre time­line avec les iden­ti­fiants 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 para­mètre since_id=3566. Quand vous voudrez rafrai­chir votre time­line, il vous suffira de suivre le lien. Il vous retour­nera 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 para­mètre max_id=3245. Quand vous voudrez aller cher­cher 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 fini­rez avec un lien qui contient et un since_id et un max_id, vous assu­rant de combler les trous que vous avez dans votre time­line, sans jamais renvoyer un message en double ni en oublier.

Si vous souhai­tez faire une synchro­ni­sa­tion complète, il suffit de stocker tous les liens rel=prev que vous rece­vez dans une liste, et d’al­ler les suivre un à un à la fréquence que vous souhai­tez. Vous pouvez avoir un autre fil d’exé­cu­tion en paral­lè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é­ra­le­ment un rel=next (messages juste suivants) plutôt qu’un rel=last (derniers messages), mais Twit­ter est parti­cu­liers : Ça va si vite qu’en géné­ral la prio­rité est d’avoir les derniers messages à date, quitte à géné­rer des trous dans la time­line qui seront comblés plus tard.

Twit­ter est aussi facile parce qu’on trie toujours pas date, et que l’iden­ti­fiant unique de chaque message est toujours ordonné lui aussi. Ailleurs on utili­sera peut être la date de dernière modi­fi­ca­tion comme pivot pour gérer la pagi­na­tion. L’im­por­tant est que le critère de tri soit cohé­rent avec la donnée utili­sée comme pivot

 

Comments

5 réponses à “Pagi­na­tion sans limit ni offset”

  1. Avatar de mat
    mat

    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. Avatar de Éric
      Éric

      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. Avatar de mat
      mat

      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).

  2. Avatar de nyro
    nyro

    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. Avatar de Éric
      Éric

      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.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *