Physical Data Warehouse Design - Data Warehouse Systems: Design and Implementation - page 253

a

ProductKey ProductName QuantityPerUnit UnitPrice Discontinued CategoryKey
p1 prod1 25 60 No c1

p2 prod2 45 60 Yes c1

p3 prod3 50 75 No c2

p4 prod4 50 100 Yes c2

p5 prod5 50 120 No c3

p6 prod6 70 110 Yes c4

b c

25 45 50 70
p1 1

60 75 100 110 120
p1 1 0 0 0 0 0 0 0

p2 0 1 0 0 p2 1 0 0 0 0

p3 0 0 1 0 p3 0 1 0 0 0

p4 0 0 1 0 p4 0 0 1 0 0

p5 0 0 1 0 p5 0 0 0 0 1

p6 0 0 0 1 p6 0 0 0 1 0

Fig. 7.10 An example of bitmap indexes for a Product dimension table. ( a ) Product
dimension table. ( b ) Bitmap index for attribute QuantityPerUnit .( c ) Bitmap index
for attribute UnitPrice

a b c

45 50 OR1
p1 0

100 110 120 OR2 OR1 OR2 AND

0 0 p1 0 0 0 0 p1 0 0 0

p2 1 0 1 p2 0 0 0 0 p2 1 0 0

p3 0 1 1 p3 0 0 0 0 p3 1 0 0

p4 0 1 1 p4 1 0 0 1 p4 1 1 1

p5 0 1 1 p5 0 0 1 1 p5 1 1 1

p6 0 0 0 p6 0 1 0 1 p6 0 1 0

Fig. 7.11 Finding the products having between 45 and 55 pieces per unit and with
a unit price between 100 and 200. ( a ) OR for QuantityPerUnit .( b ) OR for UnitPrice .
( c ) AND operation

two vectors, shown in Fig. 7.11 c, gives the rows satisfying both conditions.
The result is that products p4 and p5 satisfy the query.
The operation just described is the main reason of the high performance
achieved by bitmapped indexing in the querying process. When performing
AND , OR ,and NOT operations, the system will just perform a bit comparison,
and the resulting bit vector is obtained at a very low CPU cost.
The above example suggests that the best opportunities for these indexes
are found where the cardinality of the attributes being indexed is low.