Bitmap Index Design and Evaluation

 

Bitmap indexing has been touted as a promising approach for processing complex adhoc queries in read­mostly environments, like those of decision support systems. Nevertheless, only few possible bitmap schemes have been proposed in the past and very little is known about the space­time tradeoff that they offer. The paper present a general framework to study the design space of bitmap indexes for selection queries and examine the disk­space and time characteristics that the various alternative index choices offer. In particular, it draw a parallel between bitmap indexing and number representation in different number systems, and define a space of two orthogonal dimensions that captures a wide array of bitmap indexes, both old and new.

Within that space, it identify the following interesting points:

  • The time­optimal bitmap index;

  • The space­optimal bitmap index;

  • The bitmap index with the optimal space­time tradeoff (knee).

  • The time­optimal bitmap index under a given disk­space constraint.

    • It also examine the impact of bitmap compression and bitmap buffering on the space­time tradeoffs among those indexes. As part of this work, it also describes a bitmap­index­based evaluation algorithm for selection queries that represents an improvement over earlier proposals.

    .

    The best way to get the filling what this is about is by the examples:

    Bitmap in the simple form: Value list bitmap.

    E ach column represents one possible value.

    1 for the value 0 otherwise.

    .

     

    Attribute Value Decomposition.

     

     

    Range Encoding Bitmap Indexes:

        Vi righ most bits 0, rest 1.
         

     

     

    Evaluation Algorithm for

    Range-Encoded Bitmap Indexes:

      RangeEval-Opt: HighLights

  • number bitmap operation 50% off

  • less bitmap scans for range predicate evaluation

  • caluclating only the requested bitmap

  • avoids the intermediate equality predicate evaluation by evaluating each range query in term only off <= based on:

  • A < v == A<=v-1

  • A > v == ! (A<=v)

  • A>=v == A<=v-1

  • Working with only one bitmap B vs. working with at least two
    [Beq and ( Blt or Bge)]

    •  

    For A <= 864 Queruy using a 3 component base-10 index

    Range Eval Range Eval-Opt

     

     

     

    These are the key feature of bitmaps indexes that gives an idea to the reader what this all about. For getting more knowladge you can look at the paper Bitmap Index Design and Evaluation