Parcourir les résultats


Après avoir implémenté une requête top-N en pipeline pour récupérer efficacement la première page, vous aurez aussi souvent besoin d’une autre requête pour récupérer les pages suivantes. Le challenge qui en résulte est que la requête doit ignorer les lignes des pages précédentes. Il existe deux méthodes : tout d’abord la méthode de décalage, qui numérote les lignes à partir du début et utilise un filtre sur le numéro de lignes pour ignorer celles qui précèdent la page demandée. La seconde méthode, que j’appelle la méthode de recherche recherche la dernière ligne de la page précédente puis récupère les lignes suivantes.

Les exemples suivants montrent la méthode de décalage la plus fréquemment utilisée. Son avantage principal est qu’elle est très simple à gérer, tout spécialement avec les bases de données qui ont un mot clé dédié pour ça (offset). Ce mot-clé a même été repris dans le standard SQL comme faisant parti de l’extension fetch first.

MySQL

MySQL et PostgreSQL proposent la clause offset pour ignorer le nombre spécifié de lignes en partant du début d’une requête top-N. La clause limit est ensuite appliquée.

SELECT *
  FROM ventes
 ORDER BY date_vente DESC
 LIMIT 10 OFFSET 10;
Oracle

La base de données Oracle fournit la pseudo-colonne ROWNUM qui numérote automatiquement les lignes dans l’ensemble de résultats. Néanmoins, il n’est pas possible d’appliquer un filtre supérieur-ou-égal (>=) sur cette pseudo-colonne. Pour que cela fonctionne, vous devez tout d’abord matérialiser les numéros de ligne en renommant la colonne avec un alias.

SELECT *
  FROM ( SELECT tmp.*, rownum rn
           FROM ( SELECT *
                    FROM ventes
                   ORDER BY date_vente DESC
                ) tmp
          WHERE rownum <= 20
       )
 WHERE rn > 10;

Notez l’utilisation de l’alias RN pour la limite basse et l’utilisation de la pseudo-colonne ROWNUM directement pour la limite supérieure (merci à Tom Kyte).

PostgreSQL

L’extension fetch first définit la clause offset ... rows. Néanmoins, PostgreSQL accepte seulement offset sans le mot clé rows. La syntaxe limit/offset précédemment utilisée fonctionne toujours comme indiqué dans l’exemple MySQL.

SELECT *
  FROM ventes
 ORDER BY date_vente DESC
OFFSET 10
 FETCH NEXT 10 ROWS ONLY;
SQL Server

SQL Server n’a pas d’extension « offset » pour sa clause propriétaire top mais a introduit l’extension fetch first avec SQL Server 2012 (« Denali »). La clause offset est obligatoire bien que le standard la définisse comme optionnelle.

SELECT *
  FROM ventes
 ORDER BY date_vente DESC
OFFSET 10 ROWS
 FETCH NEXT 10 ROWS ONLY;

En dehors de la simplicité, un autre avantage de cette méthode est que vous avez juste besoin du décalage de la ligne pour récupérer une page arbitraire. Néanmoins, la base de données doit compter toutes les lignes à partir du début jusqu’à atteindre la page réclamée. La Figure 7.2 montre que l’intervalle parcouru de l’index devient plus grand quand on récupère plus de pages.

Figure 7.2. Accès utilisant la méthode du décalage


Cela présente deux inconvénients : (1) les pages se décalent lors de l’insertion de nouvelles ventes car la numérotation est toujours refaite à chaque fois ; (2) le temps de réponse croît en allant plus loin.

Le livre d'optimisation SQL destine aux développeurs !

La méthode de recherche évite ces deux inconvénients car elle utilise les valeurs de la page précédente comme délimiteur. Cela signifie qu’elle recherche les valeurs qui doivent être avant le dernier enregistrement de la page précédente. Cela se fait simplement avec une clause where. Autrement dit, la méthode de recherche ne sélectionne pas les valeurs déjà affichées.

L’exemple suivant montre la méthode de recherche. Pour cette démons­tration, nous commencerons avec une seule vente par jour. Cela fait de DATE_VENTE une clé unique. Pour sélectionner les ventes qui viennent après une date particulière, vous devez utiliser une condition plus-petit-que (<) à cause de l’ordre de tri descendant. Pour un ordre ascendant, vous devez utiliser la condition plus-grand-que (>). La clause fetch first est seulement utilisée pour limiter le résultat à dix lignes.

SELECT *
  FROM ventes
 WHERE date_vente < ?
 ORDER BY date_vente DESC
 FETCH FIRST 10 ROWS ONLY;

Au lieu d’un numéro de ligne, vous utilisez la dernière valeur de la page précédente pour indiquer la limite basse. L’énorme bénéfice consiste en des performances très importantes car la base de données peut exécuter la condition DATE_VENTE < ? en accédant à l’index. Cela signifie que la base de données peut vraiment ignorer les lignes des pages précédentes. De plus, vous obtiendrez aussi des résultats stables si de nouvelles lignes sont insérées.

Néanmoins, cette méthode ne fonctionne pas s’il y a plus d’une vente par jour, comme indiquée dans la Figure 7.2 parce qu’utiliser la dernière date à partir de la dernière page (« hier ») ignore tous les résultats d’hier, pas seulement ceux déjà montrés sur la première page. Le problème vient de la clause order by qui n’établit pas une séquence déterminée de lignes. Néanmoins, c’est un prérequis pour l’utilisation d’une condition d’intervalle simple pour les changements de pages.

Sans clause order by déterministique, la base de données, par définition, ne délivrera pas une séquence déterminée de lignes. La seule raison qui fait que vous obtenez habituellement une séquence cohérente de lignes est que la base de données exécute habituellement la requête de la même façon. Néanmoins, la base de données pourrait en fait renvoyer les lignes différemment en ayant une même DATE_VENTE tout en respectant la clause order by. Dans les versions récentes, vous pouvez obtenir le résultat dans un ordre différent à chaque fois que vous exécutez la requête, non pas parce que la base de données modifie intentionnellement l’ordre des lignes mais parce que la base de données pourrait utiliser une exécution parallélisée de la requête. Cela signifie que le même plan d’exécution peut aboutir à une séquence de lignes différentes car les différents exécuteurs finissent leur travail dans un ordre non déterminé.

Important

La pagination nécessite un ordre de tri déterministique.

Même si les spécifications fonctionnelles nécessitent uniquement un tri « par date, les derniers en premier », en tant que développeurs, nous voulons nous assurer que la clause order by ramène une séquence de lignes déterminée. Pour cela, nous pouvons avoir besoin d’étendre la clause order by avec des colonnes arbitraires. Si l’index utilisé pour l’order by en pipeline a des colonnes supplémentaires, il est bon de les ajouter à la clause order by pour continuer d’utiliser cet index pour un order by en pipeline. Si cela ne permet toujours pas d’avoir un ordre de tri déterminé, il suffit d’ajouter une (ou plusieurs) colonne unique et d’étendre l’index de la même façon.

Dans l’exemple suivant, nous étendons la clause order by et l’index avec la clé primaire, ID_VENTE, pour obtenir une séquence de lignes déterminée. De plus, nous devons appliquer la logique « vient après » aux deux colonnes ensemble pour obtenir le résultat désiré :

CREATE INDEX vt_dtid ON ventes (date_vente, id_vente);

SELECT *
  FROM ventes
 WHERE (date_vente, id_vente) < (?, ?)
 ORDER BY date_vente DESC, id_vente DESC
 FETCH FIRST 10 ROWS ONLY;

La clause where utilise la syntaxe peu connue appelée « valeurs de lignes » (voir l’encadré « Valeurs de ligne en SQL »). Elle combine plusieurs valeurs en une unité logique qui est applicable aux opérateurs standards de comparaison. Comme valeurs scalaires, la condition plus-petit-que correspond à « vient après » lors d’un tri en ordre descendant. Cela signifie que la requête considère seulement les ventes qui viennent après la paire DATE_VENTE, ID_VENTE donnée.

Valeurs de ligne en SQL

En dehors des valeurs scalaires habituelles, le standard SQL définit aussi ce qu’on appelle des constructeurs de valeur de ligne. Ils « donnent un ensemble ordonné de valeurs à assembler en une ligne complète ou partielle » [SQL:92, §7.1: <row value constructor>]. Syntaxiquement, les valeurs de ligne sont des listes entre crochets. Cette syntaxe est plus connue pour son utilisation dans l’instruction insert.

Néanmoins, utiliser des constructeurs de valeurs de ligne dans la clause where est bien moins connu et tout aussi valide. En fait, le standard SQL définit tous les opérateurs de comparaison pour des constructeurs de valeurs de ligne. Par exemple, voici la définition pour l’opération plus-petit-que :

"Rx < Ry" est vrai si et seulement si RXi = RYi pour tout i < n et RXn < RYn pour certains n.

— SQL:92, §8.2.7.2

i et n reflètent les positions dans les listes. Cela signifie qu’une valeur de ligne RX est plus petite que RY si chaque valeur RXn est plus petite que la valeur correspondante RYn et que toutes les paires de valeurs correspondantes sont égales (RXi = RYi; pour i<n).

Cette définition fait que l’expression RX < RY est synonyme de « RX est trié avant RY », ce qui est exactement la logique dont nous avons besoin pour la méthode de recherche.

Même si la syntaxe des valeurs de ligne fait partie du standard SQL, seules quelques bases de données la proposent. SQL Server 2012 (« Denali  ») n’accepte pas les valeurs de lignes. La base de données Oracle accepte les valeurs de ligne en principe mais ne peut pas leur appliquer les opérateurs d’intervalle (ORA-01796). MySQL évalue correctement les expressions de valeurs de ligne mais ne peut pas les utiliser en prédicat d’accès lors de l’accès à un index. Néanmoins, PostgreSQL accepte la syntaxe de valeur de ligne et les utilise pour accéder à l’index si un index correspondant existe.

Néanmoins, il est possible d’utiliser une variante approximative de la méthode de recherche avec des bases de données qui ne supportent pas correctement les valeurs de ligne, même si l’approximation n’est pas aussi élégante et efficace que les valeurs de lignes dans PostgreSQL. Pour cette approximation, nous devons utiliser des comparaisons « standards » pour exprimer la logique demandée comme dans cet exemple pour Oracle :

SELECT *
  FROM ( SELECT *
           FROM ventes
          WHERE date_vente <= ?
            AND NOT (date_vente = ? AND id_vente >= ?)
          ORDER BY date_vente DESC, id_vente DESC
       )
 WHERE rownum <= 10;

La clause where consiste en deux parties. La première considère seulement DATE_VENTE et utilise une condition plus-petit-que-ou-égal-à (<=). Elle sélectionne plus de lignes que nécessaire. Cette partie de la clause where est suffisamment simple pour que toutes les bases de données puissent l’utiliser en accédant à l’index. La deuxième partie de la clause where supprime les lignes en trop qui ont déjà été montrées sur la page précédente. L’encadré « Indexer une logique équivalente » explique pourquoi la clause where est exprimée de cette façon.

Indexer une logique équivalente

Une condition logique peut toujours être exprimée de plusieurs façons. Par exemple, vous pouvez aussi implémenter la logique montrée ci-dessus ainsi :

WHERE (
         (date_vente < ?)
       OR
         (date_vente = ? AND id_vente < ?)
      )

Cette variante utilise seulement les conditions incluantes et est certainement plus facile à comprendre, tout du moins pour les êtres humains. Les bases de données ont un point de vue différent. Elles ne comprennent pas que la clause where sélectionne toutes les lignes commençant avec la paire DATE_VENTE/ID_VENTE, en supposant que DATE_VENTE est la même pour les deux branches. À la place, la base de données utilise la clause where complète comme prédicat de filtre. Nous pouvons au moins nous attendre à ce que l’optimiseur factorise la condition DATE_VENTE <= ? des deux branches OU, mais aucune des bases de données ne le fait.

Néanmoins, nous pouvons ajouter manuellement la condition redondante, même si cela n’améliore pas la lisibilité :

WHERE date_vente <= ?
  AND (
         (date_vente < ?)
       OR
         (date_vente = ? AND id_vente < ?)
      )

Heureusement, toutes les bases de données peuvent utiliser cette partie de la clause where comme prédicat d’accès. Cependant, cette clause est plus dure à appréhender que la logique approximative montrée ci-dessus. De plus, la logique originale évite le risque que toute partie non nécessaire (redondante) soit supprimée accidentellement de la clause where.

Le plan d’exécution montre que la base de données utilise la première partie de la clause where comme prédicat d’accès.

---------------------------------------------------------------
|Id | Operation                      | Name    |  Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT               |         |    10 |    4 |
|*1 |  COUNT STOPKEY                 |         |       |      |
| 2 |   VIEW                         |         |    10 |    4 |
| 3 |    TABLE ACCESS BY INDEX ROWID | VENTES  | 50218 |    4 |
|*4 |     INDEX RANGE SCAN DESCENDING| VT_DTIT |     2 |    3 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(ROWNUM<=10)
   4 - access("DATE_VENTE"<=:DATE_VENTE)
       filter("DATE_VENTE"<>:DATE_VENTE
           OR "ID_VENTE"<TO_NUMBER(:ID_VENTE))

Les prédicats d’accès sur DATE_VENTE active la base de données pour ignorer les jours qui étaient affichés sur les pages précédentes. La deuxième partie de la clause where est seulement un prédicat d’accès. Cela signifie que la base de données inspecte de nouveau quelques lignes à partir de la page précédente, mais les supprime immédiatement. La Figure 7.3 montre le chemin d’accès respectif.

Figure 7.3. Accès utilisant la méthode de recherche


La Figure 7.4 compare les caractéristiques des performances des méthodes de décalage et de recherche. La précision de la mesure n’est pas suffisante pour voir la différence sur le côté gauche du graphe. Par contre, la différence est évidente à partir de la page 20.

Figure 7.4. Scalabilité lors de la récupération de la prochaine page


Bien sûr, la méthode de recherche a aussi des inconvénients, sa gestion difficile étant la principale. Non seulement vous devez être très attentif lors de l’écriture de la clause where, vous ne pouvez pas en plus récupérer des pages arbitraires. Mais, en plus, vous avez besoin d’inverser toutes les opérations de comparaison et de tri pour modifier la direction de la navigation. Plus précisément, ces deux fonctions, pour passer des pages et naviguer en sens inverse, ne sont pas nécessaires lors de l’utilisation du mécanisme de parcours infini pour l’interface utilisateur.

Trouvé une erreur?