The column partition is scanned
and for each value, the in-memory array is probed. Depending on whether a match
is found or not, a 1 or a 0 is stored at the corresponding row position of a bitmap.
This process is repeated for predicates on other columns. At the end of scanning all
queried columns, individual bitmaps are obtained, which can be ANDed or ORed
resulting in a bitmap with 1 at row positions that satisfy all predicates. Tuples corresponding
to these row positions can be retrieved.
A bitmap join index (BJI) (Vanichayobon & Gruenwald, 1999) is built by creating
a bitmap index on a table T based on a single column A of table S, where A is a
join attribute; hence, the actual join need not be performed. It is usually used with
low cardinality data.
Koudas??™ Encoded Bitmap Index
Koudas (2000) proposes a technique to index large cardinality attributes using less
storage space compared to SBIs, taking into account both the query and data distribution
of the attribute instances. We call this technique Koudas??™ encoded bitmap
index (KEBI). The idea is to encode sequences of attribute values together in the
bitmap index, as opposed to creating one bitmap per attribute value. The information
returned from the bitmap may be a superset of a query answer. Table 2 shows an
example of this approach. The attribute WorkYears has five distinct values.
Pages:
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357