Use Sparse Bitmaps

[tomijaga]

Changes to make

Update the bitmap implementation to include a sparse bitmap that uses the roaring bitmap compression

Why We need this change?

Our index scans return a range of ids which are often not in order and have holes in them. These ids are loaded into a bitmap to perform set operations. But due to the way the general bitmap works it wastes space allocating memory for all elements between 0 and the largest id in the range even though if they not present in the id range.

Consider an index scan that returns the range (10_000_000, 10_000_005).
The current bitmap implementation will allocate space for every value from 0 to 10_000_005 and only set the last 5 elements to true, wasting space for the 10 million elements elements in between.

The sparse bitmap implementation will avoid allocating space for those 10 million ids. Which would in turn reduce our memory usage and wasm instructions, and result in faster queries.