cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jonathan Ellis (JIRA)" <j...@apache.org>
Subject [jira] [Created] (CASSANDRA-9843) Augment or replace partition index with adaptive range filters
Date Sat, 18 Jul 2015 04:02:04 GMT
Jonathan Ellis created CASSANDRA-9843:
-----------------------------------------

             Summary: Augment or replace partition index with adaptive range filters
                 Key: CASSANDRA-9843
                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9843
             Project: Cassandra
          Issue Type: New Feature
          Components: Core
            Reporter: Jonathan Ellis
            Assignee: T Jake Luciani


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



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message