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

Add Bitmap indexes

    XMLWordPrintable

    Details

    • Type: New Feature
    • Status: Open
    • Priority: Major - P3
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: Backlog
    • Component/s: Indexing
    • Labels:
      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

            • Votes:
              48 Vote for this issue
              Watchers:
              39 Start watching this issue

              Dates

              • Created:
                Updated: