Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-1723

Add Bitmap indexes

    XMLWordPrintable

Details

    • New Feature
    • Status: Backlog
    • Major - P3
    • Resolution: Unresolved
    • None
    • None
    • Index Maintenance
    • None

    Description

      As an alternative to a B+Tree, using Bitmap Indexes (http://en.wikipedia.org/wiki/Bitmap_index) could allow a very speedy retrieval of simple queries like the equivalent of "SELECT * FROM FOO WHERE GENDER = "MALE" AND "STUDENT" = TRUE.

      Bitmap indexes used to be thought of a "low cardinality" thing, but in "An Adequate Design for Large Data Warehouse Systems: Bitmap index versus B-tree index" by Zaker et al, the authors go even as far as saying that for certain situations, the cardinality of the values does not even matter. Their conclusive statement is as follows:

      Thus, we conclude that Bitmap index is the conclusive choice for a DW designing no matter for columns with high or low cardinality.

      A highly optimized C++ library called Fastbit (https://sdm.lbl.gov/fastbit/) already exists.

      Especially when using large amounts of data that have a low cardinality (e.g. a 'gender' field), the compressed bitmap indexes could keep the RAM usage low and outperform B+Trees.

      Attachments

        Activity

          People

            backlog-query-optimization Backlog - Query Optimization
            rb2k Marc Seeger
            Votes:
            51 Vote for this issue
            Watchers:
            43 Start watching this issue

            Dates

              Created:
              Updated: