Dans les articles précédents, nous avons discuté du moteur d'indexation PostgreSQL et de l'interface des méthodes d'accès, ainsi que des index de hachage , des arbres B , GiST , SP-GiST , GIN , RUM et BRIN . Mais nous devons encore examiner les indices Bloom.

Bloom

Concept général

Un filtre Bloom classique est une structure de données qui nous permet de vérifier rapidement l'appartenance d'un élément à un ensemble. Le filtre est très compact, mais autorise les faux positifs: il peut à tort considérer un élément comme membre d'un ensemble (faux positif), mais il n'est pas autorisé de considérer un élément d'un ensemble comme n'étant pas membre (faux négatif) .

Le filtre est un tableau de $$$m$ bits (également appelés signature ) qui sont initialement remplis de zéros. $$$k$ différentes fonctions de hachage sont choisies pour mapper n'importe quel élément de l'ensemble sur $$$k$ morceaux de la signature. Pour ajouter un élément à l'ensemble, nous devons définir chacun de ces bits dans la signature. Par conséquent, si tous les bits correspondant à un élément sont mis à un, l'élément peut être membre de l'ensemble, mais si au moins un bit est égal à zéro, l'élément n'est pas dans l'ensemble à coup sûr.

Dans le cas d'un SGBD, nous avons en fait $$$N$ filtres séparés construits pour chaque ligne d'index. En règle générale, plusieurs champs sont inclus dans l'index, et ce sont les valeurs de ces champs qui composent l'ensemble d'éléments pour chaque ligne.

En choisissant la longueur de la signature $$$m$ , nous pouvons trouver un compromis entre la taille de l'indice et la probabilité de faux positifs. Le domaine d'application de l'index Bloom est de grandes tables significativement "larges" à interroger à l'aide de filtres sur chacun des champs. Cette méthode d'accès, comme BRIN, peut être considérée comme un accélérateur de balayage séquentiel: toutes les correspondances trouvées par l'index doivent être revérifiées avec la table, mais il est possible d'éviter de considérer la plupart des lignes du tout.

La structure

Nous avons déjà discuté des arbres de signature dans le contexte de la méthode d'accès GiST . Contrairement à ces arbres, l'indice Bloom est une structure plate. Il consiste en une métapage suivie de pages régulières avec des lignes d'index. Chaque ligne d'index contient une signature et une référence à une ligne de table (TID), comme illustré schématiquement sur la figure.

Création et choix des valeurs des paramètres

Lors de la création d'un index Bloom, une taille totale de la signature ("longueur") est spécifiée, ainsi que le nombre de bits à définir pour chaque champ individuel inclus dans l'index ("col1" - "col32"):

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...); 

La façon de spécifier le nombre de bits semble étrange: ces nombres doivent être les paramètres d'une classe d'opérateurs plutôt que l'index. Le fait est que les classes d'opérateurs ne peuvent pas être paramétrées à l'heure actuelle, bien que le travail sur ce point soit en cours.

Malheureusement, il n'y a plus de progrès à ce sujet.

Comment choisir des valeurs adaptées? La théorie stipule que compte tenu de la probabilité $$$p$ d'un filtre pour retourner un faux positif, le nombre optimal de bits de signature peut être estimé comme $$$m = −n \ log_2 p / \ ln 2$ , où $$$n$ est le nombre de champs dans l'index et le nombre de bits à définir est $$$k = - \ log_2 p$ .

La signature est stockée à l'intérieur de l'index sous la forme d'un tableau de nombres entiers à deux octets, donc la valeur de $$$m$ peut être arrondi en toute sécurité à $$ .

Lors du choix de la probabilité $$$p$ , nous devons tenir compte de la taille de l'indice, qui sera approximativement égale à $$$(m / 8 + 6) N$ , où $$$N$ est le nombre de lignes du tableau et $$ est la taille du pointeur TID en octets.

Quelques points à noter:

• La probabilité $$$p$ d'un faux positif se rapporte à un filtre, par conséquent, nous nous attendons à obtenir $$$Np$ faux positifs lors de l'analyse de la table (bien sûr, pour une requête qui renvoie peu de lignes). Par exemple, pour une table avec un million de lignes et la probabilité 0,01, dans le plan de requête, en moyenne, nous pouvons nous attendre à "Lignes supprimées par recontrôle d'index: 10000".
• Le filtre Bloom est une structure probabiliste. Il est logique de parler de nombres spécifiques uniquement lorsque la moyenne d'un grand nombre de valeurs, alors que dans chaque cas particulier, nous pouvons obtenir tout ce que nous pouvons penser.
• Les estimations ci-dessus sont basées sur un modèle mathématique idéalisé et quelques hypothèses. En pratique, le résultat risque d'être pire. Alors, ne surestimez pas les formules: elles ne sont qu'un moyen de choisir des valeurs initiales pour de futures expériences.
• Pour chaque champ individuellement, la méthode d'accès nous permet de choisir le nombre de bits à régler. Il existe une hypothèse raisonnable selon laquelle le nombre optimal dépend en fait de la distribution des valeurs dans la colonne. Pour approfondir la plongée, vous pouvez lire cet article (les références à d'autres recherches sont les bienvenues). Mais relisez d'abord l'article précédent.

Mise à jour

Lorsqu'une nouvelle ligne est insérée dans une table, une signature est créée: pour les valeurs de tous les champs indexés, tous leurs bits correspondants sont mis à un. En théorie, nous devons avoir k fonctions de hachage différentes, tandis qu'en pratique, le générateur de nombres pseudo-aléatoires suffit, dont la graine est choisie à chaque fois à l'aide de la seule fonction de hachage.

Un filtre Bloom standard ne prend pas en charge la suppression d'éléments, mais cela n'est pas requis pour l'index Bloom: lorsqu'une ligne de tableau est supprimée, la signature entière est supprimée, ainsi que la ligne d'index.

Comme d'habitude, une mise à jour consiste à supprimer la version de ligne obsolète et à insérer la nouvelle (la signature étant calculée à partir de zéro).

Numérisation

Étant donné que la seule chose que le filtre Bloom peut faire est de vérifier l'appartenance d'un élément dans un ensemble, la seule opération prise en charge par l'index Bloom est une vérification d'égalité (comme dans l'index de hachage).

Comme nous l'avons déjà mentionné, l'indice Bloom est plat, donc au cours de l'accès à l'index, il est toujours lu successivement et entièrement. Au cours de la lecture, un bitmap est construit, qui est ensuite utilisé pour accéder à la table.

Dans un accès à un index normal, il est supposé que peu de lignes d'index devront être lues et, en outre, elles peuvent être bientôt à nouveau nécessaires, par conséquent, elles sont stockées dans un cache tampon. La lecture de l'index Bloom, cependant, est en réalité un balayage séquentiel. Pour éviter d'expulser des informations utiles hors du cache, la lecture se fait via un petit anneau tampon, exactement de la même manière que pour le scan séquentiel des tables.

Il faut tenir compte du fait que plus la taille de l'indice Bloom est importante, moins il semblera attrayant pour le planificateur. Cette dépendance est linéaire, contrairement aux index arborescents.

Exemple

Table

Regardons l'indice Bloom par exemple d'une grande table "vols_bi" de l'article précédent . Pour rappel, la taille de ce tableau est de 4 Go avec environ 30 millions de lignes. Définition du tableau:

 demo=# \d flights_bi 

  Table "bookings.flights_bi" Column | Type | Collation | Nullable | Default --------------------+--------------------------+-----------+----------+--------- airport_code | character(3) | | | airport_coord | point | | | airport_utc_offset | interval | | | flight_no | character(6) | | | flight_type | text | | | scheduled_time | timestamp with time zone | | | actual_time | timestamp with time zone | | | aircraft_code | character(3) | | | seat_no | character varying(4) | | | fare_conditions | character varying(10) | | | passenger_id | character varying(20) | | | passenger_name | text | | | 

Créons d'abord l'extension: bien que l'index Bloom soit inclus dans une livraison standard à partir de la version 9.6, il n'est pas disponible par défaut.

 demo=# create extension bloom; 

La dernière fois, nous avons pu indexer trois champs à l'aide de BRIN ("horaire_programmé", "heure_actuelle", "décalage_aéroport"). Étant donné que les index Bloom ne dépendent pas de l'ordre physique des données, essayons d'inclure presque tous les champs de la table dans l'index. Excluons cependant les champs de temps ("horaire_programmé" et "heure_réelle"): la méthode ne prend en charge que la comparaison pour l'égalité, mais une requête pour l'heure exacte n'est guère intéressante pour personne (nous pourrions cependant construire l'index sur une expression, en arrondissant le à un jour, mais nous ne le ferons pas). Nous devrons également exclure les coordonnées géographiques des aéroports ("airport_coord"): pour l'avenir, le type "point" n'est pas supporté.

Pour choisir les valeurs des paramètres, définissons la probabilité d'un faux positif à 0,01 (en gardant à l'esprit que nous en obtiendrons plus). Les formules ci-dessus pour $$$n = 9$ et $$$N = 30 \, 000 \, 000$ donner la taille de signature de 96 bits et suggérer de définir 7 bits par élément. La taille estimée de l'indice est de 515 Mo (environ un huitième du tableau).

(Avec une taille de signature minimale de 16 bits, les formules promettent une taille d'index deux fois plus petite, mais permettent de s'appuyer uniquement sur la probabilité de 0,5, ce qui est très faible.)

Classes d'opérateur

Essayons donc de créer l'index.

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 ERROR: data type character has no default operator class for access method "bloom" HINT: You must specify an operator class for the index or define a default operator class for the data type. 

Malheureusement, l'extension ne nous fournit que deux classes d'opérateurs:

 demo=# select opcname, opcintype::regtype from pg_opclass where opcmethod = (select oid from pg_am where amname = 'bloom') order by opcintype::regtype::text; 

  opcname | opcintype ----------+----------- int4_ops | integer text_ops | text (2 rows) 

Mais heureusement, il est assez facile de créer des classes similaires pour d'autres types de données également. Une classe d'opérateur pour la méthode d'accès Bloom doit contenir exactement un opérateur - égalité - et exactement une fonction auxiliaire - hachage. Le moyen le plus simple de trouver les opérateurs et les fonctions nécessaires pour un type arbitraire est de consulter le catalogue système pour les classes d'opérateurs de la méthode "hash":

 demo=# select distinct opc.opcintype::regtype::text, amop.amopopr::regoperator, ampr.amproc from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr where am.amname = 'hash' and opc.opcmethod = am.oid and amop.amopfamily = opc.opcfamily and amop.amoplefttype = opc.opcintype and amop.amoprighttype = opc.opcintype and ampr.amprocfamily = opc.opcfamily and ampr.amproclefttype = opc.opcintype order by opc.opcintype::regtype::text; 

  opcintype | amopopr | amproc -----------+----------------------+-------------- abstime | =(abstime,abstime) | hashint4 aclitem | =(aclitem,aclitem) | hash_aclitem anyarray | =(anyarray,anyarray) | hash_array anyenum | =(anyenum,anyenum) | hashenum anyrange | =(anyrange,anyrange) | hash_range ... 

Nous allons créer deux classes manquantes à l'aide de ces informations:

 demo=# CREATE OPERATOR CLASS character_ops DEFAULT FOR TYPE character USING bloom AS OPERATOR 1 =(character,character), FUNCTION 1 hashbpchar; demo=# CREATE OPERATOR CLASS interval_ops DEFAULT FOR TYPE interval USING bloom AS OPERATOR 1 =(interval,interval), FUNCTION 1 interval_hash; 

Une fonction de hachage n'est pas définie pour les points (type "point"), et c'est pour cette raison que nous ne pouvons pas construire d'index Bloom sur un tel champ (tout comme nous ne pouvons pas effectuer de jointure de hachage sur des champs de ce type).

Réessayer:

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 CREATE INDEX 

La taille de l'indice est de 526 Mo, ce qui est un peu plus grand que prévu. En effet, la formule ne prend pas en compte la surcharge de page.

 demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 

  pg_size_pretty ---------------- 526 MB (1 row) 

Requêtes

Nous pouvons maintenant effectuer une recherche en utilisant divers critères, et l'index le supportera.

Comme nous l'avons déjà mentionné, le filtre Bloom est une structure probabiliste, par conséquent, l'efficacité dépend fortement de chaque cas particulier. Par exemple, regardons les rangées relatives à deux passagers, Miroslav Sidorov:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Rows Removed by Index Recheck: 38562 Heap Blocks: exact=21726 -> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Planning time: 0.109 ms Execution time: 3010.736 ms 

et Marfa Soloveva:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 

  QUERY PLAN --------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Rows Removed by Index Recheck: 3950168 Heap Blocks: exact=45757 lossy=67332 -> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Planning time: 0.157 ms Execution time: 10142.730 ms 

Dans un cas, le filtre n'a permis que 40 000 faux positifs et jusqu'à 4 millions dans l'autre ("Rows Removed by Index Recheck"). Les temps d'exécution des requêtes diffèrent en conséquence.

Et voici les résultats de la recherche des mêmes lignes par l'ID du passager plutôt que par son nom. Miroslav:

 demo=# explain(costs off,analyze) demo-# select * from flights_bi where passenger_id='5864 006033'; 

  QUERY PLAN ------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '5864 006033'::text) Rows Removed by Index Recheck: 9620258 Heap Blocks: exact=50510 lossy=165722 -> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) Index Cond: ((passenger_id)::text = '5864 006033'::text) Planning time: 0.110 ms Execution time: 16907.423 ms 

Et marfa:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_id='2461 559238'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '2461 559238'::text) Rows Removed by Index Recheck: 30669 Heap Blocks: exact=27513 -> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) Index Cond: ((passenger_id)::text = '2461 559238'::text) Planning time: 0.120 ms Execution time: 3934.517 ms 

Les rendements diffèrent encore beaucoup, et cette fois Marfa a eu plus de chance.

Notez que la recherche simultanée sur deux champs se fera beaucoup plus efficacement car la probabilité d'un faux positif $$$p$ se transforme en $$$p ^ 2$ :

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV' and passenger_id='5864 006033'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) Recheck Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Rows Removed by Index Recheck: 357 Heap Blocks: exact=356 -> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) Index Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Planning time: 0.524 ms Execution time: 877.967 ms 

Cependant, la recherche avec un booléen "ou" n'est pas du tout prise en charge; il s'agit d'une limitation d'un planificateur plutôt que de la méthode d'accès. Bien sûr, il reste une option pour lire l'index deux fois, créer deux bitmaps et les joindre, mais cela est probablement trop coûteux pour que ce plan soit choisi.

Comparaison avec BRIN et Hash

Les domaines d'application des indices Bloom et BRIN se croisent évidemment. Ce sont de grandes tables pour lesquelles il est souhaitable d'assurer la recherche par différents champs, la précision de recherche étant sacrifiée à la compacité.

Les index BRIN sont plus compacts (par exemple, jusqu'à des dizaines de mégaoctets dans notre exemple) et peuvent prendre en charge la recherche par plage, mais ont une forte limitation liée à l'ordre physique des données dans un fichier. Les index Bloom sont plus grands (des centaines de mégaoctets), mais n'ont pas de limites, sauf la disponibilité d'une fonction de hachage appropriée.

Comme les index Bloom, les index de hachage prennent en charge la seule opération de vérification d'égalité. L'index de hachage garantit une précision de recherche inaccessible pour Bloom, mais la taille de l'index est beaucoup plus grande (dans notre exemple, un gigaoctet pour un seul champ et un index de hachage ne peut pas être créé sur plusieurs champs).

Propriétés

Comme d'habitude, regardons les propriétés de Bloom (des requêtes ont déjà été fournies ).

Voici les propriétés de la méthode d'accès:

  amname | name | pg_indexam_has_property --------+---------------+------------------------- bloom | can_order | f bloom | can_unique | f bloom | can_multi_col | t bloom | can_exclude | f 

Evidemment, la méthode d'accès nous permet de construire un index sur plusieurs colonnes. Cela n'a guère de sens de créer un indice Bloom sur une colonne.

Les propriétés de couche d'index suivantes sont disponibles:

  name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f 

La seule technique de scan disponible est le scan bitmap. Étant donné que l'index est toujours entièrement analysé, il n'est pas logique d'implémenter un accès d'index régulier qui renvoie les lignes TID par TID.

  name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

Seuls les tirets sont ici; la méthode ne peut même pas manipuler les valeurs NULL.

Et enfin:

Il n'est pas impossible que cette série d'articles se poursuive à l'avenir, lorsque de nouveaux types d'indices d'intérêt apparaissent, mais il est temps de s'arrêter maintenant.

Je voudrais exprimer ma gratitude à mes collègues de Postgres Professional (certains d'entre eux sont les auteurs de nombreuses méthodes d'accès discutées) pour avoir lu les ébauches et fourni leurs commentaires. Et je vous suis certainement reconnaissant de votre patience et de vos précieux commentaires. Votre attention m'a encouragé à en arriver là. Je vous remercie!