Récupérer les N premières lignes

Les requêtes Top-N sont des requêtes qui limitent le résultat à un nombre spécifique de lignes. Ce sont souvent des requêtes permettant de récupérer les enregistrements les plus récents ou les plus intéressants sur un ensemble de résultats. Pour une exécution efficace, le tri doit se faire avec un order by en pipeline.

La façon la plus simple de récupérer les premières lignes d'une requête est de récupérer les lignes intéressantes puis de terminer la requête. Malheureusement, l'optimiseur ne peut pas le deviner en préparant le plan d'exécution. Pour trouver le meilleur plan d'exécution, l'optimiseur doit savoir si l'application récupérera au final toutes les lignes. Dans ce cas, un parcours complet de table avec une opération explicite de tri pourrait être plus performante, alors qu'un order by serait meilleur si on ne souhaite récupérer que les dix premières lignes, même si la base de données doit récupérer les dix lignes une par une. En d'autres termes, l'optimiseur doit savoir si vous allez annuler la requête avant d'avoir récupéré toutes les lignes pour sélectionner le meilleur plan d'exécution.

Le standard SQL n'a pas pris en compte ce besoin pendant longtemps. L'extension correspondante (fetch first) a été introduite à partir de SQL:2008 et est actuellement seulement disponible avec IBM DB2, PostgreSQL et SQL Server 2012. Ceci est dû dans un premier temps au fait que cette fonctionnalité n'est pas une extension principale, mais aussi parce que chaque base de données propose sa solution propriétaire depuis de nombreuses années.

Les exemples suivants montrent l'utilisation de telles extensions en récupérant les dix ventes les plus récentes. La base est toujours identique : récupérer toutes les ventes, en commençant par la plus récente. La syntaxe top-N respective annule simplement l'exécution après avoir récupéré dix lignes.

Toutes les requêtes SQL affichées ci-dessus sont spéciales car les bases de données les reconnaissent comme des requêtes top-N.

Si l'optimiseur sait que nous n'avons besoin que des dix premières lignes, il va préférer l'utilisation d'un order by en pipeline si c'est possible :

----------------------------------------------------------------
| Operation                     | Name           | Rows | Cost |
----------------------------------------------------------------
| SELECT STATEMENT              |                |   10 |    9 |
|  COUNT STOPKEY                |                |      |      |
|   VIEW                        |                |   10 |    9 |
|    TABLE ACCESS BY INDEX ROWID| VENTES         | 1004K|    9 |
|     INDEX FULL SCAN DESCENDING| VENTES_DATE_PR |   10 |    3 |
----------------------------------------------------------------

Le plan d'exécution Oracle indique la fin planifiée avec l'opération COUNT STOPKEY. La base de données a bien reconnu la requête top-N.

Utiliser la bonne syntaxe est seulement la moitié du travail car terminer efficacement l'exécution nécessite que les opérations précédentes soient exécutées en pipeline. Autrement dit, la clause order by doit être exécutée via un index, dans cet exemple l'index VENTE_DATE_PR sur VENTE_DATE et ID_PRODUIT. En utilisant cet index, la base de données peut éviter une opération explicite de tri et peut donc immédiatement envoyer les lignes lues de l'index à l'application. L'exécution est annulée après avoir récupéré dix lignes, donc la base de données ne lit pas plus de lignes que celles sélectionnées.

Si aucun index n'est disponible sur VENTE_DATE pour exécuter un order by en pipeline, la base de données doit lire et trier la table entière. La première ligne n'est renvoyée qu'après avoir lu la dernière ligne de la table.

---------------------------------------------------
| Operation               | Name   | Rows |  Cost |
---------------------------------------------------
| SELECT STATEMENT        |        |   10 | 59558 |
|  COUNT STOPKEY          |        |      |       |
|   VIEW                  |        | 1004K| 59558 |
|    SORT ORDER BY STOPKEY|        | 1004K| 59558 |
|     TABLE ACCESS FULL   | VENTES | 1004K|  9246 |
---------------------------------------------------

Ce plan d'exécution n'a pas d'order by en pipeline et est aussi lent que le client récupère toutes les lignes ou seulement les premières. Utiliser la syntaxe top-N est toujours préférable car la base de données n'a pas à matérialiser les résultats complets, seulement les dix premières lignes, ce qui nécessite bien moins de mémoire. Le plan d'exécution Oracle indique cette optimisation avec le modificateur STOPKEY sur l'opération SORT ORDER BY.

Les avantages d'une requête top-N en pipeline incluent non seulement des gains immédiats en performance mais aussi une scalabilité améliorée. Sans utiliser une exécution en pipeline, le temps de réponse de cette requête top-N grossit avec la taille de la table. Le temps de réponse lors de l'utilisation d'une exécution grossit seulement avec le nombre de lignes sélectionnées. En d'autres termes, le temps de réponse d'une requête top-N en pipeline est toujours le même. Il est totalement indépendant de la taille de la table. Quand la profondeur du B-tree grossit, la requête peut cependant devenir un peu plus lente.

La Figure 7.1 montre la scalabilité des deux variantes suivant un volume de données grossissant. Le temps de réponse linéaire des deux variantes pour une exécution sans order by en pipeline est clairement visible. Le temps de réponse pour une exécution en pipeline reste constant.

Figure 7.1 Scalabilité des requêtes Top-N

Bien que le temps de réponse d'une requête top-N en pipeline ne dépende pas de la taille de la table, il grossit toujours avec le nombre de lignes sélectionnées. Du coup, le temps de réponse double si vous sélectionnez deux fois plus de lignes. Ceci est particulièrement significatif lors de la pagination de requêtes qui chargent des résultats supplémentaires car ces requêtes commencent souvent à la première entrée ; elles liront les lignes déjà montrées sur la page précédente et les ignoreront jusqu'à atteindre les résultats de la seconde page. Néanmoins, il existe aussi une solution à ce problème, comme nous le verrons dans la section suivante.