Efficacité des index

(sujet mis à jour avec la version 10 devel)

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 9.6beta1, compiled by Visual C++ build 1800, 64-bit (1 ligne) create table ventes_agg(dtv timestamp, mtv smallint); CREATE TABLE do $$ begin for i in 1..5256000 loop insert into ventes_agg(dtv,mtv) values (current_timestamp - i * '1 minute'::interval, trunc(random()*100)); end loop; end$$; DO select extract(year from dtv), count(*) from ventes_agg group by extract(year from dtv) order by 1; date_part | count -----------+-------- 2006 | 307524 2007 | 525600 2008 | 527040 2009 | 525600 2010 | 525600 2011 | 525600 2012 | 527040 2013 | 525600 2014 | 525600 2015 | 525600 2016 | 215196 (11 lignes) \dt+ ventes_agg Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+------------+-------+--------------+--------+------------- public | ventes_agg | table | postgres | 222 MB | (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 ----------------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=56018.29..56018.30 rows=1 width=32) (actual time=3281.515..3281.515 rows=1 loops=1) -> Gather (cost=56017.86..56018.27 rows=4 width=32) (actual time=3281.487..3281.501 rows=5 loops=1) Workers Planned: 4 Workers Launched: 4 -> Partial Aggregate (cost=55017.86..55017.87 rows=1 width=32) (actual time=3198.423..3198.423 rows=1 loops=5) -> Parallel Seq Scan on ventes_agg (cost=0.00..54691.00 rows=130745 width=2) (actual time=345.361..3157.326 rows=105120 loops=5) 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: 946080 Planning time: 0.476 ms Execution time: 3301.831 ms (10 lignes) set max_parallel_degree=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=134838.46..134838.47 rows=1 width=32) (actual time=19429.577..19429.578 rows=1 loops=1) -> Seq Scan on ventes_agg (cost=0.00..133531.00 rows=522981 width=2) (actual time=1306.770..19239.445 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.390 ms Execution time: 19429.696 ms (6 lignes) create index ventes_agg_i1 on ventes_agg(dtv); CREATE INDEX \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=20337.51..20337.52 rows=1 width=32) (actual time=416.829..416.829 rows=1 loops=1) -> Index Scan using ventes_agg_i1 on ventes_agg (cost=0.44..19030.06 rows=522981 width=2) (actual time=0.056..276.385 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.248 ms Execution time: 416.918 ms (5 lignes) drop index ventes_agg_i1; DROP INDEX create index ventes_agg_br1 on ventes_agg using brin(dtv); CREATE INDEX \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=45550.63..45550.64 rows=1 width=32) (actual time=3292.303..3292.303 rows=1 loops=1) -> Bitmap Heap Scan on ventes_agg (cost=5372.56..44243.18 rows=522981 width=2) (actual time=13.429..3111.615 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..5241.81 rows=522981 width=0) (actual time=0.890..0.890 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.282 ms Execution time: 3292.433 ms (9 lignes)

      Le balayage complet de la table (Seq Scan) sans parallèlisme est ici particulièrement lent. Le meilleur temps pour la requête est obtenu avec l’index B-Tree utilisé de manière classique (Index Scan). Le passage par un index BRIN donne à peu près le même temps qu’un balayage complet de la table effectué par 4 processus opérant en parallèle.
      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 select extract(year from dtn), count(*) from prospects group by extract(year from dtn) order by 1; date_part | count -----------+-------- 2006 | 307524 2007 | 525600 2008 | 527040 2009 | 525600 2010 | 525600 2011 | 525600 2012 | 527040 2013 | 525600 2014 | 525600 2015 | 525600 2016 | 215196 (11 lignes) \dt+ prospects Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+-----------+-------+--------------+--------+------------- public | prospects | table | postgres | 222 MB | (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 ----------------------------------------------------------------------------------------------------------------------------------------------------- Finalize Aggregate (cost=56022.39..56022.40 rows=1 width=32) (actual time=3280.736..3280.736 rows=1 loops=1) -> Gather (cost=56021.97..56022.38 rows=4 width=32) (actual time=3280.432..3280.718 rows=5 loops=1) Workers Planned: 4 Workers Launched: 4 -> Partial Aggregate (cost=55021.97..55021.98 rows=1 width=32) (actual time=3201.803..3201.803 rows=1 loops=5) -> Parallel Seq Scan on prospects (cost=0.00..54691.00 rows=132388 width=2) (actual time=0.956..3164.849 rows=105120 loops=5) 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: 946080 Planning time: 0.312 ms Execution time: 3302.572 ms (10 lignes) set max_parallel_degree=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=134854.88..134854.89 rows=1 width=32) (actual time=18826.115..18826.116 rows=1 loops=1) -> Seq Scan on prospects (cost=0.00..133531.00 rows=529552 width=2) (actual time=0.754..18615.907 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.309 ms Execution time: 18826.242 ms (6 lignes) create index prospects_i1 on prospects(dtn); CREATE INDEX \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.000642835 (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=51566.27..51566.28 rows=1 width=32) (actual time=1237.711..1237.711 rows=1 loops=1) -> Bitmap Heap Scan on prospects (cost=11240.35..50242.39 rows=529552 width=2) (actual time=359.171..1062.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..11107.96 rows=529552 width=0) (actual time=335.996..335.996 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.360 ms Execution time: 1238.718 ms (8 lignes) 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=131371.31..131371.32 rows=1 width=32) (actual time=7810.319..7810.319 rows=1 loops=1) -> Index Scan using prospects_i1 on prospects (cost=0.44..130047.43 rows=529552 width=2) (actual time=0.266..7556.313 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.261 ms Execution time: 7810.417 ms (5 lignes)

      Non, Prosper.E n’était pas injustement défavorisé ! Pour les recherches sur une date ou une petite plage de dates sur 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 : 29/05/2016