GoSuda

Motif bitmap vif

By snowmerak views ...

Qu'est-ce qu'un bitmap ?

Ici, le bitmap désigne un type d'index. Si vous êtes arrivé ici en pensant à la graphique, vous pouvez revenir en arrière.

Concept de base

Le bitmap est une technique d'indexation des bases de données. Il représente les valeurs d'une colonne sous la forme d'un tableau de bits ou d'un élément de vecteur, où chaque bit indique si une valeur spécifique de cette colonne existe. Ainsi, la forme la plus élémentaire consiste à attribuer un index binaire à chaque row et à représenter la présence ou l'absence d'une valeur par 0 et 1.

Par exemple, supposons qu'il existe une table comportant une colonne de sexe. Supposons que cette table contienne 5 rows et que les valeurs de la colonne de sexe soient les suivantes :

  1. Homme
  2. Femme
  3. Homme
  4. Femme
  5. Autre

Dans ce cas, l'index bitmap de la colonne de sexe peut être représenté comme suit :

  • Homme : 10100
  • Femme : 01010
  • Autre : 00001

Alors, à quoi sert-il réellement ?

Vous penserez sans doute que le bitmap ne sert pas simplement à représenter ces données. Pour bien comprendre son utilisation, considérons le cas suivant.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Supposons que cette table contienne 1 000 000 de rows. Supposons ensuite que l'on exécute la requête suivante.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Cette requête recherche les rows dont les colonnes active et sex sont toutes deux égales à TRUE. Pour trouver le plus rapidement les rows satisfaisant cette double condition, on peut utiliser l'opération bit and.

  • L'index bitmap de la colonne active est indexé à l'avance sous la forme 1100110011... (tableau de 1 000 000 bits),
  • l'index bitmap de la colonne sex est indexé à l'avance sous la forme 1010101010... (tableau de 1 000 000 bits).

En effectuant l'opération bit and sur ces deux index bitmap, on peut rapidement trouver les rows dont les deux colonnes sont TRUE. Comme il s'agit d'une simple opération binaire, on obtient le résultat beaucoup plus rapidement qu'avec d'autres analyses d'index.

Compromis

Les index bitmap peuvent être très efficaces, mais ils présentent certains compromis. Il existe de nombreux autres inconvénients, mais je n'en évoquerai qu'un seul pour l'instant.

Il s'agit de la cardinality : les index bitmap conviennent mieux aux faibles cardinality (c'est-à-dire lorsque le nombre de valeurs possibles dans une colonne est réduit). L'utilisation d'un index bitmap sur une colonne à forte cardinality peut entraîner une taille de bitmap très importante.

Lorsqu'un index bitmap est utilisé sur une colonne à forte cardinality, il faut générer un bitmap distinct pour chaque valeur unique, ce qui peut nécessiter beaucoup d'espace de stockage. Par exemple, si une colonne contient 1 000 000 de valeurs uniques, il faut générer 1 000 000 de bitmaps, ce qui peut être extrêmement inefficace.

Notre solution

On peut remplacer les bitmaps issus des fortes cardinality par une structure appelée Roaring Bitmap. Roaring Bitmap possède de nombreuses caractéristiques, mais sa philosophie et sa propriété fondamentales sont sélectionner dynamiquement la méthode de stockage la plus adaptée en fonction de la densité des données, afin de maximiser à la fois le taux de compression et la vitesse des opérations.

Concept de base de Roaring Bitmap

Indexation en deux niveaux

Roaring Bitmap passe d'abord par les deux étapes suivantes pour stocker un entier. Bien qu'il s'agisse d'une indexation en deux niveaux, il suffit de considérer cela comme un simple tableau à deux dimensions.

  • Extraction des 16 bits supérieurs : on extrait les 16 bits supérieurs de l'entier et on les utilise comme index. Il s'agit de l'index du tableau externe, parmi un tableau à deux dimensions d'une longueur totale de 65536. Ce tableau stocke l'adresse du conteneur décrit plus loin.
  • Extraction des 16 bits inférieurs : on extrait les 16 bits inférieurs de l'entier et on les utilise comme position à l'intérieur du conteneur.

Conteneur

Ce conteneur correspond, comme nous venons de l'expliquer par analogie, au tableau interne du tableau à deux dimensions. Contrairement au tableau des 16 bits supérieurs, la structure interne de ce conteneur varie selon la quantité de données qu'il contient. Roaring Bitmap prend en charge les 3 conteneurs suivants.

  • Array Container : ce conteneur est utilisé lorsque les données stockées sont peu nombreuses. Plus précisément, il est utilisé pour stocker 4096 éléments ou moins. Il est implémenté sous la forme d'un simple tableau d'entiers trié. Les éléments peuvent être recherchés par recherche dichotomique.
  • Bitmap Container : ce conteneur est utilisé lorsque les données stockées sont nombreuses. Plus précisément, il est utilisé pour stocker plus de 4096 éléments. Il est implémenté sous la forme d'un bitmap de 65536 bits (8192 octets). Chaque bit indique si l'entier correspondant à cette position existe.
  • Run Container : ce conteneur est utilisé pour stocker des plages d'entiers consécutifs. Par exemple, il est efficace pour stocker des entiers consécutifs tels que 1, 2, 3, 4, 5. Il est implémenté sous la forme d'une liste de paires (valeur de départ, longueur). Et si tout est présent ? Cela signifie simplement que tous les éléments, du début à la fin, sont présents ; il suffit donc de stocker une seule paire (0, 65536).

Cette méthode permet à Roaring Bitmap d'utiliser la mémoire de manière très efficace et de fournir des performances optimales pour différentes densités de données.

Fonctionnalités de Roaring Bitmap

Fonctionnalités de base

Roaring Bitmap fournit les fonctionnalités de base suivantes.

  • Insertion : ajoute un nouvel entier au bitmap. Au cours de ce processus, le conteneur approprié peut être sélectionné ou, si nécessaire, converti.
  • Suppression : retire un entier existant du bitmap. Là encore, un traitement approprié est effectué selon l'état du conteneur.
  • Recherche : vérifie si un entier spécifique existe dans le bitmap. Cette opération est exécutée très rapidement.

Opérations ensemblistes

Roaring Bitmap prend également en charge les opérations ensemblistes suivantes.

  • Union : crée un nouveau bitmap contenant tous les éléments des deux bitmaps.
  • Intersection : crée un nouveau bitmap ne contenant que les éléments présents dans les deux bitmaps.
  • Symmetric Difference : crée un nouveau bitmap contenant les éléments présents dans un seul des deux bitmaps.

Ces opérations sont optimisées selon le type de conteneur et sont exécutées très rapidement.

En Go

En Go, il est possible d'utiliser facilement Roaring Bitmap grâce au package github.com/RoaringBitmap/roaring. Ce package fournit l'ensemble des fonctionnalités de Roaring Bitmap et est optimisé selon les caractéristiques du langage Go.

Installation

1go get github.com/RoaringBitmap/roaring/v2

Exemple d'utilisation

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Initialisation avec 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialisation avec 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Ajout de 5
14	b2.Add(10) // Ajout de 10
15
16	b2.Remove(12) // Suppression de 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Les opérations sur bitmap modifient l'original, on utilise donc une copie
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Parmi les principales fonctionnalités qui ne figurent pas dans l'exemple de code ci-dessus :

  • Contains(x uint32) bool : vérifie si une valeur spécifique existe dans le bitmap
  • GetCardinality() uint64 : renvoie le nombre d'éléments contenus dans le bitmap
  • Rank(x uint32) uint64 : renvoie le nombre d'éléments inférieurs ou égaux à une valeur spécifique
  • ToBytes() ([]byte, error) : sérialise le bitmap en slice d'octets
  • FromBytes(data []byte) error : restaure le bitmap à partir d'un slice d'octets
  • Clone() *Bitmap : crée une copie du bitmap
  • Clear() : réinitialise le bitmap
  • NextValue(x uint32) int64 : renvoie le prochain élément supérieur ou égal à x
  • PreviousValue(x uint32) int64 : renvoie l'élément précédent inférieur à x ou
  • Maximum() uint32 : renvoie le plus grand élément du bitmap
  • Minimum() uint32 : renvoie le plus petit élément du bitmap

Ces fonctionnalités sont disponibles. Pour plus de détails, consultez la documentation officielle.

À titre de référence, le package roaring inclut également un package prenant en charge non seulement uint32, mais aussi uint64. Il offre une interface presque identique, ce qui permet de l'utiliser en le remplaçant directement.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Initialisation avec 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialisation avec 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Ajout de 5
14	b2.Add(10) // Ajout de 10
15
16	b2.Remove(12) // Suppression de 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Les opérations sur bitmap modifient l'original, on utilise donc une copie
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Conclusion

Roaring Bitmap est un outil puissant pour stocker et manipuler efficacement des ensembles d'entiers à forte cardinality. En Go, l'utilisation du package github.com/RoaringBitmap/roaring permet d'exploiter facilement l'ensemble des fonctionnalités de Roaring Bitmap. Grâce à ses différents types de conteneurs et à ses opérations optimisées, ce package maximise l'utilisation de la mémoire et les performances. Roaring Bitmap peut être utilisé dans de nombreux domaines, tels que l'indexation de bases de données, l'analyse de logs ou le calcul statistique, pour mettre en œuvre un traitement de données efficace.

Roaring Bitmap se révèle particulièrement performant sur les grands ensembles de données et peut être utile dans de nombreuses applications. Associé à la syntaxe concise et efficace du langage Go, il offre aux développeurs un outil puissant. On peut s'attendre à ce que Roaring Bitmap gagne encore en fonctionnalités et en optimisations à mesure de son développement.

Pourquoi ai-je fait cela ? C'était pour l'indexation par tag et les opérations d'union rapides dans une base de données de séries temporelles.