bloom fournit une méthode d'accès aux index basée sur les filtres Bloom.
Un filtre Bloom est une structure de données efficace en terme d'espace disque, utilisée pour tester si un élément fait partie d'un ensemble. Dans le cas d'une méthode d'accès aux index, il permet une exclusion rapide des lignes ne correspondant pas à la recherche via des signatures dont la taille est déterminée lors de la création de l'index.
Une signature est une représentation avec perte des attributs indexé(s) et, de ce fait, est sujet à renvoyer des faux positifs ; c'est-à-dire qu'il peut indiquer à tort qu'un élément fait partie d'un ensemble. De ce fait, les résultats d'une recherche doivent toujours être vérifiés en utilisant les valeurs réelles des attributs de la ligne dans la table. Des signatures plus larges réduisent les risques de faux positifs et réduisent donc le nombre de visites inutiles à la table. Bien sûr, l'index est plus volumineux et donc plus lent à parcourir.
Ce type d'index est principalement utile quand une table a de nombreux attributs et que les requêtes en testent des combinaisons arbitraires. Un index btree traditionnel est plus rapide qu'un index bloom mais il en faut généralement plusieurs pour supporter toutes les requêtes que gèrerait un seul index bloom. Noter que les index bloom ne supportent que les recherches par égalité, là où les index btree peuvent aussi réaliser des recherches d'inégalité et d'intervalles.
Un index bloom accepte les paramètres suivants dans sa clause WITH :
Longueur de chaque signature (enregistrement dans l'index) en bits. La valeur par défaut est de 80 et le maximum est 4096.
Nombre de bits générés pour chaque colonne d'index. Le nom de chaque paramètre fait référence au numéro de la colonne d'index qu'il contrôle. La valeur par défaut est 2 bits et le maximum 4095. Les paramètres pour les colonnes d'index non utilisées sont ignorés.
Voici un exemple de création d'un index bloom :
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
WITH (length=80, col1=2, col2=2, col3=4);
L'index est créé avec une longueur de signature de 80 bits, avec les attributs i1 et i2 correspondant à 2 bits, et l'attribut i3 à 4 bits. Nous pourrions avoir omis les informations length, col1, et col2 car elles ont les valeurs par défaut.
Voici un exemple plus complet de définition et d'utilisation d'un index bloom, ainsi qu'une comparaison avec les index btree équivalents. L'index bloom est considérablement plus petit que l'index btree et offre de meilleures performances.
=# CREATE TABLE tbloom AS
SELECT
(random() * 1000000)::int as i1,
(random() * 1000000)::int as i2,
(random() * 1000000)::int as i3,
(random() * 1000000)::int as i4,
(random() * 1000000)::int as i5,
(random() * 1000000)::int as i6
FROM
generate_series(1,10000000);
SELECT 10000000
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
pg_size_pretty
----------------
153 MB
(1 row)
=# CREATE index btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
387 MB
(1 row)
Un parcours séquentiel sur cette grande table prend beaucoup de temps :
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..213694.08 rows=1 width=24) (actual time=1445.438..1445.438 rows=0 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Planning time: 0.177 ms
Execution time: 1445.473 ms
(5 rows)
En général, l'optimiseur sélectionnera un parcours d'index si c'est possible. Avec un index btree, nous obtenons ceci :
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Index Only Scan using btreeidx on tbloom (cost=0.56..298311.96 rows=1 width=24) (actual time=445.709..445.709 rows=0 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Heap Fetches: 0
Planning time: 0.193 ms
Execution time: 445.770 ms
(5 rows)
Bloom est meilleur que btree pour gérer ce type de recherche :
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=178435.39..178439.41 rows=1 width=24) (actual time=76.698..76.698 rows=0 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 2439
Heap Blocks: exact=2408
-> Bitmap Index Scan on bloomidx (cost=0.00..178435.39 rows=1 width=0) (actual time=72.455..72.455 rows=2439 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Planning time: 0.475 ms
Execution time: 76.778 ms
(8 rows)
Noter le nombre relativement important de faux positifs : 2349 lignes ont été sélectionnées pour vérification dans la table, mais aucune ne correspondait au filtre de la requête. Nous pouvons réduire cela en spécifiant une longueur de signature plus importante. Dans cet exemple, créer l'index avec length=200 a réduit le nombre de faux positifs à 55 mais doublé la taille de l'index (306 Mo) et s'est révélé plus lent pour cette requête (125 ms en tout).
Le problème principal avec la recherche btree est que btree est inefficace quand les critères de recherche ne portent pas sur la ou les premières colonne(s) de l'index. Une meilleure stratégie avec les btree est de créer un index séparé pour chaque colonne. À ce moment-là, l'optimiseur pourra choisir quelque chose comme :
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.148..0.148 rows=0 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.145..0.145 rows=0 loops=1)
-> Bitmap Index Scan on tbloom_i5_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.089..0.089 rows=10 loops=1)
Index Cond: (i5 = 123451)
-> Bitmap Index Scan on tbloom_i2_idx (cost=0.00..4.52 rows=11 width=0) (actual time=0.048..0.048 rows=8 loops=1)
Index Cond: (i2 = 898732)
Planning time: 2.049 ms
Execution time: 0.280 ms
(9 rows)
Bien que cette requête soit bien plus rapide qu'avec n’importe lequel des index à une colonne, nous payons une large pénalité en taille d'index. Chacun des index btree mono-colonne occupe 214 Mo, soit un espace total de plus de 1,2 Go, autrement dit huit fois la place utilisée par l'index bloom.
Une classe d'opérateur pour les index bloom ne requiert qu'une fonction de hachage pour le type de données indexé et un opérateur d'égalité pour la recherche. Cet exemple définit la classe d'opérateur pour le type de données text :
CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
OPERATOR 1 =(text, text),
FUNCTION 1 hashtext(text);
Seules les classes d'opérateur pour int4 et text sont incluses avec le module.
Seul l'opérateur = est supporté pour la recherche. Mais il est possible d'ajouter le support des tableaux avec les opérations union et intersection dans le futur.
Teodor Sigaev <teodor@postgrespro.ru>, Postgres Professional, Moscou, Russie
Alexander Korotkov <a.korotkov@postgrespro.ru>, Postgres Professional, Moscou, Russie
Oleg Bartunov <obartunov@postgrespro.ru>, Postgres Professional, Moscou, Russie
auto_explain
