Indexation : BLOOM

Toujours plus !

      Les possiblités d’indexation avec PostgreSQL ont (encore) été étendues. En plus des index classiques B-tree, des index GIN et GIST, des index BRIN, il est possible depuis PostgreSQL 9.6 de créer des index BLOOM. Burton Howard Bloom a imaginé une structure, le filtre de Bloom en 1970. Comme l’indique Wikipedia, un filtre de Bloom permet de savoir :

      Les index BLOOM, déjà utilisés notamment dans BigTable de Google, ont été ajoutés en tant qu’extension avec PostgreSQL 9.6. Ils sont présentés comme spécialement intéressants dans les recherches multi-critères, quand la liste de ces critères est variable. En effet, un index composé BLOOM n’est pas soumis à l’habituelle règle des index composés B-Tree. Ils ne perdent PAS leur efficacité si la 1ère colonne (leading column) n’est pas utilisée en tant que critère de recherche. Ils ne sont pas aussi efficaces dans les requêtes qu’un ensemble d'index B-Tree, notamment car les faux positifs entraînent une vérification complémentaire. Mais ils peuvent permettre un compromis intéressant entre l’efficacité des recherches, les performances DML (insert, update, delete) et la consommation d’espace.
      Dans cet exemple nous allons considérer une table t1 comprenant 8 colonnes allant de c1 à c8. c1 est la clé primaire. Les colonnes c2 à c6 peuvent servir de critères de recherche :

SELECT version(); version ------------------------------------------------------------------------------------------ PostgreSQL 9.6.1 on x86_64-pc-linux-gnu, compiled by gcc (Debian 4.9.2-10) 4.9.2, 64-bit (1 ligne) CREATE TABLE t1(c1 SERIAL PRIMARY KEY, c2 CHARACTER VARYING(32), c3 CHARACTER VARYING(32), c4 INTEGER, c5 SMALLINT, c6 CHARACTER(1), c7 CHARACTER VARYING(64), c8 CHARACTER VARYING(64)); CREATE TABLE INSERT INTO t1(c2,c3,c4,c5,c6,c7,c8) SELECT lower(md5(random()::text)), lower(md5(random()::text)), trunc(random() * 1000000), trunc(random() * 200), CASE WHEN random() <= 0.55 THEN 'M' ELSE 'F' END, lower(md5(random()::text)), lower(md5(random()::text)) FROM generate_series(1,100000); INSERT 0 100000 Temps : 2786,118 ms \d+ Liste des relations Schéma | Nom | Type | Propriétaire | Taille | Description --------+-----------+----------+--------------+------------+------------- public | t1 | table | postgres | 17 MB | public | t1_c1_seq | séquence | postgres | 8192 bytes | ANALYZE t1; ANALYZE Temps : 742,800 ms EXPLAIN ANALYZE SELECT c1 FROM t1 WHERE (c2 = 'a95f8c4964b850c6040deaedb611cb15' OR c3 = 'a95f8c4964b850c6040deaedb611cb15') AND (c4 = 45000 OR c5 = 187) AND c6 = 'F' ; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Seq Scan on t1 (cost=0.00..4473.00 rows=1 width=4) (actual time=0.065..54.756 rows=1 loops=1) Filter: ((c6 = 'F'::bpchar) AND (((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) OR ((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text)) AND ((c4 = 45000) OR (c5 = 187))) Rows Removed by Filter: 99999 Planning time: 0.154 ms Execution time: 54.801 ms (5 lignes) ... Planning time: 0.148 ms Execution time: 54.590 ms ... Planning time: 0.158 ms Execution time: 54.739 ms ... CREATE EXTENSION bloom; CREATE EXTENSION CREATE INDEX bl1 ON t1 USING BLOOM(c2,c3,c4,cast (c5 as integer), cast (c6 as character varying)); CREATE INDEX Temps : 192,919 ms \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+---------+-------+--------------+-------+---------+------------- public | bl1 | index | postgres | t1 | 1584 kB | public | t1_pkey | index | postgres | t1 | 2208 kB | (2 lignes) EXPLAIN ANALYZE SELECT c1 FROM t1 WHERE (c2 = 'a95f8c4964b850c6040deaedb611cb15' OR c3 = 'a95f8c4964b850c6040deaedb611cb15') AND (c4 = 45000 OR c5 = 187) AND c6 = 'F' ; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on t1 (cost=3084.00..3091.87 rows=1 width=4) (actual time=2.863..5.561 rows=1 loops=1) Recheck Cond: (((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) OR ((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text)) Rows Removed by Index Recheck: 1531 Filter: ((c6 = 'F'::bpchar) AND ((c4 = 45000) OR (c5 = 187))) Heap Blocks: exact=1108 -> BitmapOr (cost=3084.00..3084.00 rows=2 width=0) (actual time=2.529..2.529 rows=0 loops=1) -> Bitmap Index Scan on bl1 (cost=0.00..1542.00 rows=1 width=0) (actual time=1.250..1.250 rows=705 loops=1) Index Cond: ((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) -> Bitmap Index Scan on bl1 (cost=0.00..1542.00 rows=1 width=0) (actual time=1.272..1.272 rows=830 loops=1) Index Cond: ((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) Planning time: 0.177 ms Execution time: 5.613 ms (12 lignes) ... Planning time: 0.182 ms Execution time: 5.459 ms ... Planning time: 0.176 ms Execution time: 5.406 ms EXPLAIN ANALYZE SELECT c1 FROM t1 WHERE (c2 = 'a95f8c4964b850c6040deaedb611cb15' OR c3 = 'a95f8c4964b850c6040deaedb611cb15') AND (c4 = 45000 OR c5::integer = 187) AND c6::character varying= 'F' ; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on t1 (cost=3584.00..3588.03 rows=1 width=4) (actual time=2.647..4.013 rows=1 loops=1) Recheck Cond: ((((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) AND (((c6)::character varying)::text = 'F'::text)) OR (((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) AND (((c6)::character varying)::text = 'F'::text))) Rows Removed by Index Recheck: 685 Filter: ((c4 = 45000) OR ((c5)::integer = 187)) Heap Blocks: exact=583 -> BitmapOr (cost=3584.00..3584.00 rows=1 width=0) (actual time=2.460..2.460 rows=0 loops=1) -> Bitmap Index Scan on bl1 (cost=0.00..1792.00 rows=1 width=0) (actual time=1.215..1.215 rows=321 loops=1) Index Cond: (((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) AND (((c6)::character varying)::text = 'F'::text)) -> Bitmap Index Scan on bl1 (cost=0.00..1792.00 rows=1 width=0) (actual time=1.239..1.239 rows=366 loops=1) Index Cond: (((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) AND (((c6)::character varying)::text = 'F'::text)) Planning time: 0.238 ms Execution time: 4.079 ms (12 lignes) .. Planning time: 0.230 ms Execution time: 3.996 ms .. Planning time: 0.195 ms Execution time: 3.712 ms DROP INDEX bl1; DROP INDEX CREATE INDEX i2 ON t1(c2); CREATE INDEX Temps : 715,342 ms CREATE INDEX i3 ON t1(c3); CREATE INDEX Temps : 708,116 ms CREATE INDEX i4 ON t1(c4); CREATE INDEX Temps : 176,997 ms CREATE INDEX i5 ON t1(c5); CREATE INDEX Temps : 177,198 ms CREATE INDEX i6 ON t1(c6); CREATE INDEX Temps : 259,007 ms postgres=# \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+---------+-------+--------------+-------+---------+------------- public | i2 | index | postgres | t1 | 5792 kB | public | i3 | index | postgres | t1 | 5792 kB | public | i4 | index | postgres | t1 | 2208 kB | public | i5 | index | postgres | t1 | 2208 kB | public | i6 | index | postgres | t1 | 2208 kB | public | t1_pkey | index | postgres | t1 | 2208 kB | (6 lignes) EXPLAIN ANALYZE SELECT c1 FROM t1 WHERE (c2 = 'a95f8c4964b850c6040deaedb611cb15' OR c3 = 'a95f8c4964b850c6040deaedb611cb15') AND (c4 = 45000 OR c5 = 187) AND c6 = 'F' ; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on t1 (cost=8.85..16.72 rows=1 width=4) (actual time=0.065..0.067 rows=1 loops=1) Recheck Cond: (((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) OR ((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text)) Filter: ((c6 = 'F'::bpchar) AND ((c4 = 45000) OR (c5 = 187))) Heap Blocks: exact=1 -> BitmapOr (cost=8.85..8.85 rows=2 width=0) (actual time=0.050..0.050 rows=0 loops=1) -> Bitmap Index Scan on i2 (cost=0.00..4.43 rows=1 width=0) (actual time=0.029..0.029 rows=1 loops=1) Index Cond: ((c2)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) -> Bitmap Index Scan on i3 (cost=0.00..4.43 rows=1 width=0) (actual time=0.015..0.015 rows=0 loops=1) Index Cond: ((c3)::text = 'a95f8c4964b850c6040deaedb611cb15'::text) Planning time: 0.210 ms Execution time: 0.114 ms .. Planning time: 0.188 ms Execution time: 0.107 ms .. Planning time: 0.257 ms Execution time: 0.147 ms DROP INDEX bl1; DROP INDEX TRUNCATE TABLE t1; TRUNCATE TABLE INSERT INTO t1(c2,c3,c4,c5,c6,c7,c8) SELECT lower(md5(random()::text)), lower(md5(random()::text)), trunc(random() * 1000000), trunc(random() * 200), CASE WHEN random() <= 0.55 THEN 'M' ELSE 'F' END, lower(md5(random()::text)), lower(md5(random()::text)) FROM generate_series(1,100000); INSERT 0 100000 Temps : 5860,394 ms .. INSERT 0 100000 Temps : 6701,274 ms .. INSERT 0 100000 Temps : 6858,069 ms UPDATE t1 SET c2 = upper(c2), c3 = upper(c3), c4 = c4 - 1, c5 = c5 + 1, c6 = lower(c6); UPDATE 300000 Temps : 22607,029 ms UPDATE t1 SET c2 = upper(c2), c3 = upper(c3), c4 = c4 - 1, c5 = c5 + 1, c6 = lower(c6); UPDATE 300000 Temps : 21088,527 ms UPDATE t1 SET c2 = upper(c2), c3 = upper(c3), c4 = c4 - 1, c5 = c5 + 1, c6 = lower(c6); UPDATE 300000 Temps : 23787,098 ms DROP INDEX i2; DROP INDEX Temps : 0,547 ms DROP INDEX i3; DROP INDEX Temps : 0,414 ms DROP INDEX i4; DROP INDEX Temps : 0,444 ms DROP INDEX i5; DROP INDEX Temps : 0,466 ms DROP INDEX i6; DROP INDEX Temps : 0,456 ms CREATE INDEX bl1 ON t1 USING BLOOM(c2,c3,c4,cast (c5 as integer), cast (c6 as character varying)); CREATE INDEX Temps : 477,160 ms TRUNCATE TABLE t1; TRUNCATE TABLE Temps : 4,789 ms INSERT INTO t1(c2,c3,c4,c5,c6,c7,c8) SELECT lower(md5(random()::text)), lower(md5(random()::text)), trunc(random() * 1000000), trunc(random() * 200), CASE WHEN random() <= 0.55 THEN 'M' ELSE 'F' END, lower(md5(random()::text)), lower(md5(random()::text)) FROM generate_series(1,100000); INSERT 0 100000 Temps : 4231,385 ms INSERT 0 100000 Temps : 3898,128 ms INSERT 0 100000 Temps : 3917,312 ms UPDATE t1 SET c2 = upper(c2), c3 = upper(c3), c4 = c4 - 1, c5 = c5 + 1, c6 = lower(c6); UPDATE 300000 Temps : 8559,446 ms UPDATE t1 SET c2 = upper(c2), c3 = upper(c3), c4 = c4 - 1, c5 = c5 + 1, c6 = lower(c6); UPDATE 300000 Temps : 8142,606 ms UPDATE t1 SET c2 = upper(c2), c3 = upper(c3), c4 = c4 - 1, c5 = c5 + 1, c6 = lower(c6); UPDATE 300000 Temps : 8633,249 ms

      Que remarque-t-on au niveau du temps d’exécution des requêtes ? Sans indexation, nous obtenons un balayage complet (seq scan) de t1. La requête a un temps d’exécution de plus de 54ms. L’indexation Bloom permet de passer à moins de 6ms voire moins de 4ms en modifiant la requête pour effectuer des conversions explicites. Les index Bloom sont soumis à des restrictions dans les cas d’utilisation et les types de données. Ils ne servent actuellement QUE pour les égalités (=) entre des données entières (INTEGER) et les égalités (=) entre des données texte (CHARACTER VARYING/TEXT). Dans ces conditions l’indexation Bloom est très efficace...mais moins que l’indexation B-Tree qui fait ici passer les temps d’exécution à moins de 0,2ms.
      L’indexation Bloom prend sa revanche sur d’autres aspects. Les index B-Tree supplémentaires pèsent plus de 18Mo alors que la table t1 fait 17Mo. L’index Bloom ne pèse lui que 1,6Mo. Il serait certes possible de créer un index B-Tree composé mais il perdrait son efficacité avec une combinaison différente de critéres omettant les 1ères colonnes, au contraire de l’index Bloom.
      Les performances DML sont également beaucoup moins affectées par la présence de l’index Bloom que par l’ensemble d’index B-Tree. Insérer 100000 lignes avec l’indexation B-Tree en place prend au minimum 5s8 alors qu’elle prend au maximum 4s2 avec l’index Bloom. Le gain est plus spectaculaire dans les mises à jour. 300000 UPDATE de la table t1 prennent moins de 9s avec l’indexation Bloom en place contre plus de 21s avec les B-Tree.
      A l’image des minuscules index BRIN présentés dans cet article, les index Bloom peuvent donc se révéler efficaces s’ils sont utilisés conformémement à ce qu’indique la documenation PostgreSQL.

Mise à jour : 06/11/2016