PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 12.18 » Langage SQL » Index » Parcours d'index seul et index couvrants

11.9. Parcours d'index seul et index couvrants

Tous les index dans PostgreSQL sont des index secondaires, ceci signifiant que chaque index est stocké séparément des données de la table (ce qui est appelé le heap dans la terminologie PostgreSQL). Ceci signifie que, dans un parcours d'index habituel, chaque récupération de ligne nécessite de récupérer les données de l'index et du heap. De plus, bien que les entrées d'un index correspondant à une condition WHERE indexable soient habituellement proches dans l'index, les lignes de la table qu'elles référencent peuvent se trouver n'importe où dans le heap. La portion accédée du heap pendant un parcours d'index implique donc beaucoup d'accès aléatoires au heap, ce qui peut être lent, tout particulièrement sur les disques magnétiques traditionnels. (Comme décrit dans Section 11.5, les parcours de bitmap essaient de diminuer ce coût en réalisant les accès au heap de façon ordonnée, mais cette méthode a ses limites.)

Pour résoudre ce problème de performances, PostgreSQL supporte les parcours d'index seul, qui peuvent répondre aux requêtes à partir d'un index seul sans aucun accès au heap. L'idée de base est de renvoyer les valeurs directement à partir de chaque entrée dans l'index au lieu de consulter l'entrée associée dans le heap. Il existe deux restrictions fondamentales pour l'utilisation de cette méthode :

  1. Le type d'index doit supporter les parcours d'index seul. Les index B-tree peuvent toujours le faire. Les index GiST et SP-GiST supportent les parcours d'index seuls uniquement pour certaines classes d'opérateurs, mais pas pour les autres. D'autres types d'index n'ont aucun support. Le prérequis sous-jacent est que l'index doit enregistrer physiquement, ou être capable de reconstruire, les données originales pour chaque entrée d'index. En contre-exemple, les index GIN ne supportent pas les parcours d'index seul, car chaque entrée d'index contient typiquement seulement une partie de la valeur originale.

  2. La requête doit référencer seulement les colonnes enregistrées dans l'index. Par exemple, avec un index sur les colonnes x et y d'une table qui a aussi une colonne z, ces requêtes peuvent utiliser des parcours d'index seul :

    SELECT x, y FROM tab WHERE x = 'key';
    SELECT x FROM tab WHERE x = 'key' AND y < 42;
         

    alors que ces requêtes ne le peuvent pas :

    SELECT x, z FROM tab WHERE x = 'key';
    SELECT x FROM tab WHERE x = 'key' AND z < 42;
         

    (Les index fonctionnels et les index partiels compliquent cette règle, comme expliquée ci-dessous.)

Si ces deux prérequis fondamentaux sont rencontrés, alors toutes les valeurs requises par la requête sont disponibles dans l'index, donc un parcours d'index seul est physiquement possible. Mais il existe un prérequis supplémentaire pour tout parcours de table dans PostgreSQL : il doit vérifier que chaque ligne récupérée est « visible » dans le cadre du snapshot MVCC de la requête, comme indiqué dans Chapitre 13. Les informations de visibilité ne sont pas enregistrées dans les entrées de l'index, uniquement dans les entrées de la table. Donc a priori, cela voudrait dire que chaque récupération de ligne nécessite un accès au heap de la table. Et c'est bien le cas si la ligne de la table a été modifiée récemment. Néanmoins, pour les données changeant peu, il y a toujours un moyen de contourner ce problème. PostgreSQL trace pour chaque page dans le heap de la table, si toutes les lignes enregistrées dans cette page sont suffisamment anciennes pour être visibles par toutes les transactions en cours et futures. Cette information est enregistrée dans un bit de la carte de visibilité de la table. Un parcours d'index seul, pour trouver une entrée d'index candidate, vérifie le bit de la carte de visibilité pour la page correspondante du heap. Si ce bit est vrai, la ligne est connue comme étant visible et donc la donnée peut être renvoyée sans plus de tests. Dans le cas contraire, l'entrée heap doit être visitée pour trouver si elle est visible, donc aucune amélioration des performances n'est obtenue par rapport à un parcours d'index standard. Même dans le cas d'une réussite, cette approche remplace des accès au heap par des accès à la carte de visibilité. Comme la carte de visibilité est quatre fois plus petite que le heap qu'elle décrit, moins d'accès IO sont nécessaires pour accéder à l'information. Dans la plupart des cas, la carte de visibilité reste en mémoire tout le temps.

En bref, quand un parcours d'index seul est possible d'après les deux prérequis fondamentaux, son utilisation ne sera réellement intéressante que si une faction significative des blocs du heap de la table ont leur bit all-visible configuré. Mais les tables dont une large fraction des lignes ne changent pas sont habituellement suffisantes pour que ce type de parcours se révèle très utile en pratique.

Pour une utilisation efficace de la fonctionnalité du parcours d'index seul, vous pourriez choisir de créer un index couvrant, qui est un index conçu spécifiquement pour inclure les colonnes nécessaires pour un type particulier de requêtes que vous exécutez fréquemment. Comme les requêtes ont typiquement besoin de récupérer plus de colonnes que de colonnes incluses dans la recherche, PostgreSQL vous permet de créer un index pour lequel certaines colonnes ne sont qu'une « charge » et ne peuvent pas faire partie de la recherche. Ceci se fait en ajoutant la clause INCLUDE avec la liste des colonnes supplémentaires. Par exemple, si vous exécutez fréquemment des requêtes comme :

SELECT y FROM tab WHERE x = 'key';
  

l'approche habituelle pour accélérer de telles requêtes est de créer un index uniquement sur x. Néanmoins, un index défini comme

CREATE INDEX tab_x_y ON tab(x) INCLUDE (y);
  

peut gérer ces requêtes sous la forme de parcours d'index seul, car les valeurs de y peuvent être obtenues de l'index sans visiter la table.

Comme la colonne y ne fait pas partie des clés de recherche de l'index, elle n'a pas besoin d'être d'un type de donnée que l'index peut gérer ; la valeur est simplement enregistrée dans l'index et n'est pas interprétée par la machinerie de l'index. De plus, si l'index est un index unique, autrement dit

CREATE UNIQUE INDEX tab_x_y ON tab(x) INCLUDE (y);
  

la condition d'unicité s'applique uniquement à la colonne x, et non pas à la combinaison x et y. (Une clause INCLUDE peut aussi être écrite dans les contraintes UNIQUE et PRIMARY KEY, fournissant une syntaxe alternative pour configurer ce type d'index.)

Il est conseillé d'être conservateur sur l'ajout de colonnes non-clés dans un index, tout spécialement les colonnes volumineuses. Si un enregistrement d'index dépasse la taille maximale autorisée pour ce type d'index, l'insertion de données échouera. Dans tous les cas, les colonnes non-clés dupliquent les données de la table et augmentent la taille de l'index, ce qui peut ralentir les recherches. Et rappelez-vous qu'il y a peu d'intérêt d'inclure des colonnes non-clés dans un index, sauf si la table change très doucement pour qu'un parcours d'index seul n'ait pas besoin d'accéder à la table. Si la ligne de la table doit être visitée, cela ne coûte rien de récupérer la valeur de la colonne dans la table. Les autres restrictions sont que les expressions ne sont actuellement pas supportées dans les colonnes incluses, et que seuls les index B-tree et GiST supportent actuellement les colonnes incluses.

Avant que PostgreSQL ne dispose de la fonctionnalité INCLUDE, les utilisateurs créaient parfois des index couvrants en ajoutant les colonnes non-clés comme des colonnes d'index habituels, par exemple

CREATE INDEX tab_x_y ON tab(x, y);
  

même s'ils n'avaient jamais l'intention d'utiliser y comme partie de la clause WHERE. Ceci fonctionne bien tant que les colonnes supplémentaires sont les dernières colonnes ; il est déconseillé de les ajouter comme premières colonnes pour les raisons expliquées dans Section 11.3. Néanmoins, cette méthode ne supporte pas le cas où vous voulez que l'index assure l'unicité des colonnes clés.

La troncature de suffixe supprime toujours les colonnes non-clé des niveaux supérieurs du B-Tree. En tant que colonnes de charge utile, elles ne sont jamais utilisées pour guider des parcours d'index. Le processus de troncature supprime également une ou plusieurs colonne(s) clé quand le reste du préfixe de colonnes(s) se montre suffisant pour décrire les tuples du plus bas niveau de B-Tree. Dans la pratique, les index couvrants sans clause INCLUDE évitent souvent de stocker les colonnes qui sont de la charge utile effective dans les niveaux supérieurs. Cependant, définir explicitement les colonnes de charge utile comme colonnes non-clé permet de conserver des tuples de petite taille dans les niveaux supérieurs de manière fiable.

En principe, les parcours d'index seul peuvent être utilisés avec des index fonctionnels. Par exemple, avec un index sur f(x)x est une colonne de table, il est possible de l'utiliser avec la requête suivante :

SELECT f(x) FROM tab WHERE f(x) < 1;
  

pour un parcours d'index seul ; et c'est très intéressant si f() est une fonction coûteuse à l'exécution. Néanmoins, l'optimiseur de PostgreSQL n'est pas très intelligent actuellement avec de tels cas. Il considère qu'une requête est réalisable avec un parcours d'index seul uniquement quand toutes les colonnes nécessaires pour la requête sont disponibles à partir de l'index. Dans cet exemple, x n'est pas nécessaire, sauf dans le contexte f(x), mais le planificateur ne le remarque pas et conclut qu'un parcours d'index seul n'est pas possible. Si un parcours d'index seul semble suffisamment intéressant, ceci peut être contourné en ajoutant x comme colonne incluse, par exemple

CREATE INDEX tab_f_x ON tab (f(x)) INCLUDE (x);
  

Si le but est d'éviter de recalculer f(x), une autre astuce est que l'optimiseur ne fera pas forcément une correspondance entre les utilisations de f(x) qui ne sont pas dans les clauses WHERE indexables et la colonne de l'index. Généralement, le test sera efficace pour les requêtes simples comme indiquées ci-dessus, mais pas pour les requêtes qui impliquent des jointures. Ces déficiences pourraient être corrigées dans les versions futures de PostgreSQL.

Les index partiels ont aussi des interactions intéressantes avec les parcours d'index seul. Considérez l'index partiel indiqué dans Exemple 11.3 :

CREATE UNIQUE INDEX tests_success_constraint ON tests (subject, target)
    WHERE success;
  

En principe, nous pouvons faire un parcours d'index seul sur cet index pour satisfaire une requête du type :

SELECT target FROM tests WHERE subject = 'some-subject' AND success;
  

Mais il reste un problème : la clause WHERE fait référence à success qui n'est pas disponible comme colonne de résultat de l'index. Néanmoins, un parcours d'index seul est possible parce que le plan n'a pas besoin de vérifier de nouveau cette partie de la clause WHERE à l'exécution : toutes les entrées trouvées dans l'index ont obligatoirement success = true, donc il n'est pas nécessaire de le vérifier explicitement dans le plan. Les versions 9.6 et ultérieures de PostgreSQL reconnaîtront de tels cas et permettront aux parcours d'index seul d'être générés, mais les anciennes versions ne le pourront pas.