La version 9.5 de PostgreSQL sortie en Janvier 2016 propose un nouveau type d’index : les Index BRIN pour Bloc Range INdex. Ces derniers sont recommandés pour les tables volumineuses et corrélées avec leur emplacement. J’ai décidé de consacrer une série d’article sur ces index :

Pour information, je serai présent au PGDay France à Lille le mardi 31 mai pour présenter cet index. Il y aura également plein d’autres conférences intéressantes!

Cet article est la dernier de la série, il sera consacré aux performances (maintenance, lecture, insertion…)

Performances

Les articles précédents ont abordé le fonctionnement et les spécificités des index BRIN. Cet article sera plutôt consacré aux performances. Les exemples précédents portaient sur de petites volumétries. Maintenant nous allons voir ce que peuvent apporter ces index sur une volumétrie plus importante.

Les tests ont été effectués sur un PC portable, les journaux de transaction, la table et les index sont stockés sur un disque mécanique. Les résultats seront différents suivant la matériel utilisé. Ces chiffres sont purement indicatifs et servent surtout à se donner un ordre d’idée.

Exemple

Dans un premier temps il est nécessaire de créer une table avec une volumétrie importante.

Par exemple : un système de mesure avec 100 sondes et une mesure toutes les secondes. Nous allons donc obtenir 100*365*24*3600 mesures => un peu plus de 3 milliards de lignes.

La table obtenue fait un peu plus de 150Go, elle ne rentre donc pas dans  la RAM de la machine hébergeant l’instance et encore moins dans la mémoire partagée de PostgreSQL.

Maintenance

On crée plein d’index pour comparer leur taille :

Voici les résultats obtenus pour la durée de création des index et leurs tailles :

size-largesize-large

La création de l’index a été 4 fois plus rapide pour les index BRIN. Il est possible que leur création aurait été plus rapide avec un stockage plus performant.

La taille des index est également frappante,  l’index b-tree fait 66 Go alors que l’index BRIN avec le pages_per_range par défaut fait seulement 5 Mo.

On peut tout suite constater le gain sur l’espace utilisé et la rapidité de création des index. Les opérations de maintenances (REINDEX) seront grandement facilitées.

Performances en lecture

Nous allons effectuer plusieurs tests, l’idée est d’essayer de mettre en valeur les différences de comportements entre les index BRIN et b-tree.

La requête utilisée sera tout simple :

pour obtenir un résultat avec peu de lignes  :

Pour obtenir plus de résultat on prendra un intervalle avec :

Voici les résultats obtenus :

lignes BRIN Btree Gain
Durée Blocs lus Durée Blocs lus Durée Volume données lues
100 24ms 697 0.06ms 7 Btree (x400) Btree (x100)
267 millions 170s 13Go 228s 18Go BRIN (x1.3) BRIN (x1.4)
777 millions 8min 38Go 11min 54Go BRIN (x1.37) BRIN (x1.4)
1.3 milliard 13min 63Go 32min (seqscan)
18min
153 Go (seqscan)
90 Go
BRIN (x2) vs seqscan
BRIN (1.4x) vs Btree
BRIN (x2.4) vs seqscan
BRIN (1.4x) vs Btree

Pour comparer le volume de données lues et la durée d’exécution nous pouvons désactiver les index dans une transaction :

Pour le 1er test, le moteur choisit l’index-btree. En supprimant l’index b-tree il choisit l’index BRIN.

Pour les tests 2 et 3, le moteur choisit l’index BRIN, en supprimant l’index BRIN il choisit l’index b-tree.

Pour le dernier test j’ai rajouté d’autres mesures. En effet, en supprimant l’index BRIN le moteur va effectuer un seqscan (parcours de toute la table). Pour obtenir les mêmes comparaisons que les résultats précédents j’ai donc supprimé l’index BRIN et désactivé les parcours séquentiels (set enable_seqscan to ‘off’;)

Globalement on peut constater un gain de 30-40% dans les cas où beaucoup de résultats sont demandés. Le moteur lit moins de blocs lorsqu’il utilise les index BRIN, l’index b-tree étant volumineux, ses lectures sont coûteuses.

En revanche l’index b-tree s’avère particulièrement performant lorsque la requête est très sélective et que peu de résultats sont retournés. En effet, en utilisant un index BRIN, le moteur commence par lire l’intégralité de l’index. Puis il va lire un ensemble de blocs qui contiennent la valeur recherchée, certains ne contenants aucun résultat. Ces lectures supplémentaires se ressentent sur la durée d’exécution de la requête.

Performances en insertion

Vu que les index BRIN sont plus petits et leur durée de création plus courte, on peut se demander ce qu’il advient du surcoût de cet index lors d’insertion de données. Pour cela on va créer une table et mesurer l’insertion de 10 millions de lignes en fonction des index déjà présents sur la table. Afin de cibler le surcoût dû à la mise à jour des index, la table est non-journalisée, ceci permet d’éviter les écritures dans les journaux de transaction. L’autovacuum est également désactivé.

Voici les résultats obtenus :

insertionComme pour les chiffres sur les performances en lecture, ces chiffres ne représentent que les durées d’insertion sur mon matériel. La table, les index et les journaux de transaction sont sur le même disque physique, ce qui ralenti les opérations.

Cependant on peut constater qu’il est moins coûteux d’insérer des données dans une table avec un index BRIN qu’avec un index b-tree. On constate également qu’il n’y a pas d’écart significatif entre les différents types d’index BRIN.

Conclusion

Cette série d’articles a permis de présenter les principes des index BRIN. puis leur fonctionnement à travers des exemples simples.

Ensuite nous avons vu l’importance de la corrélation pour exploiter pleinement ces index. Enfin, nous avons essayé de mesurer le gain que pouvait apporter cet index sur de multiples aspect (maintenance, performance en lecture et insertion).

Décrire le fonctionnement d’un index en simplifiant sa représentation est un exercice compliqué. On peut vite sacrifier le fond à la forme. Présenter des chiffres est également délicat tellement ils peuvent dépendre du contexte. J’ai fait l’effort de détailler comment je les ai obtenu afin que chacun puisse reproduire ses propres tests. L’idée est de donner un aperçu des cas d’utilisation de ce type d’index.

Globalement il faut retenir que les index BRIN sont utiles pour les tables volumineuses et où la corrélation avec l’emplacement des données est importante. Ils seront plus lents que les index b-tree lorsque la recherche nécessite de parcourir peu de blocs. Ils seront un peu plus rapide que les index b-tree dans les situations où le moteur doit lire beaucoup de blocs (moins de blocs à lire dans l’index).

L’étude de cet index ouvre d’autres pistes de réflexion. Comme la prise en compte de la corrélation dans le calcul du coût. J’avais également pensé à la possibilité d’utiliser un index pour créer un autre index.

Dans l’exemple avec la table volumineuse (150Go). Si on souhaite créer un index partiel sur le mois précédent, le moteur va parcourir l’intégralité de la table pour créer d’index. On pourrait envisager créer l’index b-tree en utilisant l’index BRIN pour ne parcourir que les lignes correspondant au moins précédent.

La version 9.5 de PostgreSQL sortie en Janvier 2016 propose un nouveau type d’index : les Index BRIN pour Bloc Range INdex. Ces derniers sont recommandés pour les tables volumineuses et corrélées avec leur emplacement. J’ai décidé de consacrer une série d’article sur ces index :

Pour information, je serai présent au PGDay France à Lille le mardi 31 mai pour présenter cet index. Il y aura également plein d’autres conférences intéressantes!

Dans ce troisième article nous verrons pourquoi la corrélation des données avec leur emplacement est importante pour les index BRIN.

Données corrélées

Ces premiers exemples étaient volontairement simples voire simplistes afin de faciliter la compréhension. Les enregistrements avaient une particularité importante : les valeurs étaient croissantes.

Ce qui signifie qu’il y a une forte corrélation entre les enregistrements et leur emplacement.

Pour information, le moteur stocke des statistiques sur les tables afin de choisir le meilleur plan d’exécution. Lançons un ANALYSE sur notre table brin_demo et consultons la vue pg_stats, notamment la colonne « correlation » :

Essayons avec des données aléatoires :

=> La vue pg_stats nous indique que les données ne sont pas corrélées avec leur emplacement.

Que contient notre index?

L’index nous indique que tous les blocs contiennent des valeurs comprises entre 1 et 90.

Que donne une recherche des valeurs comprises entre 10 et 20?

=> Le moteur lit l’intégralité de la table ainsi que 2 blocs d’index.

Il est légitime de se demander quel est l’intérêt d’utiliser l’index si on sait que les données ne sont pas corrélées. Et qu’au final le moteur sera contraint de lire toute la table.

Allons faire un tour dans le code source. Plus précisément à la ligne 7568 du fichier src/backend/utils/adt/selfuncs.c :

On peut voir « *indexCorrelation = 1; ». En réalité le moteur ignore la corrélation… pour le moment. Une discussion est en cours pour prendre en compte la corrélation dans le coût de l’index : http://www.postgresql.org/message-id/20151116135239.GV614468@alvherre.pgsql

Trions notre table en utilisant l’ordre CLUSTER et un index b-tree :

Vérifions la corrélation :

Rejouons notre requête :

Cette fois le moteur a lu moins de blocs, regardons ce que contient notre index :

Cette fois le moteur savait qu’il n’avait à parcourir que les blocs de 48 à 96.

La version 9.5 de PostgreSQL sortie en Janvier 2016 propose un nouveau type d’index : les Index BRIN pour Bloc Range INdex. Ces derniers sont recommandés pour les tables volumineuses et corrélées avec leur emplacement. J’ai décidé de consacrer une série d’article sur ces index :

Pour information, je serai présent au PGDay France à Lille le mardi 31 mai pour présenter cet index. Il y aura également plein d’autres conférences intéressantes!

Dans ce 2eme volet nous allons voir en détail le fonctionnement d’un index BRIN.

Fonctionnement

L’index va contenir la valeur minimale et maximale 1 d’un attribut sur un ensemble de blocs : range  (dans le cas d’un index sur une seule colonne)

La taille du range par défaut est de 128 blocs (128 x 8Ko => 1Mo).

Prenons l’exemple suivant, une table de 100 000 lignes contenant une colonne id incrémentée de 1.  Schématiquement ma table sera stockée de cette façon (un bloc pouvant contenir plusieurs lignes) :

Bloc id
0 1
0 2
1 227
128 28929
255 57856
256 57857

Si on cherche les valeurs comprises entre 28929 et 57856 le moteur devra parcourir l’intégralité de la table. Il ne sait pas qu’il n’est pas nécessaire de lire avant le bloc 128 et après le bloc 255.

Le premier réflexe serait de créer un index b-tree. Sans rentrer dans les détails, ce type d’index permet un parcours plus efficace de la table. Il contiendra l’emplacement de chaque valeur de la table.

Schématiquement, en omettant la présentation en arborescence, l’index contiendrait :

id Emplacement
1 0
2 0
227 1
57857 256

Intuitivement on peut déjà en déduire que si notre table est volumineuse, l’index sera également volumineux.

Un index BRIN contiendrait les lignes suivantes :

Range (128 blocs) min max allnulls hasnulls
1 1 28928 non non
2 28929 57856 non non
3 57857 86784 non non
4 86785 115712 non non

Ainsi en cherchant les valeurs comprises entre 28929 et 57856 le moteur sait qu’il devra parcourir les blocs 128 à 255.

En comparant par rapport à un index B-tree j’ai pu représenter en 4 lignes ce qui m’aurait pris plus de 100 000 lignes dans un B-tree. Bien entendu la réalité est bien plus complexe, néanmoins, cette simplification permet déjà d’avoir un aperçu de la compacité de ce type d’index.

Influence taille du range

Par  défaut la taille du range est de 128 blocs, ce qui correspond à 1Mo (1 bloc fait 8Ko). par curiosité on va tester différentes tailles de range grâce à l’option pages_per_range.

Prenons un jeu de données plus conséquent, avec 100 millions de lignes :

Notre table fait presque 3,5Go :

Activons l’option « \timing » de psql afin de mesurer le temps de créations des index. Commençons par les index BRIN avec une valeur pages_per_range différente :

Créons également un index b-tree :

Comparons les tailles :

Voici les résultats obtenus sur les durées de création des index et leur tailles :

duration
La création d’index est bien plus rapide. Il y a quasiment un facteur x10 entre les deux types d’index. J’ai obtenu ces chiffres avec la version 9.5.1 sur une configuration assez basique (pc portable et disque mécanique). Je vous conseille de mener vos propres tests avec votre matériel.

Pour information j’ai positionné la maintenance_work_mem à 1GB, malgré cette valeur élevée cela n’a pas empêché la création de fichiers temporaires pour l’index b-tree.

sizePour les tailles d’index la différence est bien plus importante, j’ai du utiliser une échelle logarithmique pour représenter l’écart. L’index BRIN avec un pages_per_range  par défaut fait 128Ko alors que le b-tree fait plus de 2Go!

Qu’en est-il des requêtes ?

Essayons cette requête qui récupère les valeurs comprises entre 10 et 2000. Pour étudier en détail ce que fait le moteur nous allons utiliser EXPLAIN avec les options (ANALYZE,VERBOSE,BUFFERS).

Enfin, pour faciliter l’analyse nous allons utiliser un jeu de données plus petit :

Sans index le moteur parcours toute la table (seq scan) et lit 443 blocs.

La même requête avec un index BRIN :

Le moteur lit 2 blocs d’index puis 128 blocs de la table.

Essayons avec un pages_per_range plus petit, à 16 par exemple :

La encore le moteur lit 2 blocs dans l’index, en revanche il ne va lire que 16 blocs dans la table.

Un index avec un pages_per_range plus petit sera plus sélectif et permettra de lire moins de blocs.

Utilisons l’extension pageinspect pour observer le contenu des index :

Avec l’index brin_demo_brin_idx_16 on remarque bien que les valeurs qui nous intéressent sont présentes dans le premier ensemble de blocs (0 à 15). En revanche avec l’index brin_demo_brin_idx, celui-ci est moins sélectif. Les valeurs qui nous intéressent sont comprises les blocs 0 à 127 ce qui explique pourquoi il y a plus de blocs lus dans le premier exemple.

 

  1. L’index contient également deux booléens indiquant si l’ensemble contient des valeurs NULL (hasnulls ) ou s’il ne contient que des valeurs NULL (allnulls)

La version 9.5 de PostgreSQL sortie en Janvier 2016 propose un nouveau type d’index : les Index BRIN pour Bloc Range INdex. Ces derniers sont recommandés pour les tables volumineuses et corrélées avec leur emplacement. J’ai décidé de consacrer une série d’article sur ces index :

Pour information, je serai présent au PGDay France à Lille le mardi 31 mai pour présenter cet index. Il y aura également plein d’autres conférences intéressantes!

Introduction

PostgreSQL propose déjà différents type d’index : B-Tree, GIN, GiST, SP-GiST, Hash  1

Les discussions ont commencées en 2008 : Segment Exclusion
Suivi de ce RFC en 2008 qui propose les « Minmax indexes » qui sera renommé plus tard en BRIN.

Physiquement, une table est composée de blocs de 8Ko et chaque bloc contient des enregistrements 2. L’idée des index BRIN est de stocker dans un index la valeur minimale et maximale d’un attribut d’un ensemble de bloc (range) 3. Ainsi il est possible d’exclure un ensemble de bloc si vous recherchez une valeur qui n’est pas comprise dans l’intervalle.

Note : Les index BRIN sont similaires aux storage indexes d’Oracle (4. Exadata Storage Indexes).

Voici les types supportés : Built-in Operator Classes

Il est également possible d’indexer plusieurs colonnes. Notez que la documentation actuelle ne le mentionne pas, c’est corrigé dans la version en cours de développement : Multicolumn Indexes

 

  1. SELECT amname FROM pg_am; ou encore http://www.postgresql.org/docs/current/static/indexes-types.html 
  2. Si un enregistrement ne tient pas dans un bloc il est stocké séparément dans ce qu’on appelle le TOAST (The Oversized-Attribute Storage Technique). Plus exactement, si un enregistrement dépasse 2ko.
  3. L’index contient également deux booléens indiquant si l’ensemble contient des valeurs NULL (hasnulls ) ou s’il ne contient que des valeurs NULL (allnulls)