...
This document explains the proposed design for adding a bitmap index handler (https://issues.apache.org/jira/browse/HIVE-1803).
Bitmap indexing (http://en.wikipedia.org/wiki/Bitmap_index) 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.png
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.png
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)