Indexation couvrante ou parcours d’index seul

(sujet préalablement traité avec la version 11 devel)

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é.
      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.
      Il existe cependant un cas où il est plus évident que l’index peut être 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. SQL Server a particulièrement besoin de cette caractéristique. Avec ce SGBD vous pouvez ainsi stocker dans les index les données de colonnes ne participant pas à l’index au lieu d’avoir un simple pointeur vers la table, l’index devient alors "couvrant". Je ne suis pas spécialiste SQL Server mais j’imagine qu’il ne faut tout de même pas en abuser. Le risque pourrait être de recopier N fois la table au niveau des N index avec une pénalité au niveau des écritures, sans compter le fait que la RAM n’est pas extensible à l’infini et qu’il faut bien monter ces pages d’index en cache lorsqu’elles sont lues.
      Le terme d’index couvrant n’est pas employé avec Oracle et PostgreSQL. Mais ces SGBD sont capables de ne pas accéder à la table lorsque ce n’est pas nécessaire. Etre couvrant n’est pas une propriété liée à l’index mais une capacité à l’exécution. Le terme employé par PostgreSQL est Index Only Scan. 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 2017. Démonstration avec PostgreSQL 9.6 :

select version(); version --------------------------------------------------------------------------------------------------- PostgreSQL 9.6.2 on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-10) 6.3.0 20170321, 64-bit (1 ligne) 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 CREATE EXTENSION IF NOT EXISTS "uuid-ossp"; CREATE EXTENSION WITH serie(i) AS (SELECT generate_series(5500000,100001,-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 5400000 explain analyze SELECT min(taille) FROM geants WHERE revenu > 900000; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------- Aggregate (cost=157394.09..157394.10 rows=1 width=2) (actual time=951.231..951.232 rows=1 loops=1) -> Seq Scan on geants (cost=0.00..156024.39 rows=547882 width=2) (actual time=0.030..899.684 rows=540630 loops=1) Filter: (revenu > 900000) Rows Removed by Filter: 4859370 Planning time: 0.095 ms Execution time: 951.260 ms ... Execution time: 927.213 ms ... Execution time: 922.205 ms CREATE INDEX geants_i1 ON geants(revenu); CREATE INDEX set random_page_cost=1; SET explain analyze SELECT min(taille) FROM geants WHERE revenu > 900000; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=100986.14..100986.15 rows=1 width=2) (actual time=948.433..948.433 rows=1 loops=1) -> Index Scan using geants_i1 on geants (cost=0.43..99616.43 rows=547887 width=2) (actual time=0.024..880.076 rows=540630 loops=1) Index Cond: (revenu > 900000) Planning time: 0.447 ms Execution time: 948.463 ms ... Execution time: 1033.361 ms ... Execution time: 968.837 ms DROP INDEX geants_i1; DROP INDEX CREATE INDEX geants_i1 ON geants(revenu, taille); CREATE INDEX explain analyze SELECT min(taille) FROM geants WHERE revenu > 900000; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=100986.16..100986.17 rows=1 width=2) (actual time=934.078..934.078 rows=1 loops=1) -> Index Only Scan using geants_i1 on geants (cost=0.43..99616.44 rows=547887 width=2) (actual time=0.030..879.464 rows=540630 loops=1) Index Cond: (revenu > 900000) Heap Fetches: 540630 Planning time: 0.190 ms Execution time: 934.101 ms ... Execution time: 953.077 ms ... Execution time: 947.145 ms

      Ouille pas très convaincant ! L’exécution de la requête dure ici toujours autour de 1s. L’Index Only Scan ne servirait à rien ?!? 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. Ici ce n’est pas le cas et le nombre de vérifications auprès de la table (Heap Fetches) est exactement le même que celui du nombre de lignes à considérer après filtrage, 540630. 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; VACUUM explain analyze SELECT min(taille) FROM geants WHERE revenu > 900000; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=12461.17..12461.18 rows=1 width=2) (actual time=167.446..167.446 rows=1 loops=1) -> Index Only Scan using geants_i1 on geants (cost=0.43..11091.45 rows=547887 width=2) (actual time=0.013..116.429 rows=540630 loops=1) Index Cond: (revenu > 900000) Heap Fetches: 0 Planning time: 0.101 ms Execution time: 167.468 ms ... Execution time: 172.646 ms ... Execution time: 165.115 ms

      Plus de "heap fetches" nécessaires, les temps de réponse ont ici été divisés par 5. PostgreSQL est bien capable d’éviter complètement de lire les données de la table lorsque les données requises sont présentes dans un index et le gain peut se révéler très spectaculaire.

Mise à jour : 07/04/2017