多维查询之Bitmap索引

维度列构建维度字典

维度字典最核心的是两个Map映射：valueToId和idToValue，以City列为例，该列有三个值，构建出的字典就是 valueToId : <SanFrancisco, 0>, <Taiyuan,1>, <Calgary, 2>，
idToValue是map反过来。可以看出来，构建字典就是为维度列的取值赋一个自增的Int值。
同理，可以分别为Page列、UserName列和Gender列构建相应的维度字典，构建完成之后，原始表中第三行的所有维度列就不再是Page:Ke$ha, UserName:Helz, Gender:Female, City:Calgary，而是[1, 2, 1, 2]。

image.png

1: 用字典对列中的string值做映射到唯一的int id
  {
    "Justin Bieber": 0,
    "Ke$ha":         1
  }

2: 把映射后的id存入column中
  [0,
   0,
   1,
   1]

3: 生成位图
  value="Justin Bieber": [1,1,0,0]
  value="Ke$ha":         [0,0,1,1]

Bitmap索引

每个维度列实际上都会维护一个Bitmap数组：MutableBitmap[]，数组大小为每个维度列的可取值多少（Cardinality），比如Gender列只有Male和Female两个取值，Bitmap数组大小就为2。数组的第一个值为Male对应的位图数据MutableBitmap，数组的第二个值为Female对应的位图数据MutableBitmap。这里就有一个问题，为什么说数组的第一个值是Male对应的位图数据，而不是第二个值呢？这就是用到了上文中提到的维度字典，Male对应的维度字典值为0，就对应数组下标为0；Female对应的维度字典值为1，对应数据下标就为1。

查询维度字典
{
"Justin Bieber": 0,
"Ke$ha": 1
}

维度值对应的维度字典中的id

查询过程

通过id找到维度列MutableBitmap[] 对应的维度值的下标,就是value->id的id
因为id是根据出现前后递增的
MutableBitmap 就是对应列值的位图数据
然后遍历位图数据,找到为1的行号
查询对应列中行号对应的数据

构建Bitmap索引

1. 首先会为每一行生成一个自增的rowNum

2. 遍历所有维度列，分别为每个维度列构建相应的Bitmap数组

   针对某个纬度列的value值，首先在维度字典中根据value找到对应的id，这个id即是Bitmap数组的下标，根据这个下标找到该value对应的位图数据，即MutableBitmap[id]
   定位到位图数据之后，再将该位图下标为rowNum的bit位置为1

参考资料
https://zhuanlan.zhihu.com/p/53379636
http://hbasefly.com/2018/06/19/timeseries-database-8/