Index bitmap - Bitmap index

Un index bitmap est un type spécial d' index de base de données qui utilise des bitmaps .

Les index bitmap ont traditionnellement été considérés comme fonctionnant bien pour les colonnes à faible cardinalité , qui ont un nombre modeste de valeurs distinctes, soit absolument, soit par rapport au nombre d'enregistrements contenant les données. Le cas extrême de faible cardinalité est celui des données booléennes (par exemple, un habitant d'une ville a-t-il accès à Internet?), Qui ont deux valeurs, True et False. Les index bitmap utilisent des tableaux de bits (communément appelés bitmaps) et répondent aux requêtes en effectuant des opérations logiques au niveau du bit sur ces bitmaps. Les index bitmap ont un avantage considérable en termes d'espace et de performances par rapport aux autres structures pour l'interrogation de ces données. Leur inconvénient est qu'ils sont moins efficaces que les index B-tree traditionnels pour les colonnes dont les données sont fréquemment mises à jour: par conséquent, ils sont plus souvent utilisés dans des systèmes en lecture seule spécialisés pour les requêtes rapides - par exemple, les entrepôts de données, et généralement inadaptés pour applications de traitement des transactions en ligne .

Certains chercheurs affirment que les index bitmap sont également utiles pour les données de cardinalité modérée ou même élevée (par exemple, des données à valeur unique) auxquelles on accède en lecture seule, et que les requêtes accèdent à plusieurs colonnes indexées bitmap à l'aide de AND , OR ou XOR. opérateurs largement.

Les index bitmap sont également utiles dans les applications d' entreposage de données pour joindre une grande table de faits à des tables de dimension plus petites telles que celles organisées dans un schéma en étoile .

Exemple

Poursuivant l'exemple d'accès à Internet, un index bitmap peut être logiquement visualisé comme suit:

Identifiant HasInternet Bitmaps
Oui N
1 Oui 1 0
2 Non 0 1
3 Non 0 1
4 Non spécifié 0 0
5 Oui 1 0

Sur la gauche, Identifier fait référence au numéro unique attribué à chaque résident, HasInternet est les données à indexer, le contenu de l'index bitmap est affiché sous forme de deux colonnes sous l'en-tête bitmaps . Chaque colonne de l'illustration de gauche est une image bitmap dans l'index bitmap. Dans ce cas, il existe deux bitmaps de ce type, un pour "a Internet" Oui et un pour "a Internet" Non . Il est facile de voir que chaque bit du bitmap Y montre si une ligne particulière fait référence à une personne qui a accès à Internet. Il s'agit de la forme la plus simple d'index bitmap. La plupart des colonnes auront des valeurs plus distinctes. Par exemple, le montant des ventes est susceptible d'avoir un nombre beaucoup plus grand de valeurs distinctes. Les variations de l'index bitmap peuvent également indexer efficacement ces données. Nous passons brièvement en revue trois de ces variantes.

Remarque: De nombreuses références citées ici sont examinées dans ( John Wu (2007) ). Pour ceux qui pourraient être intéressés à expérimenter certaines des idées mentionnées ici, beaucoup d'entre elles sont implémentées dans des logiciels open source tels que FastBit, la bibliothèque C ++ d'index Bitmap Lemur, la bibliothèque Java Roaring Bitmap et le système Apache Hive Data Warehouse.

Compression

Pour des raisons historiques, la compression bitmap et la compression de liste inversée ont été développées comme des lignes de recherche distinctes, et ce n'est que plus tard qu'elles ont été reconnues comme résolvant essentiellement le même problème.

Le logiciel peut compresser chaque bitmap dans un index bitmap pour économiser de l'espace. Il y a eu un travail considérable sur ce sujet. Bien qu'il existe des exceptions telles que les bitmaps rugissants, les algorithmes de compression Bitmap utilisent généralement un codage de longueur d'exécution , tel que le code bitmap aligné sur les octets, le code hybride aligné sur les mots, la compression PWAH (Partitioned Word-Aligned Hybrid), le mot de la liste de positions Aligned Hybrid, l'indice adaptatif compressé (COMPAX), Enhanced Word-Aligned Hybrid (EWAH) et le COmpressed 'N' Composable Integer SEt. Ces méthodes de compression nécessitent très peu d'efforts pour compresser et décompresser. Plus important encore, les bitmaps compressés avec BBC, WAH, COMPAX, PLWAH, EWAH et CONCISE peuvent directement participer à des opérations au niveau du bit sans décompression. Cela leur donne des avantages considérables par rapport aux techniques de compression génériques telles que LZ77 . La compression BBC et ses dérivés sont utilisés dans un système de gestion de base de données commerciale . BBC est efficace à la fois pour réduire la taille des index et maintenir les performances des requêtes . BBC encode les bitmaps en octets , tandis que WAH encode en mots, ce qui correspond mieux aux processeurs actuels . "Sur les données synthétiques et les données d'application réelles, les nouveaux schémas d'alignement de mots n'utilisent que 50% d'espace en plus, mais effectuent des opérations logiques sur des données compressées 12 fois plus rapidement que BBC." Il a été rapporté que les bitmaps PLWAH occupent 50% de l'espace de stockage consommé par les bitmaps WAH et offrent des performances jusqu'à 20% plus rapides sur les opérations logiques . Des considérations similaires peuvent être faites pour CONCISE et Enhanced Word-Aligned Hybrid.

Les performances des schémas tels que BBC, WAH, PLWAH, EWAH, COMPAX et CONCISE dépendent de l'ordre des lignes. Un simple tri lexicographique peut diviser la taille de l'index par 9 et rendre les index plusieurs fois plus rapides. Plus le tableau est grand, plus il est important de trier les lignes. Des techniques de remaniement ont également été proposées pour obtenir les mêmes résultats de tri lors de l'indexation de données en continu.

Codage

Les index bitmap de base utilisent un bitmap pour chaque valeur distincte. Il est possible de réduire le nombre de bitmaps utilisés en utilisant une méthode de codage différente . Par exemple, il est possible de coder des valeurs distinctes C en utilisant des bitmaps log (C) avec un codage binaire .

Cela réduit le nombre de bitmaps, économise encore plus d'espace, mais pour répondre à n'importe quelle requête, il faut accéder à la plupart des bitmaps. Cela le rend potentiellement moins efficace que le balayage d'une projection verticale des données de base, également appelée vue matérialisée ou indice de projection. Trouver la méthode de codage optimale qui équilibre les performances (arbitraires) des requêtes, la taille de l'index et la maintenance de l'index reste un défi.

Sans considérer la compression, Chan et Ioannidis ont analysé une classe de méthodes de codage multi-composants et sont parvenus à la conclusion que le codage à deux composants se situe au coude de la courbe performance / taille de l'indice et représente donc le meilleur compromis entre la taille de l'index et performances des requêtes.

Binning

Pour les colonnes à cardinalité élevée, il est utile de regrouper les valeurs, où chaque casier couvre plusieurs valeurs et de créer les bitmaps pour représenter les valeurs dans chaque casier. Cette approche réduit le nombre de bitmaps utilisés quelle que soit la méthode de codage. Cependant, les index regroupés ne peuvent répondre qu'à certaines requêtes sans examiner les données de base. Par exemple, si un bac couvre la plage de 0,1 à 0,2, alors lorsque l'utilisateur demande toutes les valeurs inférieures à 0,15, toutes les lignes qui tombent dans le bac sont des hits possibles et doivent être vérifiées pour vérifier si elles sont réellement inférieures à 0,15 . Le processus de vérification des données de base est connu sous le nom de vérification des candidats. Dans la plupart des cas, le temps utilisé par la vérification des candidats est nettement plus long que le temps nécessaire pour travailler avec l'index bitmap. Par conséquent, les index regroupés présentent des performances irrégulières. Ils peuvent être très rapides pour certaines requêtes, mais beaucoup plus lents si la requête ne correspond pas exactement à un chutier.

Histoire

Le concept d'index bitmap a été introduit pour la première fois par le professeur Israel Spiegler et Rafi Maayan dans leur recherche "Storage and Retrieval Considerations of Binary Data Bases", publiée en 1985. Le premier produit de base de données commercial à implémenter un index bitmap était le modèle 204 de Computer Corporation of America . Patrick O'Neil a publié un article sur cette implémentation en 1987. Cette implémentation est un hybride entre l'index bitmap de base (sans compression) et la liste des identificateurs de ligne (liste RID). Dans l'ensemble, l'index est organisé sous la forme d'un arbre B + . Lorsque la cardinalité de la colonne est faible, chaque nœud feuille de l'arbre B contiendrait une longue liste de RID. Dans ce cas, il faut moins d'espace pour représenter les listes RID sous forme de bitmaps. Étant donné que chaque bitmap représente une valeur distincte, il s'agit de l'index bitmap de base. Au fur et à mesure que la cardinalité des colonnes augmente, chaque bitmap devient clairsemé et il peut prendre plus d'espace disque pour stocker les bitmaps que pour stocker le même contenu que les listes RID. Dans ce cas, il bascule pour utiliser les listes RID, ce qui en fait un index d' arborescence B + .

Bitmaps en mémoire

L'une des raisons les plus fortes de l'utilisation des index bitmap est que les résultats intermédiaires produits à partir de ceux-ci sont également des bitmaps et peuvent être réutilisés efficacement dans d'autres opérations pour répondre à des requêtes plus complexes. De nombreux langages de programmation prennent en charge cela comme une structure de données de tableau de bits. Par exemple, Java a la BitSet classe.

Certains systèmes de base de données qui n'offrent pas d'index bitmap persistant utilisent des bitmaps en interne pour accélérer le traitement des requêtes. Par exemple, les versions 8.1 et ultérieures de PostgreSQL implémentent une optimisation de «balayage d'index bitmap» pour accélérer les opérations logiques arbitrairement complexes entre les index disponibles sur une seule table.

Pour les tables avec de nombreuses colonnes, le nombre total d'index distincts pour satisfaire toutes les requêtes possibles (avec des conditions de filtrage d'égalité sur l'un ou l'autre des champs) augmente très rapidement, étant défini par cette formule:

.

Une analyse d'index bitmap combine des expressions sur différents index, ce qui ne nécessite qu'un seul index par colonne pour prendre en charge toutes les requêtes possibles sur une table.

L'application de cette stratégie d'accès aux index B-tree peut également combiner des requêtes de plage sur plusieurs colonnes. Dans cette approche, un bitmap en mémoire temporaire est créé avec un bit pour chaque ligne du tableau (1  Mo peut ainsi stocker plus de 8 millions d'entrées). Ensuite, les résultats de chaque index sont combinés dans le bitmap à l'aide d' opérations au niveau du bit . Une fois toutes les conditions évaluées, le bitmap contient un "1" pour les lignes correspondant à l'expression. Enfin, le bitmap est parcouru et les lignes correspondantes sont récupérées. En plus de combiner efficacement les index, cela améliore également la localité de référence des accès aux tables, car toutes les lignes sont extraites séquentiellement à partir de la table principale. Le bitmap interne est ignoré après la requête. S'il y a trop de lignes dans le tableau pour utiliser 1 bit par ligne, un bitmap «avec perte» est créé à la place, avec un seul bit par page de disque. Dans ce cas, le bitmap est simplement utilisé pour déterminer les pages à récupérer; les critères de filtre sont ensuite appliqués à toutes les lignes des pages correspondantes.

Les références

Remarques
Bibliographie