Return-Path: X-Original-To: apmail-cassandra-commits-archive@www.apache.org Delivered-To: apmail-cassandra-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 2BDA61830C for ; Sat, 18 Jul 2015 04:08:05 +0000 (UTC) Received: (qmail 43931 invoked by uid 500); 18 Jul 2015 04:08:04 -0000 Delivered-To: apmail-cassandra-commits-archive@cassandra.apache.org Received: (qmail 43893 invoked by uid 500); 18 Jul 2015 04:08:04 -0000 Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@cassandra.apache.org Delivered-To: mailing list commits@cassandra.apache.org Received: (qmail 43701 invoked by uid 99); 18 Jul 2015 04:08:04 -0000 Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 18 Jul 2015 04:08:04 +0000 Date: Sat, 18 Jul 2015 04:08:04 +0000 (UTC) From: "Jonathan Ellis (JIRA)" To: commits@cassandra.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Updated] (CASSANDRA-9843) Augment or replace partition index with adaptive range filters MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ 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)