Min-Max索引

Iceberg默认提供了MinMax索引，在Iceberg表的Manifest文件中，存储了数据文件每个列的Min/Max值， 使用Spark等引擎访问Iceberg表的时候，在分布式任务初始化阶段，会从Iceberg表的Manifest文件中获取文件列表及相关信息，并使用SQL中的过滤条件，尝试根据MinMax索引跳过不需要的文件。如上所述，想要更好的发挥MinMax索引的效果，数据在表文件中的分布至关重要，在一个多维分析场景中，通常过滤字段的都不止一个，对于多个常用过滤字段，无法依靠简单的自然排序，使得MinMax索引对于多个过滤字段都有比较好的筛选效果，对于2-4个左右使用ZOrder排序的过滤字段，在带上相关过滤条件的查询中，都可以有比较好的Data Skip效果，但是MinMax索引依然有不足之处，主要体现在两个方面：

1. 常用过滤字段越多，ZOrder排序后排序字段的数据聚集性越差，MinMax索引过滤效果也就越差，一般不建议超过4个，实际场景如果超过了4个过滤字段，未进行ZOrder排序字段的聚集性无法保证，MinMax索引的效果也会大打折扣。
2. MinMax索引对于取值越密集的字段越友好，对于取值越稀疏的字段越不友好。比如如果表文件字段a的MinMax是[0, 9999]，在文件中实际a的取值只有100个，那么如果查询过滤条件是等于这100个值以外的其他9900个值的任意一个，理论上是不需要实际访问这个文件的，但是MinMax索引并不能跳过这个文件，因为过滤条件的值在[0, 9999]范围中。
   

为什么要引入到更细粒度的索引？

举例：下面有两个datafile和menifest文件，内容如下
datafile1

datafile2

manifest file

针对SELECT * FROM table WHERE age > 50，利用 min-max 统计信息，很容易发现 data file 1 中没有满足条件的数据，因此 data file 1 就不会参与计算。
但是针对多维分析，如name = 'LiLy' AND age > 30，利用name和age的min-max的统计信息分别对条件name = 'LiLy'和age > 30进行判断，得到 data file 1 和 data file 2 都满足条件。然而，仔细分析 data file 1 和 data file 2 的数据，并不存在符合条件的数据，因此 min-max 过滤效果不太理想。所以通过引入合适的索引功能，可以提高 data skipping 的概率，提高查询性能。

布隆过滤器

对于写入时的非排序字段，数据随机散布于各个文件，使用该字段过滤时，MinMax索引基本很难有文件Skip的效果，BloomFilter索引在这种场景下可以更好地发挥作用，尤其是当字段基数较大的时候。布隆过滤器实际上是一个很长的二进制向量和多个Hash函数，数据通过多个函数映射到二进制向量的比特位上，布隆过滤器的空间效率和查询时间都非常高效，非常适合用于检索一个元素是否存在于一个集合中。布隆过滤器存在False-Positive可能，即检索元素是否存在返回True，但实际并不存在的可能，根本的原因是因为Hash冲突导致多个元素会被映射到相同的比特位上，一般的布隆过滤器实现都提供了两个初始化参数，元素数量和FPP(False-Positive-Probabilistic)，通过设置fpp的大小，可以控制出现False-Positive的概率，fpp越小，布隆过滤器需要的比特位越多。
布隆过滤器的空间效率和查询时间都非常高效，但是在使用上也有局限之处，主要是它能够支持的过滤条件是有限的，只适用于：=，IN，NotNull三个表达式，对于常见的Range过滤，比如>, >=, <, <=等是不支持的。为了支持更丰富的过滤表达式，我们引入了BitMap索引的支持。

BitMap索引

这里举一个具体的例子分析，某一个表中有两个字段，price和city，这两列的数据如下

可以看到这张表有9行，price的值有[2,18,20,33,50,188]这几个值出现。这些数据在后面的BitMap变种中会用到。

普通BitMap

BitMap也是一个非常常见的数据结构，将一组正整形数据映射到比特位，相比于BloomFilter，不存在Hash冲突的情况，所以不会出现False-Positive，但是一般需要更多的存储空间。BitMap在数据稠密的时候，非常节省空间，但是在数据稀疏的时候，会有极大的浪费。

对于上面的例子来讲，BitMap会以具体的值来存放其bit位是否为1，也就是在BitMap中[2,18,20,33,50,188]这些值的bit位都为1，其他的值为0.

EQUALITY-ENCODED BITMAP

对于上面的例子来讲，我们将price列的每个元素值所在的行号找出来构建BitMap，列为行号，0代表该字段值未出现在该行，1代表该字段值出现在该行，city同理，示意如下：

这样可以得到6个BitMap，对于查询 price < 19 的情况，从有序数组中判断包含2和18两个取值，把对应的BitMap取出进行bitmapOr计算，得到结果为011010000。由于是根据字段取值的行号构建的BitMap，所以不同字段的BitMap也可以进行交并计算，比如对于过滤条件price < 19 AND city = 'street5'，根据price < 19得到的BitMap为011010000，根据city = 'street5得到的BitMap为000001111，虽然根据单个过滤条件都无法跳过该文件，但是根据AND进行bitmapAnd操作后得到的结果为000000000可以判断文件中不包含满足过滤条件的数据行，所以可以跳过该文件。

对于>, <, >=, <=等范围过滤条件，BitMap索引也可以支持，但是代价比较大，比如对于lprice < 90,我们需要把全部的6个Bitmap全部取出来进行计算，在字段基数比较高的情况下，这可能耗费大量的时间和机器资源，Range-Encoded Bitmap可以用来解决这个问题。

Range-Encoded Bitmap

采用Range-Encoded编码的bitmap示例如下：

相比于上一节的Equality-encoded，对于Range-Encoded编码来说，不仅字段某个取值对应行号比特位设置为1，所有大于该取值的值，在对应行号的比特位也置为1， 以20为例，price==20出现在第0行，所以20以及大于20的取值（33，50， 188）在第0行的比特位都被置为了1。Range-Encoded下price==20的Bitmap值相当于Equality-encoded下所有小于等于20的Bitmap交集的结果。采用这样的编码方式使得对于等值和范围过滤条件都能够非常高效地计算出最终结果：

1. 对于等值过滤，比如price==20，我们找到20对应的Bitmap bm_20以及上一个取值18对应的Bitmap bm_18，用bm_20.andNot(bm_18)即可得到结果。
2. 对于小于或小于等于，比如price<19，我们找到小于19最接近的取值18对应的Bitmap bm_18即为最终结果。
3. 对于大于或大于等于，比如price>30，我们找到最大取值188的Bitmap bm_188，以及小于30最接近的取值20的Bitmap bm_20， 用bm_188.andNot(bm_20)即可得到结果。

可以看到，采用Range-Encoded编码后，我们最多取两个Bitmap即可计算任意等值或大于小于过滤条件的结果，和字段基数大小没有任何关系。这对于BitMap计算十分高效，但是对于基数比较高的字段，我们构建Bitmap索引时，依然要生成存储对应基数个数的Bitmap，存储的索引文件过大，不仅要占用大量的存储空间，查询的效率也会收到很大影响。

Bit-Sliced Encode BitMap

其主要原理是根据一个数据的位数来划分Slice的，比如20这个数个位为0，十位为2，百位为0，在图中表示为：slice-0（0），slice-1（2），slice-3（0），其他的数据也是一样

这样可以使用30个BitMap就可以表示0-999范围的数字。

后续还可以与Rang-Encoded BitMap结合，达到28个BitMap就可以表示0-999范围的数字的效果。
如果你希望进一步减少BitMap的数量，那么可以这种十进制的slice方式改为二进制，可以缩减为10个！
这里不过多赘述，详情可以参考写的这篇文章：
Using Bitmaps to Perform Range Queries