Parcours d’index seul, indexation couvrante

(sujet préalablement traité avec la version 9.6)

Yggdrasil peut-il suffire ?

      Chaque SGBD dispose d'un optimiseur ou planner lui permettant de déterminer comme exécuter votre requête. Ce n'est pas parce qu'un index peut être utilisé qu'il le sera. Le choix est basé sur une estimation de coût et le but est bien sûr d'améliorer les temps de réponse.
      Les optimiseurs d'Oracle et PostgreSQL savent au moment de faire le choix de passer par un index si un critère élimine beaucoup de lignes ou non. Mais ces SGBD ne se limitent pas à la sélectivité. Ils utilisent en plus ce qu'Oracle définit comme le clustering factor et PostgreSQL comme la corrélation. Cela leur permet de déterminer plus précisément le coût de lecture lors de l'exécution si un index est utilisé.
      Il existe cependant un cas où l'index est plus souvent bénéfique même si la sélectivité est médiocre. Si toutes les données à retourner sont dans l'index alors il peut permettre de ne pas lire du tout les données de la table.
      Le terme employé par PostgreSQL est Index Only Scan, parcours d'index seul. Les Index Only Scan ont été introduits avec la version 9.2 ce qui signifie que TOUTES les versions supportées de PostgreSQL en sont capables en 2018.
      Démonstration avec PostgreSQL 11 devel :

select version(); version --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PostgreSQL 11devel (Ubuntu 11~~devel~20180418.1031-1~571.gitfe7fc52.pgdg16.04+1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609, 64-bit (1 ligne) CREATE EXTENSION IF NOT EXISTS "uuid-ossp" schema extensions; CREATE EXTENSION create table geants( idu uuid, dtn date, genre char(1), taille smallint, masse smallint, actif boolean, devise varchar(128), pw smallint, heureux boolean, couleur varchar(8), veteran boolean, clan smallint, gabarit varchar(8), revenu integer, pm smallint, berserk boolean, tutelaire smallint, ere varchar(10), cyclope boolean); CREATE TABLE WITH serie(i) AS (SELECT generate_series(55000000,1,-1)) insert into geants select uuid_generate_v4(), current_date - (ceil(i/3) || ' minutes')::interval + (trunc(random() * 100 + 1) || ' days')::interval, case when random() < 0.45 then 'M' else 'F' end, 200 + (trunc(random() * 200 + 1)), 300 + (trunc(random() * 200 + 1)), case when random() < 0.7 then false else true end, upper(md5(random()::text)), (trunc(random()*100 + 1)), case when random() < 0.1 then false else true end, case when random() < 0.7 then 'GRIS' when random() < 0.8 then 'NOIR' else 'BLEU' end, case when random() < 0.9 then false else true end, (trunc(random()*1000 + 1)), case when random() < 0.1 then 'PETIT' when random() < 0.9 then 'MOYEN' else 'GRAND' end, (trunc(random()*1000000 + 1)), (trunc(random()*10 + 1)), case when random() < 0.01 then true else false end, (trunc(random()*10 + 1)), case when i < 18000000 then 'TAUREAU' when i < 40000000 then 'LICORNE' else 'DRAGON' end, case when random() < 0.001 then true else false end from serie; INSERT 0 55000000 \d+ Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description ----------+--------+-------+--------------+---------+------------- postgres | geants | table | postgres | 7046 MB | (1 ligne) CREATE INDEX geants_i1 ON geants(genre, dtn); CREATE INDEX \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description ----------+-----------+-------+--------------+--------+---------+------------- postgres | geants_i1 | index | postgres | geants | 1178 MB | (1 ligne) explain SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; QUERY PLAN ------------------------------------------------------------------------------------------------------------------ Gather (cost=17509.88..1346678.18 rows=695946 width=33) Workers Planned: 2 -> Parallel Bitmap Heap Scan on geants (cost=16509.88..1276083.58 rows=289978 width=33) Recheck Cond: ((genre = 'M'::bpchar) AND (dtn >= '1988-01-01'::date) AND (dtn < '1989-01-01'::date)) -> Bitmap Index Scan on geants_i1 (cost=0.00..16335.89 rows=695946 width=0) Index Cond: ((genre = 'M'::bpchar) AND (dtn >= '1988-01-01'::date) AND (dtn < '1989-01-01'::date)) JIT: Functions: 4 Inlining: true Optimization: true (10 lignes) \timing SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; Temps : 386,342 ms ... Temps : 346,768 ms ... Temps : 350,073 ms drop index geants_i1; DROP INDEX CREATE INDEX geants_i1 ON geants(genre, dtn, devise); CREATE INDEX \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description ----------+-----------+-------+--------------+--------+---------+------------- postgres | geants_i1 | index | postgres | geants | 3560 MB | (1 ligne) explain SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; QUERY PLAN ------------------------------------------------------------------------------------------------------------------ Gather (cost=32937.86..1362105.77 rows=695945 width=33) Workers Planned: 2 -> Parallel Bitmap Heap Scan on geants (cost=31937.86..1291511.27 rows=289977 width=33) Recheck Cond: ((genre = 'M'::bpchar) AND (dtn >= '1988-01-01'::date) AND (dtn < '1989-01-01'::date)) -> Bitmap Index Scan on geants_i1 (cost=0.00..31763.88 rows=695945 width=0) Index Cond: ((genre = 'M'::bpchar) AND (dtn >= '1988-01-01'::date) AND (dtn < '1989-01-01'::date)) JIT: Functions: 4 Inlining: true Optimization: true

      Ouille, les conditions semblent réunies pour un parcours d'index seul et pourtant le plan d'exécution ne change pas après la création de l'index composé.
      En fait cette situation est liée au fonctionnement de PostgreSQL (MVCC) et à la nature artificielle de mon test. Dans la réalité la table aurait vécu, reçu des AUTOVACUUM etc. Nous allons procéder à un VACUUUM (attention pas un VACUUM FULL !), ce que je vous conseille après un chargement massif décisionnel par exemple, et relancer la requête :

vacuum geants; VACUUM explain SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; QUERY PLAN ------------------------------------------------------------------------------------------------------ Index Only Scan using geants_i1 on geants (cost=0.56..38723.33 rows=695945 width=33) Index Cond: ((genre = 'M'::bpchar) AND (dtn >= '1988-01-01'::date) AND (dtn < '1989-01-01'::date)) (2 lignes) SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; Temps : 256,704 ms ... Temps : 228,816 ms ... Temps : 223,746 ms

      Pas de "heap fetches" (retours vers la table) nécessaires après le VACUUM. Le temps de réponse est meilleur que celui obtenu initialement alors que le parallélisme n'est pas utilisé et que la consommation de ressources est moindre.

      Lors de mes tests sommaires avec SQL Server, j'ai constaté qu'avec ce SGBD seule la sélectivité compte lorsqu'il s'agit de déterminer si un index doit être utilisé. L'optimiseur est donc logiquement bien plus conservateur lorsque la sélectivité n'est pas excellente...sauf bien sûr dans le cas où un Index Only Scan est possible.
      SQL Server a introduit la possibilité de stocker dans les index les données de colonnes ne participant pas à l'index au lieu d'avoir un simple pointeur vers la table. Dans la terminologie SQL Server, l'index devient alors couvrant. Il ne faut tout de même pas en abuser. Le risque en recopiant N fois la table au niveau de N index est bien sûr d'occasionner une pénalité au niveau des écritures. La RAM n'est pas non extensible à l'infini, il faut bien monter ces pages d'index en cache lorsqu'elles sont lues et cette approche peut au final également pénaliser les lectures.
      PostgreSQL dispose des index couvrants depuis la version 11 via le mot clé INCLUDE. Démonstration :

drop index geants_i1; DROP INDEX CREATE INDEX geants_i1 ON geants(genre, dtn) INCLUDE (devise); CREATE INDEX \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description ----------+-----------+-------+--------------+--------+---------+------------- postgres | geants_i1 | index | postgres | geants | 3535 MB | (1 ligne) explain SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; QUERY PLAN ------------------------------------------------------------------------------------------------------ Index Only Scan using geants_i1 on geants (cost=0.56..38559.33 rows=695945 width=33) Index Cond: ((genre = 'M'::bpchar) AND (dtn >= '1988-01-01'::date) AND (dtn < '1989-01-01'::date)) (2 lignes) SELECT devise FROM geants WHERE dtn >= date '1988-01-01' and dtn < date '1989-01-01' and genre = 'M'; Temps : 226,258 ms ... Temps : 202,840 ms ... Temps : 217,331 ms

      L'index est (très légèrement) plus petit et les performances sont (très légèrement) meilleures que celles obtenues avec un index composé classique.
      INCLUDE n'ajoute pas une fonctionnalité essentielle mais, si vous êtes certains qu'une ou plusieurs colonnes apparaissent dans les clauses de projection (SELECT) mais jamais dans les clauses de restriction (WHERE) ET qu'il y a un bénéfice important à réaliser un Index Only Scan alors vous pouvez prendre en compte ces colonnes supplémentaires via la clause INCLUDE plutôt que de créer un index composé classique. Petite caractéristique intéressante qui n'est pas présentée dans l'exemple : si l'index est unique, la contrainte ne concerne pas les colonnes ajoutées via INCLUDE.
      Les réserves déjà émises s'appliquent évidemment, n'oubliez pas le coût de maintenance des index et le fait que la mémoire vive n'est pas infinie. Si les requêtes sont variées, recopier les tables dans chaque index composé n'est probablement PAS la bonne approche !

Mise à jour : 18/04/2018