par Guillaume Lelarge.

Indexer un tri


Les requêtes SQL disposant d'une clause order by n'ont pas besoin de trier les résultats explicitement si l'index adéquat renvoie déjà les lignes dans l'ordre requis. Cela signifie que le même index peut être utilisé pour la clause where et pour la clause order by.

Prenons comme exemple la requête suivante qui sélectionne les ventes d'hier ordonnées par la date de la vente et l'identifiant du produit :

SELECT date_vente, id_produit, quantite
  FROM ventes
 WHERE date_vente = TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY date_vente, id_produit;

Il existe déjà un index sur DATE_VENTE qui peut être utilisé pour la clause where. Néanmoins, la base de données doit réaliser une opération de tri explicite pour satisfaire la clause order by :

---------------------------------------------------------------
|Id | Operation                    | Name       | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT             |            |  320 |   18 |
| 1 |  SORT ORDER BY               |            |  320 |   18 |
| 2 |   TABLE ACCESS BY INDEX ROWID| VENTES     |  320 |   17 |
|*3 |    INDEX RANGE SCAN          | DATE_VENTE |  320 |    3 |
---------------------------------------------------------------

Un INDEX RANGE SCAN renvoie les lignes dans l'ordre de l'index de toute façon. Pour maximiser cet avantage, nous avons juste besoin d'étendre la définition de l'index pour qu'il corresponde à la clause de l'order by :

  DROP INDEX date_ventes;
CREATE INDEX date_ventes_pr ON ventes (date_vente, id_produit);

SELECT date_vente, id_produit, quantite
  FROM ventes
 WHERE date_vente = TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY date_vente, id_produit;

------------------------------------------------------------------
|Id | Operation                   | Name           | Rows | Cost |
------------------------------------------------------------------
| 0 | SELECT STATEMENT            |                |  320 |  300 |
| 1 |  TABLE ACCESS BY INDEX ROWID| VENTES         |  320 |  300 |
|*2 |   INDEX RANGE SCAN          | DATE_VENTES_PR |  320 |    4 |
------------------------------------------------------------------

L'opération de tri SORT ORDER BY a disparu du plan d'exécution même si la requête a toujours une clause order by. La base de données exploite l'ordre de l'index et n'a plus besoin d'une opération de tri explicite.

Important

Si l'ordre de l'index correspond à la clause order by, la base de données peut omettre l'opération de tri explicite.

Même si le nouveau plan d'exécution contient moins d'opérations, le coût a augmenté considérablement parce que le facteur de regroupement du nouvel index est bien pire (voir « Facteur de regroupement automatiquement optimisé »). Il faut simplement noter que le coût n'est pas toujours un bon indicateur de l'effort à l'exécution.

Facteur de regroupement automatiquement optimisé

La base de données Oracle conserve le facteur de regroupement à un minimum en se basant sur le ROWID pour l'ordre de l'index. Quand deux entrées d'index ont les mêmes valeurs de clé, le ROWID décide de l'ordre final. Du coup, l'index est aussi ordonné suivant l'ordre de la table et a le facteur de regroupement le plus petit possible car le ROWID représente l'adresse physique de la ligne de la table.

En ajoutant une autre colonne à un index, vous insérez un nouveau critère de tri avant le ROWID. La base de données a moins de liberté pour aligner les entrées de l'index suivant l'ordre de la table, donc le facteur de regroupement de l'index peut seulement empirer.

Quoiqu'il en soit, il est toujours possible que l'ordre de l'index corresponde grossièrement à l'ordre de la table. Les ventes d'un jour sont probablement toujours regroupées dans la table ainsi que dans l'index, même si leur séquence n'est plus exactement identique. La base de données doit lire les blocs de la table plusieurs fois lors de l'utilisation de l'index DATE_VENTE_PR mais ce sont les mêmes blocs qu'avant. Grâce à l'utilisation d'un cache pour les données fréquemment accédées, l'impact sur les performances pourrait être bien moins que celui indiqué par les coûts estimés.

Pour cette optimisation, il est suffisant que l'intervalle parcouru de l'index soit trié suivant la clause order by. Du coup, l'optimisation fonctionne aussi pour cet exemple particulier lors du tri de ID_PRODUIT seul :

SELECT date_vente, id_produit, quantite
  FROM ventes
 WHERE date_vente = TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY id_produit;

Dans la , nous voyons que la colonne ID_PRODUIT est le seul critère de tri dans l'intervalle parcouru de l'index. Du coup, l'ordre de l'index correspond à la clause order by dans cet intervalle d'index. La base de données peut donc omettre l'opération de tri.

Figure 6.1 Ordre de tri dans l'intervalle adéquat de l'index

Cette optimisation peut causer un comportement inattendu lors de l'agrandissement de l'intervalle parcouru de l'index :

SELECT date_vente, id_produit, quantite
  FROM ventes
 WHERE date_vente >= TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY id_produit;

Cette requête ne récupère pas les ventes d'hier mais toutes les ventes depuis hier. Cela signifie qu'elle couvre plusieurs jours et parcourt un intervalle qui n'est plus exclusivement trié par la colonne ID_PRODUIT. Si nous regardons encore la et étendons l'intervalle parcouru de l'index jusqu'au bout, nous voyons qu'il existe encore des valeurs plus petites de ID_PRODUIT. Du coup, la base de données doit utiliser une opération explicite de tri pour satisfaire la clause order by.

-----------------------------------------------------------------
|Id |Operation                    | Name          | Rows | Cost |
-----------------------------------------------------------------
| 0 |SELECT STATEMENT             |               |  320 |  301 |
| 1 | SORT ORDER BY               |               |  320 |  301 |
| 2 |  TABLE ACCESS BY INDEX ROWID| VENTES        |  320 |  300 |
|*3 |   INDEX RANGE SCAN          | DATE_VENTE_PR |  320 |    4 |
-----------------------------------------------------------------

Si la base de données utilise une opération de tri alors que vous attendiez une exécution en pipeline, cela peut avoir deux raisons : le plan d'exécution avec une opération de tri explicite a un meilleur coût ; l'ordre de l'index dans l'intervalle parcouru ne correspond pas à la clause order by.

Une façon simple de séparer les deux cas est d'utiliser la définition complète de l'index dans la clause order by, autrement dit en ajustant la requête d'après l'index pour éliminer la deuxième cause. Si la base de données utilise toujours une opération explicite de tri, l'optimiseur préfère le plan à cause de son coût : sinon la base de données ne peut pas utiliser l'index pour la clause order by originale.

Astuce

Utilisez la définition complète de l'index dans la clause order by pour trouver la raison d'une opération explicite de tri.

Dans les deux cas, vous pourriez vous demander si et comment il est possible d'avoir une exécution en pipeline d'un order by. Pour cela, vous pouvez exécuter la requête avec la définition complète de l'index dans la clause order by, puis vous inspectez le résultat. Vous réaliserez souvent que vous avez une mauvaise perception de l'index et que l'ordre de l'index n'est en fait pas requis par la clause originale de l'order by. La base de données ne peut donc pas utiliser l'index pour éviter une opération de tri.

Si l'optimiseur préfère une opération de tri explicite grâce à son coût, c'est généralement dû au fait que l'optimiseur prend le meilleur plan d'exécution pour une exécution complète de la requête. En d'autres termes, l'optimiseur choisit le plan d'exécution qui est le plus rapide pour obtenir la dernière ligne. Si la base de données détecte que l'application ne récupère que les quelques premières lignes, elle pourrait préférer exécuter l'order by avec un index. Le Chapitre 7, « Résultats partiels » explique les méthodes d'optimisation correspondantes.

À 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