Uploaded image for project: 'Cassandra'
  1. Cassandra
  2. CASSANDRA-9843

Augment or replace partition index with adaptive range filters

    Details

    • Type: New Feature
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Fix Version/s: None
    • Component/s: None
    • Labels:

      Description

      Adaptive range filters are, in principle, bloom filters for range queries. They provide a space-efficient way to avoid scanning a partition when we can tell that we do not contain any data for the range requested. Like BF, they can return false positives but not false negatives.

      The implementation is of course totally different from BF. ARF is a tree where each leaf of the tree is a range of data and a bit, either on or off, denoting whether we have some data in that range.

      ARF are described here: http://www.vldb.org/pvldb/vol6/p1714-kossmann.pdf

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                jbellis Jonathan Ellis
              • Votes:
                0 Vote for this issue
                Watchers:
                17 Start watching this issue

                Dates

                • Created:
                  Updated: