par Guillaume Lelarge.

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.

Astuce

Informez la base de données quand vous n'avez pas besoin de toutes les lignes.

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.

MySQL

MySQL et PostgreSQL utilisent la clause limit pour restreindre le nombre de lignes à récupérer.

SELECT *
  FROM ventes
 ORDER BY date_vente DESC
 LIMIT 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. Pour utiliser cette colonne dans un filtre, nous devons englober la requête :

SELECT *
  FROM (
       SELECT *
         FROM ventes
        ORDER BY date_vente DESC
       )
 WHERE rownum <= 10;
PostgreSQL

PostgreSQL supporte l'extension fetch first depuis la version 8.4. La clause limit précédemment utilisée fonctionne aussi comme indiqué dans l'exemple pour MySQL.

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

SQL Server fournit la clause top pour restreindre le nombre de lignes à récupérer.

SELECT TOP 10 *
  FROM ventes
 ORDER BY date_vente DESC;

À partir de la version 2012, SQL Server supporte aussi l'extension fetch first.

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.

Important

La base de données peut optimiser une requête pour un résultat partiel uniquement si elle le sait dès le départ.

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.

Astuce

L'Annexe A, « Plans d'exécution » résume les opérations correspon­dantes pour DB2, MySQL, Oracle, PostgreSQL et SQL Server.

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.

Important

Une requête top-N en pipeline n'a pas besoin de lire et trier l'ensemble complet des résultats.

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.

À propos de l'auteur

Photo de Markus Winand

Markus Winand teaches efficient SQL—inhouse and online. He minimizes the development time using modern SQL and optimizes the runtime with smart indexing—for that he also published the book SQL Performance Explained.

Livre de Markus

Couverture du livre « SQL : Au cœur des performances »

L'essence de SQL tuning dans 200 pages.

Acheter de Markus
(Livre de poche et PDF)

Achetez chez Amazon
(Seulement en poche)

“Use The Index, Luke!” by Markus Winand and translated by Guillaume Lelarge is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Mentions légales | Contact | NO WARRANTY | Marque déposée | Privacy | CC-BY-NC-ND 3.0 license