Page History

...

This document explains the proposed design for adding a bitmap index handler (https://issues.apache.org/jira/browse/HIVE-1803^{Image Removed}).
Bitmap indexing (http://en.wikipedia.org/wiki/Bitmap_index^{Image Removed}) is a standard technique for indexing columns with few distinct
values, such as gender.

...

Suppose we have a bitmap index on a key where, on the first block, value "a" appears in rows 5, 12, and 64, and value "b" appears in rows 7, 8, and 9. Then, for the preliminary implementation, the first entry in the index table will be:

https://issues.apache.org/jira/secure/attachment/12460083/bitmap_index_1.pngImage Removed

The values in the array represent the bitmap for each block, where each 32-bit BigInt value stores 32 rows.

For the second iteration, the first entry will be:

https://issues.apache.org/jira/secure/attachment/12460124/bitmap_index_2.pngImage Removed

This one uses 1-byte array entries, so each value in the array stores 8 rows. If an entry is 0x00 or 0xFF, it represents 1 or more consecutive bytes of zeros, (in this case 5 and 4, respectively)