Using Bitmaps to Perform Range Queries(featurebase.com)
featurebase.com
Using Bitmaps to Perform Range Queries
https://www.featurebase.com/blog/range-encoded-bitmaps
3 comments
This post discusses how FeatureBase uses Bit-sliced indexes to significantly reduce the number of bitmaps needed to represent a range of integer values. And by applying range-encoding to the indexes, it is able to perform lightning fast range queries.
Interesting, but I feel like they took the long way around to arrive in the end at a fairly "obvious" representation - slices of the binary encoded bits.
And the big question is how does the performance actually compare against scanning an array of ints.
And the big question is how does the performance actually compare against scanning an array of ints.
This was my thought when we first wrote this back in... 2018 or whatever. The papers referenced sort of derive this technique in that way that feels rather roundabout. For the actual implementation we took the more direct approach... though I think we did switch from a twos complement to a sign/magnitude representation at one point which allows us to dynamically vary the bit depth used which can save some space and computation time.
As far as the performance goes, in this system, we represent almost everything with compressed bitmaps, so there's some advantage to using them for integers and range queries as well as the output of a range query is very naturally a bitmap which can easily be combined with more typical categorical bitmaps when evaluating more complex queries.
As far as the performance goes, in this system, we represent almost everything with compressed bitmaps, so there's some advantage to using them for integers and range queries as well as the output of a range query is very naturally a bitmap which can easily be combined with more typical categorical bitmaps when evaluating more complex queries.