位图索引的工作原理 - Richard

banq

位图索引用于各种数据技术以实现高效的查询处理。在高层次上，位图索引可以被认为是一组谓词在数据集上的物理具体化，它自然是列式的，特别适合多维布尔查询处理。  当有多个属性受查询约束时（例如在复合 where 子句中），PostgreSQL 会根据查询谓词动态实现位图索引。ElasticSearch 和 Solr 中的过滤器缓存 被实现为文档 ID 上过滤器谓词的位图索引。Pilosa是一个用 Go 构建的分布式位图索引查询引擎，带有一个 Java 客户端库。
位图索引不是一刀切的数据结构，在退化的情况下，它会占用比数据本身更多的空间；在主键上使用位图索引来支持 B 树变体应该被视为滥用。存在各种风格的位图实现，但新兴的事实上的标准是 由Daniel Lemire领导的RoaringBitmap。
 
朴素位图索引
让我们构建一个简单的未压缩位图索引。假设您有一个数据集和某种从现在开始为每条记录分配整数索引或记录索引的方法（最简单的例子是 CSV 文件中的行号），并且已经选择了一些要索引的属性。对于数据的每个索引属性的每个不同值，计算与谓词匹配的记录索引集。对于每个属性，创建从属性值到相应记录索引集的映射。
用于集合的格式尚不重要，但要么是int[] 要么BitSet 根据数据和谓词的属性（例如，数据集的基数、数据集的排序顺序、与谓词匹配的记录的基数）都将是合适的。
下表展示了数据结构。第一个表代表一个简单的数据集。
Record Indices
    Country  Sector 
0             GB    Financials
1             DE    Manufacturing
2             FR    Agriculturals
3             FR    Financials
4             GB    Energies

第二个和第三个表代表数据集上的位图索引，索引Country 和Sector属性。
Country :

      Record Indices            Bitmap
GB    0,4                   0b10001
DE    1                      0b10
FR    2,3                    0b1100

Sector:

         Record Indices            Bitmap
Financials    0,3                  0b1001
Manufacturing   1                  0b10
Agriculturals   2                  0b100
Energies      4                   0b10000

值得注意的是上表中的三种模式。
  1. 一个属性的位图数量是该属性的不同计数。
  2. 通常有零或一的运行，这些运行的长度取决于记录索引属性的排序顺序。
  3. 记录索引属性本身上的位图索引将与数据本身一样大，并且表示形式要少得多。位图索引不与 B 树索引竞争主键属性。
这种简单的方案有效地将谓词对数据的结果具体化，并且特别有吸引力，因为可以通过对位图执行有效的逻辑操作来组合这些谓词。当位图的数量和每个位图的大小都尽可能小时，查询评估是最有效的。无论位图大小如何，高效的查询计划都会尽可能少地接触位图。

无论位图大小如何，高效的查询计划都会尽可能少地接触位图。以下是一些查询示例及其评估计划。

  • 单属性联合 
select *
from records
where country = "GB" or country = "FR"
  1. 访问国家索引，读取值“FR”和“GB”的位图。
  2. 应用按位逻辑 OR 以获取新位图。
  3. 使用检索到的索引访问由记录 id 存储的数据。
 
  • 多属性交集 
select *
from records
where country = "GB" and sector = "Energies"
  1. 访问国家索引，并读取值“GB”的位图。
  2. 访问扇区索引，并读取值“能源”的位图。
  3. 应用按位逻辑 AND 以获取新位图。
  4. 使用检索到的索引访问由记录 id 存储的数据。
....
 
压缩
到目前为止提出的方案可作为玩具模型使用，但位图太大而无法实用。单个属性上的位图索引在m由n记录组成的数据集上具有不同的值，使用 一个BitSet将消耗mn位，使用 一个int[]将消耗32mn位。因此，需要某种压缩才能使该方法可行。
RoaringBitmap 是一种动态数据结构，旨在成为适用于所有场景的通用解决方案。
RoaringBitmap 应该被认为是一组无符号整数，由覆盖不相交子集的容器组成。每个子集可以包含大小范围为 2^16 的值，并且该子集由 16 位键索引。这意味着在最坏的情况下，它只需要 16 位来表示一个 32 位值，因此无符号 32 位整数可以存储为 Java shorts。容器大小的选择也意味着在最坏的情况下，容器仍将适合现代处理器的 L1 缓存。
下面是范围编码位片索引的实现，作为如何使用 RoaringBitmaps 的示例。

public class RangeEncodedOptBitSliceIndex implements RoaringIndex {

  private final int[] basis;
  private final int[] cumulativeBasis;
  private final RoaringBitmap[][] bitslice;

  public RangeEncodedOptBitSliceIndex(ProjectionIndex projectionIndex, int[] basis) {
    this.basis = basis;
    this.cumulativeBasis = accumulateBasis(basis);
    this.bitslice = BitSlices.createRangeEncodedBitSlice(projectionIndex, basis);
  }

  @Override
  public RoaringBitmap whereEqual(int code, RoaringBitmap existence) {
    RoaringBitmap result = existence.clone();
    int[] expansion = expand(code, cumulativeBasis);
    for(int i = 0; i < cumulativeBasis.length; ++i) {
      int component = expansion<i>;
      if(component == 0) {
        result.and(bitslice<i>[0]);
      }
      else if(component == basis<i> - 1) {
        result.andNot(bitslice<i>[basis<i> - 2]);
      }
      else {
        result.and(FastAggregation.xor(bitslice<i>[component], bitslice<i>[component - 1]));
      }
    }
    return result;
  }

  @Override
  public RoaringBitmap whereNotEqual(int code, RoaringBitmap existence) {
    RoaringBitmap inequality = existence.clone();
    inequality.andNot(whereEqual(code, existence));
    return inequality;
  }

  @Override
  public RoaringBitmap whereLessThan(int code, RoaringBitmap existence) {
    return whereLessThanOrEqual(code - 1, existence);
  }

  @Override
  public RoaringBitmap whereLessThanOrEqual(int code, RoaringBitmap existence) {
    final int[] expansion = expand(code, cumulativeBasis);
    final int firstIndex = cumulativeBasis.length - 1;
    int component = expansion[firstIndex];
    int threshold = basis[firstIndex] - 1;
    RoaringBitmap result = component < threshold ? bitslice[firstIndex][component].clone() : existence.clone();     for(int i = firstIndex - 1; i >= 0; --i) {
      component = expansion<i>;
      threshold = basis<i> - 1;
      if(component != threshold) {
        result.and(bitslice<i>[component]);
      }
      if(component != 0) {
        result.or(bitslice<i>[component - 1]);
      }
    }
    return result;
  }

  @Override
  public RoaringBitmap whereGreaterThan(int code, RoaringBitmap existence) {
    RoaringBitmap result = existence.clone();
    result.andNot(whereLessThanOrEqual(code, existence));
    return result;
  }

  @Override
  public RoaringBitmap whereGreaterThanOrEqual(int code, RoaringBitmap existence) {
    RoaringBitmap result = existence.clone();
    result.andNot(whereLessThan(code, existence));
    return result;
  }
}