Then, the extracted list of qualifying dimension keys, for each dimension,
is used to access the bitmap index on the corresponding fact table column. The created
bitmaps are merged (i.e., ANDed) and a final bitmap, indicating the qualifying
fact table tuples, is produced. Next, bits set on the final bitmap are converted to the
corresponding row ids and the fact table tuples are retrieved. Finally, these tuples
have to be joined to the dimension tables in order to retrieve the dimension attribute
values required in the final result.
The main advantage of this method is that the bitmap operations can be executed
very efficiently. However, the lack of appropriate data clustering might lead to a
significant number of I/Os. When the query selectivity is high (small output), then
only a few bits in the final bitmap are set. If there is no particular order among
the fact table tuples, we can expect each bit to correspond to a tuple on a different
page. Thus, there will be as many I/Os as there are bits set. Moreover, bitmap
indexes become inefficient if the number of distinct values for a column is large
(O??™Neil & Quass, 1997). In this case the ???bitmap density??? (i.e., the number of bits
Advanced Ad Hoc Star Query Processing 4
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc.
Pages:
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291