Comment les index bitmap sont-ils utiles?

Wikipédia donne cet exemple

Identifier    Gender         Bitmaps
                              F    M
1           Female            1    0
2           Male              0    1
3           Male              0    1
4           Unspecified       0    0
5           Female            1    0

Mais je ne comprends pas cette.

  • Comment est-ce un index tout d'abord? Un index n'est-il pas censé pointer vers les lignes (en utilisant les rowid's) étant donné la clé?
  • quelles seraient les requêtes typiques où de tels index seraient utiles? En quoi sont-ils meilleurs que les index de l'arbre B? Je sais que si nous utilisons un index B-tree sur Gender ici, nous allons obtenir beaucoup de résultats si par exemple, nous cherchons pour Gender = Male, qui doivent être filtrés plus loin (donc pas très utile). Comment un Bitmap améliore-t-il la situation?
28
demandé sur Moeb 2010-08-10 22:58:59

3 réponses

Une meilleure représentation d'une image bitmap d'index, est si donné l'exemple ci-dessus:

Identifier    Gender          RowID
1             Female          R1
2             Male            R2
3             Male            R3
4             Unspecified     R4
5             Female          R5

l'index bitmap sur la colonne genre ressemblerait (conceptuellement) à ceci:

Gender       R1    R2   R3   R4   R5
Female       1     0    0    0    1
Male         0     1    1    0    0
Unspecified  0     0    0    1    0

les index Bitmap sont utilisés lorsque le nombre de valeurs distinctes dans une colonne est relativement faible (considérons le contraire où toutes les valeurs sont uniques: l'index bitmap serait aussi large que chaque ligne,et aussi longtemps qu'il s'agit d'une sorte de grande identité matrice.)

donc avec cet index en place une requête comme

SELECT * FROM table1 WHERE gender = 'Male'

la base de données cherche une correspondance dans les valeurs de genre dans l'index, trouve tous les rowids où le bit a été mis à 1, puis va et obtient les résultats de la table.

une requête comme:

SELECT * FROM table1 WHERE gender IN ('Male', 'Unspecified')

obtiendrait le 1 bits pour Mâle, le 1 bits pour non spécifié, faire un bitwise-ou alors aller chercher les lignes où les bits résultants sont 1.

ainsi, les avantages de l'utilisation d'un index bitmap sur un index d'arbre b*sont le stockage (avec une faible cardinalité, les index bitmap sont assez compacts), et la capacité de faire des opérations bitwise avant de résoudre les rowids réels qui peuvent être assez rapide.

notez que les index bitmap peuvent avoir des implications de performance avec les inserts/suppressions (conceptuellement, vous ajoutez/supprimez une colonne de/vers le bitmap et la réajustez en conséquence...), et peut créer un lot entier de contention comme une mise à jour sur une rangée peut verrouiller la totalité de l'entrée bitmap correspondante et vous vous ne pouvez pas mettre à jour une ligne différente (avec la même valeur bitmap) jusqu'à ce que la première mise à jour soit engagée/annulée.

33
répondu Patrick Marchand 2010-08-11 00:00:23

l'avantage vient lors du filtrage sur plusieurs colonnes, alors les index correspondants peuvent être fusionnés avec des opérations bitwise avant de réellement sélectionner les données. Si vous avez le sexe, la couleur de l'œil, la couleur des cheveux alors, la requête

select * from persons where
                      gender = 'male' and 
                      (eye_colour = 'blue' or hair_colour = 'blonde')

ferait d'abord un bitwise ou entre l'index eye_colour['blue'] et l'index hair_colour['blonde'] et finalement bitwise et entre le résultat et l'index gender['male']. Cette opération est très rapide sur le plan de la I / O.

Le flux de bits résultant serait utilisé pour choisir les lignes réelles.

les index Bitmap sont généralement utilisés dans "Star joins" dans les applications d'entrepôt de données.

12
répondu Albin Sunnanbo 2010-08-10 20:33:40

comme indiqué dans L'article de Wikipedia, ils utilisent des opérations bitwise, qui peuvent effectuer mieux que la comparaison de types de données tels que des entiers, de sorte que la réponse courte est la vitesse accrue des requêtes.

théoriquement, cela devrait prendre moins de calculs et moins de temps pour sélectionner tous les hommes ou toutes les femmes de votre exemple.

juste en pensant à la façon dont cela fonctionne sous le capot devrait faire pourquoi c'est plus rapide évident. Un peu est logiquement vrai ou faux. Si vous voulez faites une requête en utilisant une clause WHERE, cela permettra éventuellement d'évaluer soit un true ou un false pour les enregistrements afin de déterminer s'il faut les inclure dans vos résultats.

Préface - le reste de ce qui est censé être laïque sternes et les non-technophile

la question suivante est donc de savoir ce qu'il faut évaluer pour être vrai? Même comparer des valeurs numériques signifie que l'ordinateur doit...

  1. allouer la mémoire pour la valeur que vous voulez evaluer
  2. allouer la mémoire pour la valeur de contrôle
  3. assignez la valeur à chacun (comptez ceci comme deux étapes)
  4. Comparer les deux pour un numérique, cela devrait être rapide, mais pour les chaînes, il y a plus d'octets à comparer.
  5. assignez les résultats à une valeur 0(false) ou 1 (true).

répéter si vous utilisez un multiple de la partie de la clause where comme Où "ce = ce ET qu'="

  1. exécuter au niveau du bit opérations sur les résultats générés dans l'étape 5
  2. trouver la valeur finale
  3. désallouer la mémoire allouée dans les étapes 1 à 3

mais en utilisant la logique bitwise, vous regardez juste les valeurs 0 (false) et 1 (true). 90% des frais généraux pour le travail de comparaison sont éliminés.

4
répondu David 2010-08-10 19:37:32