Efficacité des index

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

Il sert à rien mon index ?!?

      Alex Mou, stagiaire, assiste un jour à une discussion enflammée. Prosper.E est très mécontent. Il estime être lésé par rapport à E.Van Der au niveau du matériel qui est pourtant normalement identique. Prosper cherche le potentiel moyen parmi les futurs clients nés en 2015 et c’est lent. En revanche, E.Van Der recherche rapidement le montant moyen parmi les ventes réalisées en 2015. La table des prospects fait autour de 5 millions de lignes comme la table des ventes et leurs tailles sont comparables. Les données à considérer représentent 10% du total dans les deux cas et un index existe sur la date.
      Alex décide d’enquêter sur ce mystère avec deux scenarii de test. D’abord E.Van Der :

select version(); version ---------------------------------------------------------------------------------------------------- PostgreSQL 10devel on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-8) 6.3.0 20170221, 64-bit (1 ligne) create table ventes_agg(dtv timestamp, mtv smallint); CREATE TABLE Temps : 43,663 ms WITH serie(i) AS (SELECT generate_series(1,5256000 ,1)) INSERT INTO ventes_agg (SELECT current_timestamp - i * '1 minute'::interval, trunc(random()*100) from serie); INSERT 0 5256000 Time: 11945,540 ms (00:11,946) select extract(year from dtv), count(*) from ventes_agg group by extract(year from dtv) order by 1; date_part | count -----------+-------- 2007 | 429559 2008 | 527040 2009 | 525600 2010 | 525600 2011 | 525600 2012 | 527040 2013 | 525600 2014 | 525600 2015 | 525600 2016 | 527040 2017 | 91721 (11 lignes) Time: 2833,996 ms (00:02,834) analyze ventes_agg; ANALYZE Temps : 411,778 ms postgres=# \dt+ ventes_agg Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+------------+-------+--------------+--------+------------- public | ventes_agg | table | postgres | 222 MB | (1 ligne) set max_parallel_workers_per_gather=0; SET explain analyze select avg(mtv) from ventes_agg where dtv between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=134830.64..134830.65 rows=1 width=32) (actual time=2276.085..2276.086 rows=1 loops=1) -> Seq Scan on ventes_agg (cost=0.00..133531.00 rows=519855 width=2) (actual time=391.432..2219.805 rows=525600 loops=1) Filter: ((dtv >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Rows Removed by Filter: 4730400 Planning time: 0.056 ms Execution time: 2276.109 ms ... Planning time: 0.064 ms Execution time: 2285.435 ms ... Planning time: 0.067 ms Execution time: 2303.971 ms set max_parallel_workers_per_gather=3; SET explain analyze select avg(mtv) from ventes_agg where dtv between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=63740.23..63740.24 rows=1 width=32) (actual time=624.474..624.474 rows=1 loops=1) -> Gather (cost=63739.91..63740.22 rows=3 width=32) (actual time=624.426..624.466 rows=4 loops=1) Workers Planned: 3 Workers Launched: 3 -> Partial Aggregate (cost=62739.91..62739.92 rows=1 width=32) (actual time=619.384..619.385 rows=1 loops=4) -> Parallel Seq Scan on ventes_agg (cost=0.00..62320.68 rows=167695 width=2) (actual time=114.817..605.783 rows=131400 loops=4) Filter: ((dtv >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Rows Removed by Filter: 1182600 Planning time: 0.073 ms Execution time: 626.995 ms ... Planning time: 0.180 ms Execution time: 640.018 ms ... Planning time: 0.074 ms Execution time: 634.993 ms create index ventes_agg_i1 on ventes_agg(dtv); CREATE INDEX Time: 6612,634 ms (00:06,613) \di+ ventes_agg_i1 Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+---------------+-------+--------------+------------+--------+------------- public | ventes_agg_i1 | index | postgres | ventes_agg | 113 MB | (1 ligne) select correlation from pg_stats where tablename='ventes_agg' and attname = 'dtv'; correlation ------------- -1 (1 ligne) explain analyze select avg(mtv) from ventes_agg where dtv between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------ Aggregate (cost=20656.61..20656.62 rows=1 width=32) (actual time=163.512..163.512 rows=1 loops=1) -> Index Scan using ventes_agg_i1 on ventes_agg (cost=0.44..19328.48 rows=531252 width=2) (actual time=0.030..102.133 rows=525600 loops=1) Index Cond: ((dtv >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Planning time: 0.156 ms Execution time: 163.544 ms ... Planning time: 0.084 ms Execution time: 167.483 ms ... Planning time: 0.087 ms Execution time: 164.751 ms drop index ventes_agg_i1; DROP INDEX Temps : 289,288 ms create index ventes_agg_br1 on ventes_agg using brin(dtv); CREATE INDEX Temps : 783,252 ms \di+ ventes_agg_br1 Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+----------------+-------+--------------+------------+--------+------------- public | ventes_agg_br1 | index | postgres | ventes_agg | 48 kB | (1 ligne) explain analyze select avg(mtv) from ventes_agg where dtv between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=45821.51..45821.52 rows=1 width=32) (actual time=441.963..441.964 rows=1 loops=1) -> Bitmap Heap Scan on ventes_agg (cost=5457.34..44493.38 rows=531252 width=2) (actual time=2.918..383.086 rows=525600 loops=1) Recheck Cond: ((dtv >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Rows Removed by Index Recheck: 19040 Heap Blocks: lossy=2944 -> Bitmap Index Scan on ventes_agg_br1 (cost=0.00..5324.52 rows=531252 width=0) (actual time=0.154..0.154 rows=29440 loops=1) Index Cond: ((dtv >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Planning time: 0.139 ms Execution time: 442.002 ms ... Planning time: 0.084 ms Execution time: 463.037 ms ... Planning time: 0.080 ms Execution time: 462.794 ms

      Le balayage complet de la table (Seq Scan) est ici particulièrement lent même si le parallélisme permet mécaniquement d’améliorer les choses. Mais c’est l’indexation qui se révèle ici la plus efficace. En effet le passage par un minuscule index BRIN ou le passage par un index B-Tree donnent de meilleurs résultats que la force brute.
      Pourquoi le passage par les index est-il si efficace alors que nous nous intéressons tout de même à une grande partie des valeurs ? La corrélation entre le séquencement des valeurs de dtv et leur ordre d’insertion est ici de -1, soit une valeur parfaite dans l’ordre descendant. Cela signifique que des valeurs consécutives de dtv sont regroupées dans le nombre de pages le plus réduit possible plutôt que d’être dispersées dans un grand nombre de pages. Qu’en est-il à présent dans le cas de Prosper.E ?

create table prospects(dtn timestamp, pot smallint); CREATE TABLE insert into prospects(dtn, pot) select dtv, mtv from ventes_agg order by random(); INSERT 0 5256000 Time: 12739,939 ms (00:12,740) analyze prospects; ANALYZE Temps : 415,226 ms select extract(year from dtn), count(*) from prospects group by extract(year from dtn) order by 1; date_part | count -----------+-------- 2007 | 429559 2008 | 527040 2009 | 525600 2010 | 525600 2011 | 525600 2012 | 527040 2013 | 525600 2014 | 525600 2015 | 525600 2016 | 527040 2017 | 91721 (11 lignes) \dt+ prospects Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+-----------+-------+--------------+--------+------------- public | prospects | table | postgres | 222 MB | (1 ligne) set max_parallel_workers_per_gather=0; SET explain analyze select avg(pot) from prospects where dtn between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=134841.93..134841.94 rows=1 width=32) (actual time=2358.338..2358.338 rows=1 loops=1) -> Seq Scan on prospects (cost=0.00..133531.00 rows=524372 width=2) (actual time=0.144..2299.184 rows=525600 loops=1) Filter: ((dtn >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtn <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Rows Removed by Filter: 4730400 Planning time: 0.065 ms Execution time: 2358.366 ms ... Planning time: 0.067 ms Execution time: 2299.815 ms ... Planning time: 0.064 ms Execution time: 2299.976 ms set max_parallel_workers_per_gather=3; SET explain analyze select avg(pot) from prospects where dtn between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=63743.88..63743.89 rows=1 width=32) (actual time=626.567..626.567 rows=1 loops=1) -> Gather (cost=63743.56..63743.87 rows=3 width=32) (actual time=626.468..626.559 rows=4 loops=1) Workers Planned: 3 Workers Launched: 3 -> Partial Aggregate (cost=62743.56..62743.57 rows=1 width=32) (actual time=623.787..623.787 rows=1 loops=4) -> Parallel Seq Scan on prospects (cost=0.00..62320.68 rows=169152 width=2) (actual time=0.262..610.000 rows=131400 loops=4) Filter: ((dtn >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtn <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Rows Removed by Filter: 1182600 Planning time: 0.075 ms Execution time: 629.094 ms ... Planning time: 0.074 ms Execution time: 625.606 ms ... Planning time: 0.077 ms Execution time: 683.792 ms create index prospects_i1 on prospects(dtn); CREATE INDEX Time: 8895,121 ms (00:08,895) \di+ prospects_i1 Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+--------------+-------+--------------+-----------+--------+------------- public | prospects_i1 | index | postgres | prospects | 113 MB | (1 ligne) select correlation from pg_stats where tablename='prospects' and attname = 'dtn'; correlation ------------- -0.00636855 (1 ligne) explain analyze select avg(pot) from prospects where dtn between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=50965.53..50965.54 rows=1 width=32) (actual time=285.467..285.468 rows=1 loops=1) -> Bitmap Heap Scan on prospects (cost=10947.90..49675.90 rows=515850 width=2) (actual time=64.657..226.816 rows=525600 loops=1) Recheck Cond: ((dtn >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtn <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Heap Blocks: exact=28411 -> Bitmap Index Scan on prospects_i1 (cost=0.00..10818.94 rows=515850 width=0) (actual time=60.635..60.635 rows=525600 loops=1) Index Cond: ((dtn >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtn <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Planning time: 0.145 ms Execution time: 285.502 ms ... Planning time: 0.085 ms Execution time: 245.882 ms ... Planning time: 0.114 ms Execution time: 242.054 ms set enable_bitmapscan=off; SET set enable_seqscan=off; SET explain analyze select avg(pot) from prospects where dtn between to_date('01/01/2015', 'DD/MM/YYYY') and to_date('01/01/2016','DD/MM/YYYY'); QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=130906.57..130906.58 rows=1 width=32) (actual time=969.012..969.012 rows=1 loops=1) -> Index Scan using prospects_i1 on prospects (cost=0.44..129616.94 rows=515850 width=2) (actual time=0.060..899.322 rows=525600 loops=1) Index Cond: ((dtn >= to_date('01/01/2015'::text, 'DD/MM/YYYY'::text)) AND (dtn <= to_date('01/01/2016'::text, 'DD/MM/YYYY'::text))) Planning time: 0.085 ms Execution time: 969.045 ms ... Planning time: 0.111 ms Execution time: 954.666 ms ... Planning time: 0.085 ms Execution time: 949.884 ms

      Non, Prosper.E n’était pas injustement défavorisé ! Pour les recherches sur une date, ou une petite plage de dates parmi les 5 millions, il n’y aurait pas de grandes différences entre les cas de Prosper et Van Der. Mais, en considérant 10% des dates, l’écart devient important. Pourquoi ? Parce que dans le cas de Prosper la corrélation entre le séquencement des valeurs de dtn et leur ordre "physique" dans les pages de la table rend beaucoup moins favorable un index scan. La valeur de corrélation est proche de 0 et cela se retrouve dans les estimations de coût. La requête concerne certes toujours 10% des lignes. Mais elle concerne surtout l’ensemble des pages de la table en raison de la dispersion des données. PostgreSQL va néanmoins tirer parti de l’index d’une manière différente. Bitmap index scan / bitmap heap scan : tous les pointeurs de ligne sont obtenus depuis l’index, ils sont triés dans une structure bitmap puis la table est balayée dans l’ordre physique enregistré dans cette structure. Mais le point le plus important est que PostgreSQL avait bien raison de ne pas utiliser l’index de manière classique, un balayage complet de la table étant plus efficace.

      Quid des autres SGBD ? Oracle Database se comporte de manière similaire. Seule différence : Oracle ne tire pas parti de l’index avec une structure bitmap comme PostgreSQL dans le second exemple et réalise un FULL TABLE SCAN lors de tests sur un optimiseur 11.2.0.2 (Oracle 11gR2 XE). L’équivalent de la corrélation pour Oracle est le clustering factor, c’est à dire le nombre de blocs qui seraient visités si l’index était utilisé pour retrouver chaque ligne en parcourant l’index dans l'ordre. Plus ce nombre est grand, plus il est mauvais donc. Cependant, globalement, le raisonnement à avoir pour un développeur est le même avec Oracle qu’avec PostgreSQL.

      L’entreprise d’Alex Mou ne compte pas passer sur SQL Server et je ne suis pas spécialiste de ce SGBD. Par curiosité je me suis cependant lancé dans le même test et j’ai obtenu des résultats complètement différents. Dans le cas de E.Van Der comme dans celui de Prosper.E, avec une "heap table", SQL Server Express 2014 ne tire pas parti d’un non clustered index sur la date et effectue une lecture logique par ligne retournée si on le force à l’utiliser. L’optimiseur fait donc le bon choix puisque forcer le passage par l’index ne se révèle pas favorable. SQL Server suggérait d’inclure la valeur (mtv ou pot) dans l’index. Autre possibilité : créer un clustered index sur la date. Lors de mes tests cela permettait bien de diviser les lectures logiques par 10 et de diminuer le temps d’exécution. Dans le cas d’une table interrogée selon des critères différents, il doit cependant être délicat de choisir un clustered index. Je comprends mieux pourquoi certains experts SQL Server semblaient considérer que ne pas disposer d’index couvrants dans PostgreSQL était si catastrophique. La possibilité de faire des INDEX ONLY SCAN a été ajoutée en version 9.2 mais c’est juste un plus pour PostgreSQL alors que c’est quasi essentiel pour SQL Server.

Mise à jour : 05/03/2017