Indexation : un BRIN de folie - partie 1

(sujet mis à jour avec la version 10 beta)

Toujours plus !

      Les possiblités d’indexation avec PostgreSQL ont été étendues. En plus des index classiques B-tree et des index GIN et GIST, il est possible depuis PostgreSQL 9.5 de créer des Block Range Index (BRIN). Quelles sont les caractéristiques de ces index par rapport aux B-Tree ?

      Les index BRIN ne remplacent PAS les index B-Tree et ils sont généralement moins efficaces lors des requêtes. Cependant ils peuvent être très utiles pour éviter des balayages complets de table en permettant l’indexation de colonnes peu souvent utilisées comme critères de sélection en environnement décisionnel.
      Dans cet exemple nous allons considérer une table VENTES_AGG contenant le montant total des ventes de notre site international à chaque seconde. Nous avons réalisé le montant de vente MTV dans la seconde suivant le temps stocké dans la colonne DTV. Cette colonne DTV est une bonne candidate pour un index BRIN. En effet les données dans DTV sont triées en fonction de l’ordre d’insertion pusque le temps passe au fur et à mesure des insertions. Cette table est en fait ici remplie grâce aux fonctions GENERATE_SERIES et RANDOM et nous allons déterminer une valeur moyenne sur une période donnée en comparant les performances d’un index B-Tree et d’un index BRIN avec PostgreSQL 9.5.0 :

postgres=# \timing Chronométrage activé. postgres=# create table ventes_agg(dtv timestamp, mtv integer); CREATE TABLE Temps : 5,729 ms postgres=# insert into ventes_agg postgres=# select generate_series(date_trunc('second', current_timestamp-interval '1 year'), postgres=# date_trunc('second', current_timestamp), postgres=# '1 second'), postgres=# trunc(random() * 100000 + 1); INSERT 0 31536001 Temps : 144892,471 ms postgres=# \d+ Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+------------+-------+--------------+---------+------------- public | ventes_agg | table | postgres | 1332 MB | (1 ligne) postgres=# explain select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------- Aggregate (cost=869281.26..869281.27 rows=1 width=4) -> Seq Scan on ventes_agg (cost=0.00..865962.20 rows=1327621 width=4) Filter: ((dtv >= to_timestamp('13/03/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv < to_timestamp('27/03/2015'::text, 'DD/MM/YYYY'::text))) (3 lignes) Temps : 2,432 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 109458,224 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 104880,457 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 104881,813 ms postgres=# create index br_dtv on ventes_agg using brin(dtv); CREATE INDEX Temps : 9744,103 ms postgres=# \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+--------+-------+--------------+------------+--------+------------- public | br_dtv | index | postgres | ventes_agg | 80 kB | (1 ligne) postgres=# explain select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------ Aggregate (cost=210694.02..210694.03 rows=1 width=4) -> Bitmap Heap Scan on ventes_agg (cost=12610.00..207625.24 rows=1227512 width=4) Recheck Cond: ((dtv >= to_timestamp('13/03/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv < to_timestamp('27/03/2015'::text, 'DD/MM/YYYY'::text))) -> Bitmap Index Scan on br_dtv (cost=0.00..12303.12 rows=1227512 width=0) Index Cond: ((dtv >= to_timestamp('13/03/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv < to_timestamp('27/03/2015'::text, 'DD/MM/YYYY'::text))) (5 lignes) Temps : 2,801 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 5098,562 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 4628,871 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 4539,238 ms postgres=# drop index br_dtv; DROP INDEX Temps : 5,906 ms postgres=# create index id_dtv on ventes_agg(dtv); CREATE INDEX Temps : 66340,853 ms postgres=# \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+--------+-------+--------------+------------+--------+------------- public | id_dtv | index | postgres | ventes_agg | 676 MB | (1 ligne) postgres=# explain select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------ Aggregate (cost=47722.59..47722.60 rows=1 width=4) -> Index Scan using id_dtv on ventes_agg (cost=0.57..44653.81 rows=1227512 width=4) Index Cond: ((dtv >= to_timestamp('13/03/2015'::text, 'DD/MM/YYYY'::text)) AND (dtv < to_timestamp('27/03/2015'::text, 'DD/MM/YYYY'::text))) (3 lignes) Temps : 2,207 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 916,602 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 797,573 ms postgres=# select avg(mtv) from ventes_agg where dtv >= to_timestamp('13/03/2015','DD/MM/YYYY') and dtv < to_timestamp('27/03/2015','DD/MM/YYYY'); avg -------------------- 49998.355997023810 (1 ligne) Temps : 760,026 ms

      Que remarque-t-on ? La table contient une année de données et la requête portant sur 14 jours de mars prend :

      L’index BRIN permet donc de diviser par plus de 20 le temps d’exécution alors que l’index B-Tree permet de le diviser encore par plus de 5. Cependant l’index B-Tree est 8652 fois plus volumineux que l’index BRIN : 672Mo contre 80Ko ! De plus la création de l’index B-Tree a pris plus d’une minute alors que l’index BRIN a été créé en moins de 10 secondes.
      Les index BRIN sont donc très efficaces s’ils sont utilisés selon les préconisations que l’on trouve dans la documentation PostgreSQL. Mais que se passe-t-il s’ils sont utilisés dans un cas a priori beaucoup plus défavorable ?

Mise à jour : 27/01/2016