par Guillaume Lelarge.

Indexer le « Group By »


Les bases de données SQL utilisent deux algorithmes entièrement différents pour le group by. Le premier, un algorithme de hachage, agrège les enregis­trements en entrée dans une table de hachage temporaire. Une fois tous les enregistrements en entrée traitées, la table de hachage est renvoyée comme résultat. Le deuxième algorithme, l'algorithme de tri/groupe, trie en premier lieu les données en entrée en suivant la clé de groupement pour que les lignes de chaque groupe se suivent les unes les autres en une succession immédiate. Après cela, la base de données a juste besoin de les regrouper. En général, les deux algorithmes ont besoin de matérialiser un état intermédiaire, donc elles ne sont pas exécutées via un pipeline. Néanmoins, l'algorithme de tri/groupe peut utiliser un index pour éviter l'opération de tri, et du coup activer l'exécution du group by en pipeline.

Remarque

MySQL 5.6 n'utilise pas l'algorithme de hachage. Néanmoins, l'optimisation pour l'algorithme tri/groupe fonctionne comme décrit ci-dessus.

Considérez la requête suivante. Elle renvoie les revenus d'hier groupés par ID_PRODUIT :

SELECT id_produit, sum(valeur_eur)
  FROM ventes
 WHERE date_vente = TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY id_produit;

En connaissant l'index sur DATE_VENTE et ID_PRODUIT de la section précé­dente, l'algorithme de tri/groupe est plus approprié car un INDEX RANGE SCAN renvoie automatiquement les lignes dans l'ordre requis. Ceci signifie que la base de données évite la matérialisation car elle n'a pas besoin d'une opération explicite de tri. Le group by est exécuté en pipeline.

------------------------------------------------------------------
|Id |Operation                    | Name           | Rows | Cost |
------------------------------------------------------------------
| 0 |SELECT STATEMENT             |                |   17 |  192 |
| 1 | SORT GROUP BY NOSORT        |                |   17 |  192 |
| 2 |  TABLE ACCESS BY INDEX ROWID| VENTES         |  321 |  192 |
|*3 |   INDEX RANGE SCAN          | DATE_VENTES_PR |  321 |    3 |
------------------------------------------------------------------

Le plan d'exécution de la base de données Oracle marque une opération SORT GROUP BY en pipeline avec le mot-clé NOSORT. Le plan d'exécution des autres bases de données ne mentionne pas du tout les opérations de tri.

Le group by en pipeline a les mêmes prérequis que le order by en pipeline, sauf qu'il n'y a aucun modificateur ASC et DESC. Cela signifie que définir un index avec les modificateurs ASC/DESC ne devrait pas affecter l'exécution en pipeline d'un group by. C'est aussi vrai pour NULLS FIRST/LAST. Cependant, certaines bases de données ne peuvent pas utiliser correctement un index ASC/DESC pour un group by exécuté en pipeline.

Attention

Pour PostgreSQL, vous devez ajouter une clause order by pour qu'un index avec un tri NULLS LAST puisse être utilisé avec un group by dans un pipeline.

La base de données Oracle ne peut pas lire un index à l'envers pour exécuter un group by dans un pipeline s'il est suivi par un order by.

Plus de détails sont disponibles dans les annexes respectives : PostgreSQL, Oracle.

Si nous étendons la requête pour qu'elle considère toutes les ventes depuis hier, comme nous l'avions fait dans l'exemple sur l'order by en pipeline, cela empêche le group by en pipeline pour la même raison que précédemment : le INDEX RANGE SCAN ne fournit pas les lignes triées par la clé de regroupement (comparez à la Figure 6.1).

SELECT id_produit, sum(valeur_eur)
  FROM ventes
 WHERE date_vente >= TRUNC(sysdate) - INTERVAL '1' DAY
 GROUP BY id_produit;
-----------------------------------------------------------------
|Id |Operation                    | Name          | Rows | Cost |
-----------------------------------------------------------------
| 0 |SELECT STATEMENT             |               |   24 |  356 |
| 1 | HASH GROUP BY               |               |   24 |  356 |
| 2 |  TABLE ACCESS BY INDEX ROWID| VENTES        |  596 |  355 |
|*3 |   INDEX RANGE SCAN          | DATE_VENTE_PR |  596 |    4 |
-----------------------------------------------------------------

À la place, la base de données Oracle utilise l'algorithme de hachage. L'avantage de cet algorithme est qu'il est seulement nécessaire de mettre en cache le résultat agrégé alors que l'algorithme de tri/groupe matérialise l'ensemble complet en entrée. En d'autres termes, l'algorithme de hachage a besoin de moins de mémoire.

Comme avec un order by exécuté en pipeline, une exécution rapide n'est pas l'aspect le plus important d'une exécution group by en pipeline. Il est plus important que la base de données l'exécute via un pipeline et renvoie les premiers résultats avant de lire l'entrée en entier. C'est la condition pour les méthodes d'optimisation avancées expliquées dans le prochain chapitre.

Astuce

Pouvez-vous trouver d'autres opérations des bases de données (en dehors du tri et des groupes) pouvant utiliser un index pour éviter un tri ?

À 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