PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 12.18 » Langage SQL » Index » Index et ORDER BY

11.4. Index et ORDER BY

Au-delà du simple fait de trouver les lignes à renvoyer à une requête, un index peut les renvoyer dans un ordre spécifique. Cela permet de résoudre une clause ORDER BY sans étape de tri séparée. De tous les types d'index actuellement supportés par PostgreSQL, seuls les B-tree peuvent produire une sortie triée -- les autres types d'index renvoient les lignes correspondantes dans un ordre imprécis, dépendant de l'implantation.

Le planificateur répond à une clause ORDER BY soit en parcourant un index disponible qui correspond à la clause, soit en parcourant la table dans l'ordre physique et en réalisant un tri explicite. Pour une requête qui nécessite de parcourir une fraction importante de la table, le tri explicite est probablement plus rapide que le parcours d'un index, car il nécessite moins d'entrées/sorties disque, du fait de son accès séquentiel. Les index sont plus utiles lorsqu'il s'agit de ne récupérer que quelques lignes. ORDER BY combiné à LIMIT n est un cas spécial très important : un tri explicite doit traiter toutes les données pour identifier les n premières lignes, mais s'il y a un index qui correspond à l'ORDER BY, alors les n premières lignes peuvent être récupérées directement sans qu'il soit nécessaire de parcourir les autres.

Par défaut, les index B-tree stockent leurs entrées dans l'ordre ascendant, valeurs NULL en dernier (le TID de la table est traité comme une colonne de départage pour les entrées qui, sans quoi, seraient identiques). Cela signifie que le parcours avant d'un index sur une colonne x produit une sortie satisfaisant ORDER BY x (ou en plus verbeux ORDER BY x ASC NULLS LAST). L'index peut aussi être parcouru en arrière, produisant ainsi une sortie satisfaisant un ORDER BY x DESC (ou en plus verbeux ORDER BY x DESC NULLS FIRST, car NULLS FIRST est la valeur par défaut pour un ORDER BY DESC).

L'ordre d'un index B-tree peut être défini à la création par l'inclusion des options ASC, DESC, NULLS FIRST, et/ou NULLS LAST lors de la création de l'index ; par exemple :

CREATE INDEX test2_info_nulls_low ON test2 (info NULLS FIRST);
CREATE INDEX test3_desc_index ON test3 (id DESC NULLS LAST);
   

Un index stocké en ordre ascendant avec les valeurs NULL en premier peut satisfaire soit ORDER BY x ASC NULLS FIRST, soit ORDER BY x DESC NULLS LAST selon la direction du parcours.

On peut s'interroger sur l'intérêt de proposer quatre options, alors que deux options associées à la possibilité d'un parcours inverse semblent suffire à couvrir toutes les variantes d'ORDER BY. Dans les index monocolonnes, les options sont en effet redondantes, mais pour un index à plusieurs colonnes, elles sont utiles. Si l'on considère un index à deux colonnes (x, y), il peut satisfaire une clause ORDER BY x, y sur un parcours avant, ou ORDER BY x DESC, y DESC sur un parcours inverse. Mais il se peut que l'application utilise fréquemment ORDER BY x ASC, y DESC. Il n'y a pas moyen d'obtenir cet ordre à partir d'un index plus simple, mais c'est possible si l'index est défini comme (x ASC, y DESC) or (x DESC, y ASC).

Les index d'ordre différent de celui par défaut sont visiblement une fonctionnalité très spécialisée, mais ils peuvent parfois être à l'origine d'accélérations spectaculaires des performances sur certaines requêtes. L'intérêt de maintenir un tel index dépend de la fréquence des requêtes qui nécessitent un tri particulier.