Implement Bit-sliced index for CRoaring

[Smallhi]

There are implements for bit slice index in java and go. Do we need in C/C++?

I think implementing Bit-sliced index for CRoaring include these tasks:

• support mutable Bit-sliced index in C
• support RangeBitmap in C
• A range Index demo for postgres using RangeBitmap in C
• A mutable bit-sliced index demo for postgres using bit-sliced index in C
• A range index demo for Apache Parequet file-format in C/C++
• A mutable bit-sliced index demo for Apache Parequet file-format using Bit-sliced index in C

@lemire we've implemented mutable Bit-sliced index in C and using it for postgres. Due to there are two implements for bit-sliced index, (BSI and RangeBitmap), one is mutable but the performance is poor, the other is immutable ,but the performance is great. Could we make a decision or re-design it ?

cc @ richardstartin

refer to :

1. https://richardstartin.github.io/posts/range-bitmap-index
2. https://richardstartin.github.io/posts/range-predicates
3. https://github.com/RoaringBitmap/RoaringBitmap/tree/master/bsi
4. could you merge this lib to RoraringBtimap? lemire/BitSliceIndex#1

[lemire]

Yes, a pull request to provide this functionality in C is invited.

[patelprateek]

@Smallhi : I alos have this use case , any idea when would we be able to merge this implementation.
Also i have a noob question : Why is bit sliced index dependent on Rangebitmap implementation ? What exactly is the difference between range index and bit slice index ?

[goldenbean]

@Smallhi I just made my own header-only BSI impl based on CRoaring, and will upload whole project soon.... :) you could check it out if you still need it. https://github.com/goldenbean/BSI/blob/main/roaring64bsi.hh

[Smallhi]

@goldenbean That's Great！And two more suggestion:

1. I think that's would be good if the layout had magic Number for the puposre of upgrading.

you can learn from here https://github.com/RoaringBitmap/CRoaring/blob/master/src/roaring_array.c#L551

// This function is endian-sensitive.
size_t ra_portable_serialize(const roaring_array_t *ra, char *buf) {
char *initbuf = buf;
uint32_t startOffset = 0;
bool hasrun = ra_has_run_container(ra);
if (hasrun) {
uint32_t cookie = SERIAL_COOKIE | ((uint32_t)(ra->size - 1) << 16);
memcpy(buf, &cookie, sizeof(cookie));
buf += sizeof(cookie);
uint32_t s = (ra->size + 7) / 8;
uint8_t *bitmapOfRunContainers = (uint8_t *)roaring_calloc(s, 1);
assert(bitmapOfRunContainers != NULL); // todo: handle
for (int32_t i = 0; i < ra->size; ++i) {
if (get_container_type(ra->containers[i], ra->typecodes[i]) ==
RUN_CONTAINER_TYPE) {
bitmapOfRunContainers[i / 8] |= (1 << (i % 8));
}
}

....

2. try your best to use inplace not new bitmap object. That improve performace greatly in postgres Aggregation operation.

[goldenbean]

the suggestions sound great for me. I will take a close look at this and consolidate the changes before uploading whole project to github.

@goldenbean That's Great！ I think that's would be good if the layout had magic Number for the puposre of upgrading. you can learn from here https://github.com/RoaringBitmap/CRoaring/blob/master/src/roaring_array.c#L551

// This function is endian-sensitive. size_t ra_portable_serialize(const roaring_array_t *ra, char *buf) { char *initbuf = buf; uint32_t startOffset = 0; bool hasrun = ra_has_run_container(ra); if (hasrun) { uint32_t cookie = SERIAL_COOKIE | ((uint32_t)(ra->size - 1) << 16); memcpy(buf, &cookie, sizeof(cookie)); buf += sizeof(cookie); uint32_t s = (ra->size + 7) / 8; uint8_t *bitmapOfRunContainers = (uint8_t *)roaring_calloc(s, 1); assert(bitmapOfRunContainers != NULL); // todo: handle for (int32_t i = 0; i < ra->size; ++i) { if (get_container_type(ra->containers[i], ra->typecodes[i]) == RUN_CONTAINER_TYPE) { bitmapOfRunContainers[i / 8] |= (1 << (i % 8)); } }

....