Using Bitmaps to Perform Range Queries

49 points by maycotte 2 years ago | 3 comments
  • maycotte 2 years ago
    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.
    • tveita 2 years ago
      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.

      • jaffee 2 years ago
        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.