KtSQL的BitmapInvertedIndex

发表于

目录

  • 引入Bitmap倒排索引
  • BitmapInvertedIndex
  • KtSQL的实现思路
  • 附录

引入Bitmap倒排索引

多维查询支持对于复杂化查询是一项必备的功能，KtSQL在设计时，则把复杂化查询作为一项核心特性考虑到系统实现中。对于以实时小批量查询为主要应用场景的事务型数据库，bitmap索引自然成为首选的对象之一。

复杂查询中，bitmap支持对某类对象的特性进行查询，如查询符合某些过滤条件的物品。bitmap还可以对多个集合间的关系进行处理，如进行or或and处理。bitmap还支持如TopN、contains、Total等操作，对于计算下推，这些功能都有极大的帮助。

不同于bitmap是把多个维度值作为一个单值进行编码，倒排索引对每一个column的值进行编码。倒排索引帮忙我们把每一个列(column)的取值映射到编码后，建立起取值编码和对应的rowkey位置的关系。通过bitmap计算，即可快速得出取值对应的rowkey值。

BitmapInvertedIndex

BitmapInvertedIndex在OLAP是较常见的，业界有名的案例是apache druid, linkedin pinot。

Pinot BitmapInvertedIndex的实现细节描述如下：

  1. 使用roaringbitmap作为底层的实现支持
  2. 数据保存在文件上，inverted index存储的方式：|1st start|1st end|2nd end|…|data for 1st bitmap|data for 2nd bitmap|…
  3. 支持保存在OnHeap和OffHeap，接口提供了addSingleColumn和addMultiColumn，参数为docId和dictId
  4. 每一个column会创建一个InvertedIndexCreator，以OnHeapBitmapInvertedIndexCreator为例
  5. 每个OnHeapBitmapInvertedIndexCreator包含一个MutableRoaringBitmap[]，用来保存每个column的bitmap array
  6. MutableRoaringBitmap支持serialize写到stream

KtSQL的实现思路

参考Pinot的实现，先实现OnHeap模式，创建inverted index时，每个column创建一个bitmapInvertedIndex，采取实时构建的方式，通过适当牺牲入库的性能，避免复杂化数据的查询步骤，流程如下：

  • 将rowkey映射到array index中，把rowkey编码成唯一值，如取值为long，可以容纳 2^64 的数值
  • 不允许对建立了位图倒排索引的数据记录进行删除，也不允许对rowkey进行修改
  • 将每一个column的取值进行编码（依赖全局字典），对该取值维护一个队列，记录该值所在的rowkey对应的long值
  • 因为每个取值都会消耗掉一个array，所以column的取值越多，存储空间消耗越大。所以有观点提出column取值应该在10万以下，过多则不适合建立bitmap索引。
  • 全局字典表在分布式环境下，面临一个同步的问题，构建全局字典表。需考虑算法上支持特定值的编码在不同环境下取值一致是否可行，否则就需要用强一致的共享内存进行编码同步处理。
  • 位图倒排索引的数据保存在hbase中。在分布式环境下不同节点都需要访问同一份位图倒排索引，也需要维护数据和位图倒排索引的强一致性。这种处理方法也可避免在内存中过大。

实时入库，会面临rowkey动态增加和column值编码持续增加的情况，也要面对分布式环境下编码一致性的问题

附录