IndexDev Bitmap

=位图索引=

Introduction

本文档介绍了用于添加位图索引处理程序(https://issues.apache.org/jira/browse/HIVE-1803)的建议设计。
位图索引(http://en.wikipedia.org/wiki/Bitmap_index)是索引几乎没有区别的列的标准技术
价值观，例如性别。

Approach

我们希望开发一种位图索引，该索引可以重用尽可能多的现有紧凑索引代码。

Proposal

First implementation

此实现具有位图索引的某些优点，并且在给定已经存在的紧凑索引的情况下应该易于实现，但是它很少进行 true 的好位图索引应该进行的优化(例如压缩)。

像复杂索引一样，此实现使用索引表。列“键”上的索引表具有四列或更多列：首先是要构建索引的列，然后是_bucketname，_offset 和_bitmaps。 _bucketname 是一个字符串，指向在表中存储此块的 hadoop 文件，_offset 是块的块偏移量，_bitmaps 是该列值的值的未压缩位图编码(字节数组)，存储桶名称，和行偏移量。位图中的每个位对应于块中的一行。如果该行具有要索引的列中值的值，则该位为 1，否则为 0.如果键值根本没有出现在块中，则该值不会存储在 Map 中。

查询此索引时，如果对带位图索引的谓词执行布尔“或”或“或”运算，我们也可以使用按位运算来尝试消除块。然后，我们可以消除不包含我们感兴趣的值组合的块。我们可以使用此数据来生成文件名，紧凑索引处理程序使用的块偏移量格式数组，并在位图索引查询中重用它。

Second iteration

基本实现的唯一压缩是消除所有行均为 0 的块。对于较大的块，这种情况不太可能发生，因此我们需要更好的压缩格式。我们可以做的是字节对齐的位图压缩，其中位图是一个字节数组，一个全 1 或全 0 的字节表示一个或多个字节，每个值均为 0 或 1.然后，我们只需要在位图索引表中添加另一列，该列是一个由整数组成的数组，这些数组描述了间隔多长时间以及扩展压缩的逻辑。

Example

假设我们在一个键上有一个位图索引，其中在第一个块上，值“ a”出现在第 5、12 和 64 行中，值“ b”出现在第 7、8 和 9 行中。实施中，索引表中的第一个条目将是：

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

数组中的值表示每个块的位图，其中每个 32 位 BigInt 值存储 32 行。

对于第二次迭代，第一个条目将是：

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

这个使用 1 字节数组条目，因此数组中的每个值存储 8 行。如果条目是 0x00 或 0xFF，则它表示 1 个或多个连续的零字节(在这种情况下分别为 5 和 4)