。

在很多优化规则和物化视图相关的类中都使用了ImmutableBitSet来保存group

by字段或者聚合函数参数字段对应的index#xff0c;例如#xff1a;

//MaterializedViewAggregateRule#compensateViewPartial()…Calcite中实现了一个ImmutableBitSet类用于保存bit集合。

在很多优化规则和物化视图相关的类中都使用了ImmutableBitSet来保存group

//MaterializedViewAggregateRule#compensateViewPartial()

groupSet

groupSet.addAll(aggregateViewNode.getGroupSet());

groupSet.addAll(ImmutableBitSet.range(aggregateViewNode.getInput().getRowType().getFieldCount(),aggregateViewNode.getInput().getRowType().getFieldCount()

offset));因此本文我们就来看一看这个ImmutableBitSet一些核心的操作函数。

使用示例

这里我们介绍一个ImmutableBitSet使用的例子后续相关的函数操作说明会使用这个例子

builder

System.out.println(bitSet.cardinality());

System.out.println(bitSet.nth(1));如上所示通常先构造一个Builder然后set指定的bit位最终构造生成ImmutableBitSet。

下面来看一下主要的成员和关键函数。

主要成员

ImmutableBitSet中比较重要的几个成员变量如下所示

private

ImmutableBitSet(EMPTY_LONGS);private

final

这里最主要的变量就是words这是一个long类型的数组实际存储设置的bit位Long是64位使用6个bit就可以表示因此ADDRESS_BITS_PER_WORD设置为6用来进行一些二进制的左移和右移的运算BITS_PER_WORD表示将1左移6位结果就是64。

当words数组中存在多个成员的时候取指定long成员对应的bit位时会用到后面会详细介绍这里不再赘述。

Builder相关函数

要使用ImmutableBitSet我们首先需要构造一个ImmutableBitSet.Builder因此先看一下这个Builder的关键函数。

set(int

set函数是最常用的将指定位的bit设置为true表示该位上面有值对应的函数代码如下所示

public

}通过这个函数就可以往Builder里面设置对应的bit位上述代码主要处理逻辑如下

通过传入的bit位获取在words中的索引即数组的下标通过wordIndex函数来实现。

这个函数只有一行代码即将传入的bit右移6位。

其效果是063会返回0表示存储在words中的第一个long成员64127返回1表示存储在words中的第二个long成员以此类推如果word索引大于当前数组的长度则会扩容数组长度1将1L左移bit位并与指定index的数组成员即words[wordIndex]进行或操作并更新到当前数组成员然后返回。

//3

builder.set(129);这里我们只展示了二进制的最后8位前面56位都是0因此省略。

此时words包含3个long成员分别是

1000

需要注意的是在对1L进行左移操作时由于long是64位的因此我们需要先对bit进行64取余操作因此上面大于64的左移操作实际效果如下

(67

Builder填充完成之后就可以通过build()方法来生成ImmutableBitSet对象了。

这个函数比较简单就是将words成员作为参数来构造ImmutableBitSet同时将words成员本身置空。

也就是说Builder只能调用一次build()这点需要注意。

bitSet)

set方法只能设置单个bit位如果想要批量设置的话可以调用addAll()函数。

这个函数有三个重载方法这里我们看一下与ImmutableBitSet相关的

public

}该方法比较简单就是通过ImmutableBitSet的iterator()方法来获取每一个bit然后set到当前的Builder中。

关于iterator()处理逻辑我们下面再介绍。

ImmutableBitSet相关函数

看完Builder常用的几个函数后我们再来看一下ImmutableBitSet相关的函数。

cardinality()

这个函数会返回当前ImmutableBitSet包含的所有bit位相关代码如下所示

public

}可以看到实际是通过countBits函数来进行统计的。

该函数会遍历words数组所有的成员依次统计每个成员包含的bit位然后累计求和。

在上述例子中对应的cardinality就是5表示一共有5个bit位被设置为true前面两个成员分别包含2个为true的bit位第三个成员包含1个。

nth(int)

该函数是Calcite中也会经常用到的。

该函数的功能是取第n位对应的值代码如下所示

public

IndexOutOfBoundsException(index

out

遍历words数组通过每个成员包含的bit位数量来确定第n个bit位于哪个数组成员遍历的同时更新每个数组成员对应的起始值start第一个成员是0第二个成员是64第三个成员是128依次类推定位到对应的数组成员之后循环处理这个long每次右移1位然后start加1右移1位之后判断long的最后一位是否为1是的话则表示该bit位被set过然后再判断是否为第n个bit是的话则直接返回start。

否则继续右移long然后更新start。

iterator()

上面我们提到Builder.addAll()函数主要就是通过ImmutableBitSet的迭代器iterator()来实现批量set的这里我们就来看一下ImmutableBitSet是如何实现的。

当我们使用for循环取ImmutableBitSet的成员时会自动调用迭代器的next()函数不断获取下一个成员next()函数实现

Override

}可以看到这里主要是通过nextSetBit()函数来取下一个bit位的下面我们看下这个函数的实现逻辑。

nextSetBit(int

这个函数是用来取给定bit位以及其之后的下一个被set的bit位包含fromIndex对应的bit位本身函数代码如下所示

public

IndexOutOfBoundsException(fromIndex

fromIndex);}int

Long.numberOfTrailingZeros(word);}if

words.length)

获取传入index所在的数组成员下标即位于第几个数组成员中将word

1000省略mask前面的1然后将该结果与对应的数组成员进行与操作得到一个新的word。

这行代码的目的是为了屏蔽index前面的成员进行后续的比较。

例如数组成员是1111

1000。

那么word最后三个1对应十进制的1、2、4都被屏蔽如果word为空表示传入的index不在当前这个word中对应的bit没有被set此时更新word为下一个数组成员。

由于下一个数组成员的起始index是必定大于传入index的因此word不需要进行上面的左移和与操作word不为空先获取trailing

zero数量然后加上实际的offset即可数组成员每往后移动一个index起始offset就要加64。

我们同样使用上述的例子来看一下。

fromIndex设置为6时整个流程如下所示

get(int

IndexOutOfBoundsException(bitIndex

bitIndex);}int

bitIndex)如果为0表示对应bit没有被set即为0。

这里我们仍然结合上述例子来看

//假设bitIndex为69此时位于words的第二个数组成员范围为64127

(75

//假设bitIndex为75此时位于words的第二个数组成员范围为64127

(75

0因此get(69)返回true对应上述示例的set(70)get(75)则返回false。

本文主要介绍了Builder和ImmutableBitSet中的一些关键函数的处理逻辑并结合示例展示了具体的用法。

ImmutableBitSet还有不少其他的函数其中大多都是基于上述的函数进行实现或者本身实现比较简单这里不再一一介绍有兴趣的同学可以自行阅读源码。

set笔者猜测应该是跟逻辑执行计划有关。

使用ImmutableBitSet可以通过与操作快速判断字段对应的index是否在bit

set中效率比较高。

后续阅读到planner优化相关的代码时再做分享。