Les index pour les entrepôts de données : comparaison entre

index arbre-B et Bitmap

El Amin Aoulad Abdelouarit - Faculté des sciences de Tétouan – [email protected]

Mohamed Merouani – Faculté poly disciplinaire de Tétouan – [email protected]

Résumé — Avec le développement des systèmes Abstract— With the development of decision
de décisionnel en générale et les entrepôts de systems and specially data warehouses, the
données de manière particulière, il est devenu visibility of the data warehouse design before its
primordiale d’avoir une visibilité de la creation has become essential, and that because
conception de l’entrepôt de données avant sa of data warehouse importance as considered as
création, et cela vu l’importance de l’entrepôt de the unique data source giving meaning to the
données qui se considère la source unique des decision. In a decision system the proper
données donnant sens à la décision. Dans un functioning of a data warehouse resides in the
système de décisionnel, le bon fonctionnement smooth running of the middleware tools ETC
d’un entrepôt de données réside dans le bon step one hand, and the restitution step through
déroulement de l’étape intergicielle des outils the data mining, reporting solutions,
ETC d’une part, et l’étape de restitution via le dashboards… etc other. The large volume of data
Datamining, des progiciels de reporting, des that passes through these stages require an
tableaux de bords…etc d’autre part. La grande optimal design for a highly efficient decision
volumétrie des données qui passes par ces étapes system, without disregarding the choice of
exigent une conception optimale pour un système technologies that are introduced for the data
de décisionnel très performant, sans négliger le warehouse implementation such as: database
choix des technologies y introduit pour la mise en management system, the type of server operating
place d’un entrepôt de données tel que : le systems, physical server architecture (64-bit, for
système de gestion de base de données, la nature example) that can be a benefit performance of
des systèmes d’exploitations du serveur, this system. The designer of the data warehouse
l’architecture physique des serveurs (64 bits par should consider the effectiveness of data query,
exemple) qui peuvent être un avantage de this depends on the selection of relevant indexes
performance du dit système. Le concepteur de and their combination with the materialized
l’entrepôt de données devra prendre en views, note that the index selection is a NP-
considération l’efficacité de l’interrogation des complete problem, because the number of indexes
données, cette efficacité repose sur la sélection is exponential in the total number of attributes in
d’index pertinents et leur combinaison avec les the database, So, it is necessary to provide, while
vues matérialisé, à noter que La sélection d’index the data warehouse design, the suitable type of
est un problème NP-complet car le nombre index for this data warehouse.
d’index est exponentiel en nombre total
d’attributs dans la base, il faut donc prévoir, lors This paper presents a comparative study between
de la conception d’un entrepôt de données, le type the index B-tree type and type Bitmap, their
d’index convenable à cet entrepôt. advantages and disadvantages, with a real
experiment showing that its index of type Bitmap
Cet article présente une étude comparative sur more advantageous than the index B-tree type.
entre les index de type arbre B et de type Bitmap,
leurs avantages et inconvénients, avec une Keywords: Data Warehouse DBMS, indexes,
expérimentation réelle démontrant que les index business intelligence.
de type Bitmap son plus avantageux que les index
de type arbre-B.

Mots clés : Entrepôt de données, SGBD, index,

business intelligence.
 I- Introduction sur des bits, d’où son faible coût en terme d’espace
occupé. [7] Toutes les valeurs possibles de l’attribut
L’administrateur de l’entrepôt de données prend sont considérées, que la valeur soit présente ou non
plusieurs décisions concernant ses tâches dans la table. A chacune de ces valeurs correspond
d’administration, telle que la conception logique ou un tableau de bits, appelé bitmap, qui contient autant
physique des bases de données, la gestion de de bits que de n-uplets présents dans la table. Ainsi,
l’espace de stockage et le réglage des performances ce type d’index est très efficace lorsque les attributs
(performance tuning). La plus importantes tâche est ont un faible nombre de valeurs distinctes. Chaque
la conception physique des bases de données, qui bit représente donc la valeur d’un attribut, pour un n-
inclut l’organisation des données et l’amélioration uplet donné. Pour chacun des bits, il y a un codage
de l’accès à ces données. Pour améliorer les temps de présence/absence (1/0), ce qui traduit le fait qu’un
d'accès, l'administrateur emploie en général des n-uplet présente ou non la valeur caractérisée par le
index pour rechercher rapidement les informations bitmap.
nécessaires à une requête sans parcourir toutes les
données [1],[3],[7]. La sélection d'index est difficile
car leur nombre est exponentiel en nombre total
d'attributs dans la base. Donc l’index joue un rôle
important dans la performance des bases de données,
ROWID C B0 B1 B2 B3
c’est pourquoi nous nous intéressons à cet élément 0 2 0 0 1 0
de l’entrepôt de donnée, qui ce considère le centre 1 1 0 1 0 0
d’intérêt du concepteur lors de l’édition et 2 3 0 0 0 1
l’optimisation des requêtes de sélection. L’objectif 3 0 1 0 0 0
est de minimiser le temps d’exécution des requêtes, 4 3 0 0 0 1
et tant que les requêtes dans un entrepôt de données 5 1 0 1 0 0
se basent sur les index, nous allons travailler sur le 6 0 1 0 0 0
problème du choix de type d’index lors de la 7 0 1 0 0 0
conception de notre entrepôt de données. Il existe 8 2 0 0 1 0
Tableau 1 Bitmap basic adopté par [10]
plusieurs types d’index pris en charge par les bases
de données tel que Bitmap [4] , Arbre-B [3], [6], [7],
[9], Bitmap de jointure[10], range-based bitmap
index [11]etc. Dans ce sens nous avons choisis deux
types d’index par pertinence pour cette étude,
l’index de type : Arbre-B et index de type Bitmap.

Cet article est répartit comme suit, après la Pour illustrer le fonctionnement d’un index Bitmap
présentation du contexte et les travaux liés avec on prend un exemple E.E-O’Neil et P.P-O’Neil [12].
(section 2), puis une présentation des hypothèses « Table 1 illustre un index de type bitmap basic dans
(section 3) une expérimentation sera réalisé pour une table contenant 9 enregistrements, où l’index est
déterminer des résultats concrets (section 4). Nous créé dans la colonne C avec des entiers allant de 0 à
terminons par une conclusion et des perspectives de 3, on dit que la cardinalité de la colonne C est 4, par
recherches (section 5) ce que on a 4 valeurs distincts [0, 1, 2, 3], d’où
l’index bitmap de C contiens 4 Bitmaps indiqués
II- Présentation de l’axe de comme B0, B1, B2 et B3 correspondant la valeur
recherche representé. Dans cet exemple, la première ligne où
RowID=0, la colonne C est de valeur 2, par
1. Index Bitmap conséquence, la colonne B2 est de valeur de bit
« 1 », pendant que les autres bitmaps sont mis à
1.1 Définition et exemple: « 0 ». Même chose pour la ligne suivante, où C=1
qui correspond à que le bitmap B1 est mis sur 1 et le
Un index bitmap est une structure de données reste à « 0 ». Ce processus se répète pour le reste des
définie dans un SGBD, utilisée pour optimiser lignes. [12]
l’accès aux données dans les bases de données. C’est
un type d’indexation qui est particulièrement
intéressant et performant dans le cadre des requêtes
de sélection. L’index bitmap d’un attribut est codé
 1.2 Propriétés : la relation. Cette hypothèse n'est pas tout à fait exacte,
cependant. En réalité, un index bitmap est toujours
Les index bitmap possèdent une propriété très conseillé pour les systèmes dans lesquels les données ne
intéressante qui consiste à répondre à certains types sont pas souvent mises à jour par de nombreux systèmes
de requêtes sans retourner aux données elles-mêmes, concurrents. En fait, comme je vais démontrer ici, un
optimisant ainsi les temps de réponse. Cela est index bitmap sur une colonne avec des valeurs uniques
possible grâce aux opérations de comptage à 100% (un candidat de la colonne de clé primaire) est
(COUNT) et aux opérateurs logiques (AND, OR, aussi efficace qu'un index de B-arbre.
etc) qui agissent "bit à bit" sur les bitmaps.
Dans cet article je vais vous donner quelques
2. Index B-Arbre exemples, ainsi que les décisions de l'optimiseur, qui
sont communs aux deux types d'index sur une colonne
2.1 Définition de faible cardinalité ainsi qu'une grande cardinalité un.
Ces exemples aideront les DBA à comprendre que
L’index B-arbre stocke les pointeurs d’index et les
l'utilisation des index bitmap n'est pas en fait cardinal
valeurs à d’autres nœuds d’index en utilisant une
dépendante mais dépend de l'application.
structure d’arbre récursive. [3], [6], [7], [9], Les
données sont facilement relevées par les traces des IV- Expérimentation :
pointeurs. Le plus haut niveau de l’index est appelé
racine pendant que le niveau le plus bas on l’appelle L’expérimentation se déroule dans un serveur de base
nœud de feuille ou « leaf node ». [7] Tous les autres de données Oracle supportant OLAP. Il y en a plusieurs
niveaux entre eux sont appelés des branches ou inconvénients en utilisant un index de type bitmap dans
nœuds internes. Toutes les racines et les branches une colonne unique, l’un est le besoin de plus d’espace
contiennent des entrées qui pointent vers le niveau de disque. Cependant, la taille de l'index bitmap dépend
suivant de l’index. Nœuds feuilles se composent de de la cardinalité de la colonne sur laquelle il est créé,
la clé d’index et des pointeurs pointant vers ainsi que la répartition des données. Par conséquent, un
l’emplacement physique des enregistrements. Nous index bitmap sur la colonne « Genre » sera inférieur à
présentons plus de détails sur la structure d’index un index B-arbre sur la même colonne. En revanche, un
arbre-B[7]. index bitmap sur EMPNO (candidat à être clé primaire)
sera beaucoup plus grand qu'un index B-arbresur cette
La structure B-Arbre est utilisée par le serveur de colonne. Mais parce que moins d'utilisateurs accèdent
base de données pour configurer l’index (Figure1) aux systèmes décisionnel (DSS) qu’en accédant les
systèmes de traitement transactionnel (OLTP), les
ressources ne posent pas de problème pour ces
applications.

Pour illustrer ce point, j'ai créé deux tables,

TEST_NORMAL et TEST_RANDOM. On a inséré un
million de lignes dans la table TEST_NORMAL l'aide
d'un bloc PL / SQL, puis on a inséré ces lignes dans la
table de TEST_RANDOM dans un ordre aléatoire:
Root ou racine: plus haut niveau de l’index pointe [Tableau2]
vers les niveaux suivants des nodes branches.
Notez que la table TEST_NORMAL est organisé et que
Nœuds intermédiaires ou branches : contiennent la table TEST_RANDOM créée au hasard, elle a donc
des pointeurs vers le niveau suivant des branches ou des données désorganisées. Dans la table ci-dessus, la
vers les nœuds de feuilles. colonne EMPNO a des valeurs distinctes à 100%, elle
est donc un bon candidat pour devenir une clé primaire.
Nœud de feuilles ou leaf nodes : le plus bas niveau Si vous définissez cette colonne comme clé primaire,
de l’index pointe vers d’autres nœud de feuilles. vous allez créer un index B-arbre et non pas un index
bitmap parce que Oracle ne supporte pas les index
III- Hypothèses bitmap de clé primaire.

La sagesse conventionnelle veut que les index bitmap

soient les plus appropriés pour les colonnes ayant des
valeurs distinctes faibles - comme le sexe, état civil, et
 Create table test_normal (empno number(10), b. Identique à l'étape 1b.
ename varchar2(30), sal number(10));

Begin 3. Sur TEST_NORMAL:

For i in 1..1000000
Loop a. Identique à l'étape 1A, sauf que les
Insert into test_normal
values(i, dbms_random.string('U',30), requêtes sont exécutées dans un intervalle de
dbms_random.value(1000,7000)); prédicats.
If mod(i, 10000) = 0 then
Commit;
End if; b. Identique à l'étape 1b, sauf que les
End loop; requêtes sont exécutées dans une fourchette de
End;
/ prédicats. Et après on compare les statistiques.

Create table test_random 4. Sur TEST_RANDOM:

as
select /*+ append */ * from test_normal
order by dbms_random.random; a. Même que l'étape 3A.
SQL> select count(*) "Total Rows" from b. Identique à l'étape 3B.
test_normal;

Total Rows 5. Sur TEST_NORMAL

----------
1000000
a. Créer un index bitmap sur la colonne de
Elapsed: 00:00:01.09 salaire SAL, puis exécuter des requêtes avec
prédicats d'égalité et certaines avec des intervalles de
SQL> select count(distinct empno) "Distinct
Values" from test_normal; prédicats.
Distinct Values
---------------
b. Créer un index B-Arbre sur la colonne
1000000 SAL, puis exécuter des requêtes avec prédicats
d'égalité et certaines avec des intervalles de prédicats
Elapsed: 00:00:06.09
SQL> select count(*) "Total Rows" from (même ensemble de valeurs que dans l'étape 5A).
test_random; Comparer les E/S fait par les requêtes pour récupérer
Total Rows les résultats.
----------
1000000 6. Ajouter une colonne « genre » pour les deux
Elapsed: 00:00:03.05 tables, et mettre à jour la colonne avec trois valeurs
SQL> select count(distinct empno) "Distinct possibles: M pour masculin, F pour féminin, et nulle
Values" from test_random;
pour N/A. Cette colonne est mise à jour avec ces
Distinct Values valeurs en fonction de certaines conditions.
---------------
1000000
7. Créer un index bitmap sur cette colonne, puis
Elapsed: 00:00:12.07 exécuter des requêtes avec prédicats d'égalité.

Tableau 2 8. Créer un index B-Arbre sur la colonne de genre,

puis exécuter des requêtes avec prédicats d'égalité.
Pour analyser le comportement de ces index, nous Comparer les résultats de l'étape 7.
allons effectuer les étapes suivantes:
Les étapes 1 à 4 impliquent un haut cardinal
1. Sur TEST_NORMAL : (distincts à 100%) colonne, étape 5, une colonne
a. Créer un index bitmap sur la colonne normale cardinal, et les étapes 7 et 8 une colonne
EMPNO et exécuter des requêtes avec prédicats basse cardinal.
d'égalité.
b. Créer un index B-Arbre sur la colonne Étape 1A (sur TEST_NORMAL) :
EMPNO, exécuter des requêtes avec prédicats
d'égalité, et de comparer le physique et logique E/S Dans cette étape, nous allons créer un index bitmap
fait par les requêtes pour récupérer les résultats sur la table TEST_NORMAL puis vérifiez la taille
pour les différents ensembles de valeurs. de cet index, son coefficient de regroupement, et la
taille de la table. Ensuite, nous allons exécuter des
2. Sur TEST_RANDOM: requêtes avec prédicats d'égalité et de noter les

a. Identique à l'étape 1A.

entrées / sorties de ces requêtes en utilisant cet index SQL> set autotrace only
SQL> select * from test_normal where
bitmap. (Table 3) empno=&empno;
Enter value for empno: 1000
old 1: select * from test_normal where
empno=&empno
new 1: select * from test_normal where
SQL> create bitmap index normal_empno_bmx empno=1000
on test_normal(empno);
Elapsed: 00:00:00.01
Index created.
Execution Plan
Elapsed: 00:00:29.06 --------------------------------------------
SQL> analyze table test_normal compute --------------
statistics for table for all indexes for 0 SELECT STATEMENT Optimizer=CHOOSE
all indexed columns; (Cost=4 Card=1 Bytes=34)
1 0 TABLE ACCESS (BY INDEX ROWID) OF
'TEST_NORMAL' (Cost=4 Car
Table analyzed. d=1 Bytes=34)
2 1 BITMAP CONVERSION (TO ROWIDS)
Elapsed: 00:00:19.01 3 2 BITMAP INDEX (SINGLE VALUE)
SQL> select substr(segment_name,1,30) OF 'NORMAL_EMPNO_BMX'
segment_name, bytes/1024/1024 "Size in MB"
2 from user_segments Statistics
3* where segment_name in --------------------------------------------
('TEST_NORMAL','NORMAL_EMPNO_BMX'); --------------
0 recursive calls
SEGMENT_NAME Size in MB 0 db block gets
------------------------------------ 5 consistent gets
--------------- 0 physical reads
TEST_NORMAL 50 0 redo size
NORMAL_EMPNO_BMX 28 515 bytes sent via SQL*Net to
client
Elapsed: 00:00:02.00 499 bytes received via SQL*Net from
SQL> select index_name, clustering_factor client
from user_indexes; 2 SQL*Net roundtrips to/from
client
INDEX_NAME CLUSTERING_FACTOR 0 sorts (memory)
------------------------------ ---- 0 sorts (disk)
----------------------------- 1 rows processed
NORMAL_EMPNO_BMX 1000000

Elapsed: 00:00:00.00 Tableau 4

Tableau 3
SQL> drop index NORMAL_EMPNO_BMX;

Index dropped.

Vous pouvez le voir dans le tableau ci-dessus que la SQL> create index normal_empno_idx on
test_normal(empno);
taille de l'index est 28 Mo et que le facteur de
regroupement est égal au nombre de lignes dans le Index created.
tableau. Maintenant, nous allons exécuter les SQL> analyze table test_normal compute
requêtes avec prédicats d'égalité pour les différents statistics for table for all indexes for
ensembles de valeurs: (Tableau 4) all indexed columns;

Table analyzed.
Etape 1B (sur TEST_NORMAL)
SQL> select substr(segment_name,1,30)
segment_name, bytes/1024/1024 "Size in MB"
Maintenant, nous allons laisser tomber cet index 2 from user_segments
bitmap et créer un index B-arbresur la colonne 3 where segment_name in
EMPNO. Comme précédemment, nous allons ('TEST_NORMAL','NORMAL_EMPNO_IDX');

vérifier la taille de l'index et de son facteur de SEGMENT_NAME Size in MB

regroupement et d'exécuter les mêmes requêtes pour ----------------------------------
TEST_NORMAL 50
le même ensemble de valeurs, de comparer les E/S. NORMAL_EMPNO_IDX 18

SQL> select index_name, clustering_factor

from user_indexes;

INDEX_NAME CLUSTERING_FACTOR
---------------------------------- -----
-----------------------------
NORMAL_EMPNO_IDX 6210
Tableau 5
Il est clair dans ce tableau (Tableau 5) que les index Etape 2A (sur TEST_RANDOM)
B-Arbres est inférieur que l'index bitmap sur la
colonne EMPNO. Le facteur de regroupement de Maintenant, nous allons effectuer la même
l'index B-arbre est beaucoup plus proche du nombre expérience sur TEST_RANDOM (Tableau 8):
de blocs dans une table, pour cette raison, l'index B- SQL> create bitmap index random_empno_bmx
arbre est efficace pour les requêtes de prédicats. on test_random(empno);
Maintenant, nous allons exécuter les mêmes requêtes
Index created.
pour le même ensemble de valeurs, en utilisant notre
index B-arbre. SQL> analyze table test_random compute
statistics for table for all indexes for
all indexed columns;
SQL> set autotrace
SQL> select * from test_normal where Table analyzed.
empno=&empno;
Enter value for empno: 1000 SQL> select substr(segment_name,1,30)
old 1: select * from test_normal where segment_name, bytes/1024/1024 "Size in MB"
empno=&empno 2 from user_segments
new 1: select * from test_normal where 3* where segment_name in
empno=1000 ('TEST_RANDOM','RANDOM_EMPNO_BMX');
Elapsed: 00:00:00.01 SEGMENT_NAME Size in MB
------------------------------------
Execution Plan ---------------
-------------------------------------------- TEST_RANDOM 50
0 SELECT STATEMENT Optimizer=CHOOSE RANDOM_EMPNO_BMX 28
(Cost=4 Card=1 Bytes=34)
1 0 TABLE ACCESS (BY INDEX ROWID) OF SQL> select index_name, clustering_factor
'TEST_NORMAL' (Cost=4 Car from user_indexes;
d=1 Bytes=34)
2 1 INDEX (RANGE SCAN) OF INDEX_NAME CLUSTERING_FACTOR
'NORMAL_EMPNO_IDX' (NON-UNIQUE) (C ------------------------------ ----
ost=3 Card=1) -----------------------------
RANDOM_EMPNO_BMX 1000000
Statistics
-------------------------------------------- Tableau 8
29 recursive calls
0 db block gets Encore une fois, les statistiques (taille et le facteur
5 consistent gets
0 physical reads de regroupement) sont identiques à celles de l'index
0 redo size sur la table TEST_NORMAL (Tableau 9):
515 bytes sent via SQL*Net to
client
Elapsed: 00:00:00.01
499 bytes received via SQL*Net from
client
Execution Plan
2 SQL*Net roundtrips to/from
--------------------------------------------
client
--------------
0 sorts (memory)
0 SELECT STATEMENT Optimizer=CHOOSE
0 sorts (disk)
(Cost=4 Card=1 Bytes=34)
1 rows processed
1 0 TABLE ACCESS (BY INDEX ROWID) OF
Tableau 6 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
2 1 BITMAP CONVERSION (TO ROWIDS)
Comme vous pouvez le voir (Tableau 7), lorsque les 3 2 BITMAP INDEX (SINGLE VALUE)
OF 'RANDOM_EMPNO_BMX'
requêtes sont exécutées pour des valeurs différentes,
le nombre de lectures cohérentes et des lectures Statistics
--------------------------------------------
physiques sont identiques pour bitmap et index B- --------------
arbre sur une colonne unique de 100%. 0 recursive calls
0 db block gets
5 consistent gets
BITMAP EMPNO B-TREE 0 physical reads
Consistent Physical Consistent Physical 0 redo size
Reads Reads Reads Reads 515 bytes sent via SQL*Net to
5 0 1000 5 0 client
5 2 2398 5 2 499 bytes received via SQL*Net from
5 2 8545 5 2 client
5 2 98008 5 2 2 SQL*Net roundtrips to/from
5 2 85342 5 2 client
5 2 128444 5 2 0 sorts (memory)
5 2 858 5 2 0 sorts (disk)
1 rows processed
Tableau 7
Tableau 9
Étape 2B (sur TEST_RANDOM) SQL> select * from test_random where
empno=&empno;
Enter value for empno: 1000
Maintenant, comme dans l'étape 1b, nous allons old 1: select * from test_random where
supprimer l'index bitmap et créer un index B-arbre empno=&empno
new 1: select * from test_random where
sur la colonne EMPNO. (Tableau 10) empno=1000

SQL> drop index RANDOM_EMPNO_BMX; Elapsed: 00:00:00.01

Index dropped. Execution Plan

--------------------------------------------
SQL> create index random_empno_idx on --------------
test_random(empno); 0 SELECT STATEMENT Optimizer=CHOOSE
(Cost=4 Card=1 Bytes=34)
Index created. 1 0 TABLE ACCESS (BY INDEX ROWID) OF
'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
SQL> analyze table test_random compute 2 1 INDEX (RANGE SCAN) OF
statistics for table for all indexes for 'RANDOM_EMPNO_IDX' (NON-UNIQUE) (Cost=3
all indexed columns; Card=1)

Table analyzed. Statistics

--------------------------------------------
SQL> select substr(segment_name,1,30) --------------
segment_name, bytes/1024/1024 "Size in MB" 0 recursive calls
2 from user_segments 0 db block gets
3 where segment_name in 5 consistent gets
('TEST_RANDOM','RANDOM_EMPNO_IDX'); 0 physical reads
0 redo size
SEGMENT_NAME Size in MB 515 bytes sent via SQL*Net to
---------------------------------- client
--------------- 499 bytes received via SQL*Net from
TEST_RANDOM 50 client
RANDOM_EMPNO_IDX 18 2 SQL*Net roundtrips to/from
client
SQL> select index_name, clustering_factor 0 sorts (memory)
from user_indexes; 0 sorts (disk)
1 rows processed
INDEX_NAME CLUSTERING_FACTOR Tableau 11
---------------------------------- -----
-----------------------------
RANDOM_EMPNO_IDX 999830 Etape 3A (sur TEST_NORMAL)
Tableau 10
Dans cette étape, nous allons créer l'index bitmap
Ce tableau montre que la taille de l'index est égale à (similaire à l'étape 1A). Sachant que la taille et le
la taille de cet index sur la table TEST_NORMAL facteur de regroupement de l'index est égal au
mais le facteur de regroupement est beaucoup plus nombre de lignes dans la table. Maintenant, nous
proche du nombre de lignes, ce qui rend cet index allons lancer quelques requêtes avec intervalles de
inefficace pour les requêtes de prédicat par prédicats (Tableau 12).
intervalles (que nous verrons à l'étape 4).
Étape 3B (sur TEST_NORMAL)
Ce facteur de regroupement n'aura aucune influence
sur l’égalité des requêtes de prédicat parce que les Dans cette étape, nous allons exécuter les requêtes
lignes ont des valeurs 100% distinctes et le nombre sur la table TEST_NORMAL avec un index B-arbre
de lignes par clé est 1. sur elle. (Tableau 13).

BITMAP EMPNO B-TREE

Maintenant, nous allons exécuter les requêtes avec Consistent Physical (Range) Consistent Physical
prédicats d'égalité et le même ensemble de valeurs. Reads Reads Reads Reads
331 0 1-2300 329 0
(Tableau11) 285 0 8-1980 283 0
346 19 1850-4250 344 16
Encore une fois, les résultats sont presque identiques 427 31 28888- 424 28
à celles dans les étapes 1A et 1B. La distribution de 31850
371 27 82900- 367 23
données n'affecte pas le montant des lectures 85478
cohérentes et des lectures physiques d'une colonne 2157 149 984888- 2139 35
1000000
unique.
Tableau 14
SQL> select * from test_normal where empno Lorsque ces requêtes sont exécutées pour différents
between &range1 and &range2;
Enter value for range1: 1 intervalles, on obtient ces résultats;
Enter value for range2: 2300
old 1: select * from test_normal where Comme vous pouvez le voir, le nombre de lectures
empno between &range1 and &range2
new 1: select * from test_normal where cohérentes et de lectures physiques pour les deux
empno between 1 and 2300 index sont de nouveau presque identiques. Le
2300 rows selected. dernier intervalle (984888-1000000) a retourné
presque 15.000 lignes, ce qui était le nombre
Elapsed: 00:00:00.02
maximal de lignes extraites pour tous les intervalles
Execution Plan indiqués ci-dessus. Ainsi, lorsque nous avons
-------------------------------------------- demandé un scan de table complet, la lecture
0 SELECT STATEMENT Optimizer=CHOOSE
(Cost=23 Card=2299 Bytes=78166) cohérente et compte lire physiques étaient 7,239 et
1 0 TABLE ACCESS (BY INDEX ROWID) OF 5,663, respectivement.
'TEST_NORMAL' (Cost=23 Card=2299
Bytes=78166)
2 1 INDEX (RANGE SCAN) OF Etape 4A (sur TEST_RANDOM)
'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=8
Card=2299)
Dans cette étape, nous allons exécuter les requêtes
Statistics avec prédicats d'intervalles sur la table de
-------------------------------------------- TEST_RANDOM avec index bitmap et vérifier les
0 recursive calls
0 db block gets lectures cohérentes et les lectures physiques. Ici,
329 consistent gets vous verrez l'impact du facteur de regroupement.
15 physical reads
0 redo size (Tableau 15).
111416 bytes sent via SQL*Net client
2182 bytes received via SQL*Net from SQL>select * from test_random where empno
client between &range1 and &range2;
155 SQL*Net roundtrips to/from Enter value for range1: 1
client Enter value for range2: 2300
0 sorts (memory) old 1: select * from test_random where
0 sorts (disk) empno between &range1 and &range2
2300 rows processed new 1: select * from test_random where
Tableau 12 empno between 1 and 2300

2300 rows selected.

SQL> select * from test_normal where empno
between &range1 and &range2;
Elapsed: 00:00:08.01
Enter value for range1: 1
Enter value for range2: 2300
Execution Plan
old 1: select * from test_normal where
--------------------------------------------
empno between &range1 and &range2
--------------
new 1: select * from test_normal where
0 SELECT STATEMENT Optimizer=CHOOSE
empno between 1 and 2300
(Cost=453 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (BY INDEX ROWID) OF
2300 rows selected.
'TEST_RANDOM' (Cost=453 Card=2299
Elapsed: 00:00:00.02
Bytes=78166)
Execution Plan
2 1 BITMAP CONVERSION (TO ROWIDS)
--------------------------------------------
3 2 BITMAP INDEX (RANGE SCAN) OF
0 SELECT STATEMENT Optimizer=CHOOSE
'RANDOM_EMPNO_BMX'
(Cost=23 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (BY INDEX ROWID) OF
Statistics
'TEST_NORMAL' (Cost=23 Card=2299
--------------------------------------------
Bytes=78166)
--------------
2 1 INDEX (RANGE SCAN) OF
0 recursive calls
'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=8
0 db block gets
Card=2299)
2463 consistent gets
Statistics
1200 physical reads
--------------------------------------------
0 redo size
0 recursive calls
111416 bytes sent via SQL*Net to
0 db block gets
client
329 consistent gets
2182 bytes received via SQL*Net from
15 physical reads
client
0 redo size
155 SQL*Net roundtrips to/from
111416 bytes sent via SQL*Net to
client
client
0 sorts (memory)
2182 bytes received via SQL*Net from
0 sorts (disk)
client
2300 rows processed
155 SQL*Net roundtrips to/from
client
0 sorts (memory) Tableau 15
0 sorts (disk)
2300 rows processed
L'étape 4B (sur TEST_RANDOM)
Tableau 13
Dans cette étape, nous allons exécuter les requêtes Pour le dernier intervalle (984888-1000000)
de prédicat d’intervalle sur TEST_RANDOM avec seulement, l'optimiseur a opté pour une analyse
un index B-arbre. Rappelons que le facteur de complète de la table pour l'index bitmap, alors que
regroupement de cet index était très proche du pour tous les intervalles, il a opté pour une analyse
nombre de lignes dans une table (et donc inefficace). complète de la table pour l'index B-arbre. Cette
Voici ce que l'optimiseur a à dire à ce sujet: disparité est due au facteur de regroupement:
(Tableau 16) L'optimiseur ne tient pas compte de la valeur du
facteur de regroupement lors de la génération des
SQL> select * from test_random where empno
between &range1 and &range2; plans d'exécution en utilisant un index bitmap, alors
Enter value for range1: 1 qu’il le fait que pour un index B-arbre. Dans ce
Enter value for range2: 2300
old 1: select * from test_random where
scénario, l'index de bitmap remplit plus efficacement
empno between &range1 and &range2 que l'index B-arbre. Les étapes suivantes révèlent
new 1: select * from test_random where des faits intéressants sur ces index :
empno between 1 and 2300

2300 rows selected. Etape 5A (sur TEST_NORMAL)

Elapsed: 00:00:03.04
Créer un index bitmap sur la colonne SAL de la
Execution Plan table TEST_NORMAL. Cette colonne est de
------------------------------------------- cardinal normal.
0 SELECT STATEMENT Optimizer=CHOOSE
(Cost=613 Card=2299 Bytes=78166)
1 0 TABLE ACCESS (FULL) OF SQL> create bitmap index normal_sal_bmx on
'TEST_RANDOM' (Cost=613 Card=2299 test_normal(sal);
Bytes=78166)
Index created.
Statistics
------------------------------------------- SQL> analyze table test_normal compute
0 recursive calls statistics for table for all indexes for
0 db block gets all indexed columns;
6415 consistent gets
4910 physical reads Table analyzed.
0 redo size Tableau 18
111416 bytes sent via SQL*Net to
client
2182 bytes received via SQL*Net Maintenant, nous allons obtenir la taille de l'index et
from client le facteur de regroupement.
155 SQL*Net roundtrips to/from
client
SQL>select substr(segment_name,1,30)
0 sorts (memory)
segment_name, bytes/1024/1024 "Size in MB"
0 sorts (disk)
2* from user_segments
2300 rows processed
3* where segment_name in
Tableau 16 ('TEST_NORMAL','NORMAL_SAL_BMX');

L'optimiseur a opté pour une analyse complète de la SEGMENT_NAME Size in MB

------------------------------
table plutôt que d'utiliser l'index à cause du facteur --------------
de regroupement: TEST_NORMAL 50
NORMAL_SAL_BMX 4
BITMAP EMPNO B-TREE SQL> select index_name, clustering_factor
Consistent Physical (Range) Consistent Physical from user_indexes;
Reads Reads Reads Reads
2463 1200 1-2300 6415 4910 INDEX_NAME CLUSTERING_FACTOR
2114 31 8-1980 6389 4910 ------------------------------ ----
2572 1135 1850- 6418 4909 ------------------------------
4250 NORMAL_SAL_BMX 6001
3173 1620 28888- 6456 4909
Tableau 19
31850
2762 1358 82900- 6431 4909
85478 Pour les requêtes, première exécution avec prédicats
7254 3329 984888- 7254 4909 d’égalité (Tableau 20), Et après avec prédicats
100000
0 d’intervalle (Tableau 21)
Tableau 17
Maintenant, on supprime l'index bitmap et créer un
index B-arbre sur TEST_NORMAL.
SQL> set auto trace SQL> create index normal_sal_idx on
SQL> select * from test_normal where test_normal(sal);
sal=&sal;
Enter value for sal: 1869 Index created.
old 1: select * from test_normal where
sal=&sal SQL> analyze table test_normal compute
new 1: select * from test_normal where statistics for table for all indexes for
sal=1869 all indexed columns;

164 rows selected. Table analyzed.

Elapsed: 00:00:00.08 Take a look at the size of the index and the clustering
factor.
Execution Plan
-------------------------------------------- SQL> select substr(segment_name,1,30)
0 SELECT STATEMENT Optimizer=CHOOSE segment_name, bytes/1024/1024 "Size in MB"
(Cost=39 Card=168 Bytes=4032) 2 from user_segments
1 0 TABLE ACCESS (BY INDEX ROWID) OF 3 where segment_name in
'TEST_NORMAL' (Cost=39 Card=168 Bytes=4032) ('TEST_NORMAL','NORMAL_SAL_IDX');
2 1 BITMAP CONVERSION (TO ROWIDS)
3 2 BITMAP INDEX (SINGLE VALUE) SEGMENT_NAME Size in MB
OF 'NORMAL_SAL_BMX' ------------------------------ ------
---------
Statistics TEST_NORMAL 50
-------------------------------------------- NORMAL_SAL_IDX 17
0 recursive calls
0 db block gets SQL> select index_name, clustering_factor
165 consistent gets from user_indexes;
0 physical reads
0 redo size INDEX_NAME CLUSTERING_FACTOR
8461 bytes sent via SQL*Net to ------------------------------ ------
client ----------------------------
609 bytes received via SQL*Net from NORMAL_SAL_IDX 986778
client Tableau 22
12 SQL*Net roundtrips to/from
client
0 sorts (memory) SQL> set autotrace
0 sorts (disk) SQL> select * from test_normal where
164 rows processed sal=&sal;
Enter value for sal: 1869
old 1: select * from test_normal where
Tableau 20 sal=&sal
new 1: select * from test_normal where
SQL> select * from test_normal where sal sal=1869
between &sal1 and &sal2;
Enter value for sal1: 1500 164 rows selected.
Enter value for sal2: 2000
old 1: select * from test_normal where sal Elapsed: 00:00:00.01
between &sal1 and &sal2
new 1: select * from test_normal where sal Execution Plan
between 1500 and 2000 --------------------------------------------
--------------
83743 rows selected. 0 SELECT STATEMENT Optimizer=CHOOSE
Elapsed: 00:00:05.00 (Cost=169 Card=168 Bytes=4032)
1 0 TABLE ACCESS (BY INDEX ROWID) OF
Execution Plan 'TEST_NORMAL' (Cost=169 Card=168 Bytes=4032)
-------------------------------------------- 2 1 INDEX (RANGE SCAN) OF
0 SELECT STATEMENT Optimizer=CHOOSE 'NORMAL_SAL_IDX' (NON-UNIQUE) (Cost=3
(Cost=601 Card=83376 Bytes Card=168)
=2001024)
1 0 TABLE ACCESS (FULL) OF Statistics
'TEST_NORMAL' (Cost=601 Card=83376 --------------------------------------------
Bytes=2001024) --------------
0 recursive calls
Statistics 0 db block gets
-------------------------------------------- 177 consistent gets
0 recursive calls 0 physical reads
0 db block gets 0 redo size
11778 consistent gets 8461 bytes sent via SQL*Net to
5850 physical reads client
0 redo size 609 bytes received via SQL*Net from
4123553 bytes sent via SQL*Net client client
61901 bytes received via SQL*Net from 12 SQL*Net roundtrips to/from
client client
5584 SQL*Net roundtrips to/from 0 sorts (memory)
client 0 sorts (disk)
0 sorts (memory) 164 rows processed
0 sorts (disk) Tableau 23
83743 rows processed
Tableau 21
Dans la table ci-dessus, vous pouvez voir que cet BITMAP SAL B-TREE Rows
(Range) Consistent Fetched
index est supérieur à l'index bitmap sur la même Consistent Physical Physical
Reads Reads Reads Reads
colonne. Le facteur de regroupement est également 11778 5850 1500- 11778 3891 83743
proche du nombre de lignes dans cette table. 2000
11765 5468 2000- 11765 3879 83328
Maintenant, pour les essais; prédicats d'égalité en 2500
premier (Tableau 23), et après prédicats 11753 5471 2500- 11753 3884 83318
3000
d’intervalles (Tableau 24).
17309 5472 3000- 17309 3892 166999
4000
SQL> select * from test_normal where sal
between &sal1 and &sal2; 39398 5454 4000- 39398 3973 500520
Enter value for sal1: 1500 7000
Enter value for sal2: 2000 Tableau 26
old 1: select * from test_normal where sal
between &sal1 and &sal2
new 1: select * from test_normal where sal Pour l’intervalle de prédicats l'optimiseur opté pour
between 1500 and 2000 un scan de table complet pour tous les différents
83743 rows selected. ensemble de valeurs qu'il, n'a pas du tout utilisé les
index, tandis que pour les prédicats d'égalité,
Elapsed: 00:00:04.03
l'optimiseur a utilisé les index. Encore une fois, les
Execution Plan lectures cohérents et lectures physiques sont
--------------------------------------------
--------------
identiques. Par conséquent, on peut conclure que
0 SELECT STATEMENT Optimizer=CHOOSE pour une colonne de normale cardinal, les décisions
(Cost=601 Card=83376 Bytes
=2001024)
de l'optimiseur pour les deux types d'index sont les
1 0 TABLE ACCESS (FULL) OF mêmes et il n'y avait pas de différences
'TEST_NORMAL' (Cost=601 Card=83376 significatives entre les E/S.
Bytes=2001024)

Statistics
--------------------------------------------
--------------
Étape 6 (ajouter une colonne GENDER)
0 recursive calls
0 db block gets Avant d'effectuer le test sur une colonne basse
11778 consistent gets
3891 physical reads
cardinal, nous allons ajouter une colonne de genre
0 redo size dans ce tableau et le mettre à jour avec M, F et les
4123553 bytes sent via SQL*Net to
client
valeurs NULL.
61901 bytes received via SQL*Net from
client
5584 SQL*Net roundtrips to/from
client SQL> alter table test_normal add GENDER
0 sorts (memory) varchar2(1);
0 sorts (disk)
83743 rows processed Table altered.
Tableau 24
SQL> select GENDER, count(*) from
test_normal group by GENDER;
Lorsque les requêtes ont été exécutées pour des
valeurs différentes, le résultat obtenu, comme S COUNT(*)
indiqué dans les tableaux ci-dessous, révèle que le - ----------
F 333769
nombre des lectures cohérent et des lectures M 499921
physiques sont identiques. 166310

3 rows selected.
BITMAP SAL B-TREE Rows
(Equality) Consistent Fetched
Tableau 27
Consistent Physical Physical
Reads Reads Reads Reads
165 0 1869 177 164
169 163 3548 181 167
174 166 6500 187 172
75 69 7000 81 73
177 163 2500 190 175
Tableau 25
 La taille de l'index bitmap sur cette colonne est SQL> select * from test_normal where GENDER
is null;
d'environ 570KB, comme indiqué dans la table ci-
dessous.(Tableau 28) En revanche, l'index B-arbre 166310 rows selected.
sur cette colonne est 13MB en taille, ce qui est Elapsed: 00:00:06.08
beaucoup plus grand que l'index bitmap sur cette
Execution Plan
colonne.(Tableau 29) --------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
SQL> create bitmap index normal_GENDER_bmx (Cost=601 Card=166310 Bytes=4157750)
on test_normal(GENDER); 1 0 TABLE ACCESS (FULL) OF
'TEST_NORMAL' (Cost=601 Card=166310
Index created. Bytes=4157750)

Elapsed: 00:00:02.08 SQL> select * from test_normal where

GENDER='M';
SQL> select substr(segment_name,1,30)
segment_name, bytes/1024/1024 "Size in MB" 499921 rows selected.
2 from user_segments
3 where segment_name in Elapsed: 00:00:16.07
('TEST_NORMAL','NORMAL_GENDER_BMX');
Execution Plan
SEGMENT_NAME Size in MB --------------------------------------------
------------------------------ ------- 0 SELECT STATEMENT Optimizer=CHOOSE
-------- (Cost=601 Card=499921 Bytes=12498025)
TEST_NORMAL 50 1 0 TABLE ACCESS (FULL) OF
NORMAL_GENDER_BMX .5625 'TEST_NORMAL' (Cost=601
Card=499921Bytes=12498025)
2 rows selected.
SQL>select * from test_normal where
Tableau 28 GENDER='F'
/

333769 rows selected.

SQL> create index normal_GENDER_idx on Elapsed: 00:00:12.02

test_normal(GENDER);
Execution Plan
Index created. --------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
SQL> select substr(segment_name,1,30) (Cost=601 Card=333769 Byte
segment_name, bytes/1024/1024 "Size in MB" s=8344225)
2 from user_segments 1 0 TABLE ACCESS (FULL) OF
3 where segment_name in 'TEST_NORMAL' (Cost=601 Card=333769
('TEST_NORMAL','NORMAL_GENDER_IDX'); Bytes=8344225)

SEGMENT_NAME Size in MB Tableau 30

------------------------------ --------
-------
TEST_NORMAL 50 V- Conclusions :
NORMAL_GENDER_IDX 13
Maintenant que nous avons compris comment
2 rows selected.
Tableau 29 l'optimiseur réagit à ces techniques, nous allons
examiner un scénario qui démontre clairement les
meilleures applications respectives des index bitmap
et les index B-arbres

Avec un index bitmap sur la colonne GENDER en

Maintenant, si nous exécutons une requête avec place, on va créer un autre index bitmap sur la
prédicats d'égalité, l'optimiseur va pas utiliser colonne SAL, puis d'exécuter certaines requêtes. Les
d’index, que ce soit bitmap ou un B-arbre. Au requêtes seront exécutées à nouveau avec index B-
contraire, il va préférer un scan de table complet. arbres sur ces colonnes. Dans la table
(Tableau 30) TEST_NORMAL, on aura besoin du numéro
d'employé de tous les employés de sexe masculin
dont les salaires mensuels égaux une des valeurs
suivantes:

1000, 1500, 2000, 2500, 3000, 3500, 4000,

4500.
Ainsi :
SQL>select * from test_normal
SQL>select * from test_normal where sal in
where sal in (1000,1500,2000,2500,3000,3500,4000,4500,500
(1000,1500,2000,2500,3000,3500,4000,4500,500 0) and GENDER='M';
0) and GENDER='M';
1453 rows selected.
1453 rows selected.
Elapsed: 00:00:03.01
Elapsed: 00:00:02.03
Execution Plan
Execution Plan --------------------------------------------
-------------------------------------------- --------------
-------------- 0 SELECT STATEMENT Optimizer=CHOOSE
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=754 Bytes=18850)
(Cost=198 Card=754 Bytes=18850) 1 0 TABLE ACCESS (FULL) OF
1 0 TABLE ACCESS (BY INDEX ROWID) OF 'TEST_NORMAL' (Cost=601 Card=754
'TEST_NORMAL' (Cost=198 Card=754 Bytes=18850)
Bytes=18850)
2 1 BITMAP CONVERSION (TO ROWIDS) Statistics
3 2 BITMAP AND --------------------------------------------
4 3 BITMAP OR --------------
5 4 BITMAP INDEX (SINGLE 0 recursive calls
VALUE) OF 'NORMAL_SAL_BMX' 0 db block gets
6 4 BITMAP INDEX (SINGLE 6333 consistent gets
VALUE) OF 'NORMAL_SAL_BMX' 4412 physical reads
7 4 BITMAP INDEX (SINGLE 0 redo size
VALUE) OF 'NORMAL_SAL_BMX' 75604 bytes sent via SQL*Net to
8 4 BITMAP INDEX (SINGLE client
VALUE) OF 'NORMAL_SAL_BMX' 1555 bytes received via SQL*Net from
9 4 BITMAP INDEX (SINGLE client
VALUE) OF 'NORMAL_SAL_BMX' 98 SQL*Net roundtrips to/from
10 4 BITMAP INDEX (SINGLE client
VALUE) OF 'NORMAL_SAL_BMX' 0 sorts (memory)
11 4 BITMAP INDEX (SINGLE 0 sorts (disk)
VALUE) OF 'NORMAL_SAL_BMX' 1453 rows processed
12 4 BITMAP INDEX (SINGLE Tableau 32
VALUE) OF 'NORMAL_SAL_BMX'
13 4 BITMAP INDEX (SINGLE
VALUE) OF 'NORMAL_SAL_BMX' Bien vu, avec l'index B-tree, l'optimiseur a opté pour
14 3 BITMAP INDEX (SINGLE un scan de table complet, alors que dans le cas de
VALUE) OF 'NORMAL_GENDER_BMX' l'index bitmap, il l’a utilisé pour répondre à la
requête. Vous pouvez déduire les performances par
Statistics
-------------------------------------------- le nombre d'E / S nécessaire pour aller chercher le
-------------- résultat.
0 recursive calls En résumé, les index bitmap sont les mieux adaptés
0 db block gets
pour DSS (systèmes de décisionnels)
1353 consistent gets
920 physical reads indépendamment de cardinal pour ces raisons:
0 redo size - Avec index bitmap, l'optimiseur peut répondre
75604 bytes sent via SQL*Net to efficacement requêtes qui incluent AND, OR,
client
1555 bytes received via SQL*Net from
XOR ou. (Oracle supporte la conversion
client dynamique B-Arbre à bitmap, mais il peut être
98 SQL*Net roundtrips to/from inefficace.)
client - Avec bitmaps, l'optimiseur peut répondre à des
0 sorts (memory)
0 sorts (disk) questions lors de la recherche ou de comptage
1453 rows processed de zéros. Les valeurs nulles sont aussi indexées
dans les index bitmap (contrairement aux index
Tableau 31 B-arbre).
- Et le plus important que les index bitmap dans
les systèmes de décisionnels supportent les
requêtes ad hoc, tandis que les B-arbres ne le
Il s'agit d'une requête typique de l'entrepôt de font pas. Plus précisément, si vous avez une
données, que, bien sûr, ne faut jamais l’exécuter sur table avec 50 colonnes et les utilisateurs
un système OLTP. Voici les résultats obtenus avec fréquemment envoient des requêtes sur 10
l'index bitmap en place sur deux colonnes. d'entre eux? Soit la combinaison de tous les 10
colonnes ou parfois une seule colonne?
Avec index B-arbre en place : Création d'un index B-arbresera très difficile.
Si vous créez 10 index bitmap sur tous ces
colonnes, toutes les requêtes peuvent être
traitées par ces indices, qu'ils soient des
requêtes sur l'ensemble des 10 colonnes, sur 4
ou 6 colonnes sur les 10 ou sur une seule SIGMOD: Proceedings of the 1997 ACM
colonne. Le signe AND_EQUAL fournit cette SIGMOD international conference on
fonctionnalité pour les index B-arbres, mais Management of data.1997
pas plus de cinq indices peut être utilisé par
une requête. Cette limite n'est pas imposée avec [9] C. Dell aquila and E. Lefons and F.
des index bitmap. Tangorra, Analytic Use of Bitmap Indices.
Proceedings of the 6th WSEAS International
En revanche, les index B-arbres sont bien Conference on Artificial Intelligence,
adaptés pour les applications OLTP dans lequel Knowledge Engineering and Data Bases, Corfu
les requêtes des utilisateurs sont relativement Island, Greece, February 16-19, 2007 pp. 159
routine (et bien réglé avant le déploiement en
production), par opposition à des requêtes ad [10] P. O’Neil and G. Graefe, Multi-table joins
hoc, qui sont beaucoup moins fréquentes et through bitmapped join indices, ACM
exécutés pendant heures creuses d'affaires. SIGMOD Record 24 number 3, Sep 1995 , pp.
Comme les données sont fréquemment mis à 8-11.
jour et supprimés à partir d'applications OLTP,
les index bitmap peuvent causer un problème [11] K. Wu and P. Yu, Range-based bitmap
de blocage sérieux dans ces situations. Indexing for high cardinality attributes with
skew, In COMPSAC 98: Proceedings of the
Le message ici est assez clair. Les deux 22nd International Computer Software and
indices ont un objectif similaire: pour retourner Applications Conference. IEEE
des résultats aussi vite que possible. Mais le Computer Society, Washington, DC, USA,
choix de celui à utiliser devrait dépendre 1998, pp. 61-67.
uniquement sur le type d'application, et non sur
le niveau de cardinal. [12] E. E-O’Neil and P. P-O’Neil, Bitmap
index design choices and their performance
Références impli-cations, Database Engineering and
Applications Symposium. IDEAS 2007. 11th
[1] S. Chaudhuri, U. Dayal,An Overview of International, pp. 72-84.
Data Warehousing and OLAP Technology.,
ACM SIGMOD RECORD. 1997 [13] C. Imho and N. Galemmo and J. Geiger,
Mastering Data Warehouse Design : Relational
[2] P. O’Neil, Model 204 Architecture and and Dimensional Techniques, John Wiley and
Performance. In Proceedings of the 2nd Sons, NEW YORK.2003
international Workshop on High Performance
Transaction Systems, Lecture Notes In
Computer Science, vol. 359. Springer-Verlag,
London, (September 28 - 30, 1987),pp.40-59

[3] R. Kimball, L. Reeves, M. Ross, The Data

Warehouse Toolkit. John Wiley Sons, NEW
YORK, 2nd edition, 2002

[4] W. Inmon, Building the Data Warehouse.,

John Wiley Sons, fourth edition, 2005

[5] C. DELLAQUILA and E. LEFONS and F.

TANGORRA, Design and Implementation of a
National Data Warehouse. Proceedings of the
5th WSEAS Int. Conf. on Artificial Intelligence,
Knowledge Engineering and Data Bases,
Madrid, Spain, February 15-17, 2006 pp. 342-
347

[6] D. Comer,Ubiquitous b-tree, ACM

Comput. Surv. 11, 2, 1979, pp. 121-13

[7] R. Strohm, Oracle Database Concepts

1g,Oracle, Redwood City,CA 94065, 2007

[8] P. O’Neil and D. Quass, Improved query

performance with variant indexes, In