BitmapBuilder should be aware of compacted bitmap(all 1 bitmap)

[yuhao-su]

currently, we have a Vis

pub enum Vis {
    Bitmap(Bitmap),
    Compact(usize), // equivalent to all ones of this size
}

When the bitmap got from bitmapbuilder.finish returns a all 1 bitmap, it should actually be compacted.

[fuyufjh]

Please feel free to reassign

[y-wei]

I find many callers that expect a Bitmap from .finish(). Sizable refractors were needed if we want to have .finish() returning a Vis. Do we still want this feature?

[TennyZhuang]

Bitmap is used in many places, e.g. Vnodes. If you like to optimize for Vis, you should introduce VisBuilder. Anyway, do you have any performance result that indicates we need to optimize it?

[TennyZhuang]

Sorry @Eurekaaw, I have removed the good first issue label here since we need to discuss it first. Welcome to the discussion.

Here are some backgrounds:

1. Bitmap is a common utility, similar to bitvec, and it's used in many places, including

• mask for chunk, for the lazy materialization
• vnode bitmap, represents the distribution
• bloom filter

2. We may always introduce a Compact chunk only for the chunk. In other cases, it's likely a downgrade, since a compacted vnode mapping is rare. So we introduce the Vis to optimize the chunk.
3. Even for chunks, we have no benchmark about whether it's worth introducing the Vis, since the overhead of a Bitmap is really low. 1024-records only need 128 bytes. I guess it's may introduce a few benefits.
4. BitmapBuilder is used to build a Bitmap but not Vis. If you really want that, you should wrap a VisBuilder.
5. The compacted Vis is constructed directly, from the source, table_scan, exchange, etc. If we construct a Bitmap instead, it's likely under a prediction but all true, is it a common case? What's your target scenario?

[y-wei]

My intuition is that in cases where we call BitmapBuilder.finish() and optimize if the returned Bitmap.all(), simply returning a Vis::Compact may buy us a few benefits. OTOH I agree with you that Bitmap's over head is not likely to be significant and my intuitively optimized case seems rare. Could you please elaborate more about this issue? @yuhao-su