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] [Updated] (CASSANDRA-9843) Augment or replace partition index with adaptive range filters
Date Sat, 18 Jul 2015 04:08:04 GMT

     [ https://issues.apache.org/jira/browse/CASSANDRA-9843?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Jonathan Ellis updated CASSANDRA-9843:
--------------------------------------
    Labels: performance  (was: )

> 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
>              Labels: performance
>
> 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