Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@cassandra.apache.org
Date: Fri, 3 Jul 2015 09:29:05 +0000 (UTC)
From: "Benedict (JIRA)" <jira@apache.org>
To: commits@cassandra.apache.org
Message-ID: <JIRA.12832471.1432541421000.93011.1435915745247@Atlassian.JIRA>
In-Reply-To: <JIRA.12832471.1432541421000@Atlassian.JIRA>
References: <JIRA.12832471.1432541421000@Atlassian.JIRA>
 <JIRA.12832471.1432541421751@arcas>
Subject: [jira] [Commented] (CASSANDRA-9471) Columns should be backed by a
 BTree, not an array
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/CASSANDRA-9471?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14613058#comment-14613058 ] 

Benedict commented on CASSANDRA-9471:
-------------------------------------

Well, the decision does ultimately affect how certain features within the btree are implemented - or at least the cost/benefit analysis (for the reviewer as much as myself). Right now I've used the indexability feature to make a trivial implementation of lower/higher/floor/ceil, because it permits you to treat the whole btree as though it were an array for indexing, using binarySearch semantics and positional access. If we choose not to include this feature, it would be better to implement these directly - not onerous, of course, but I want to avoid burdening branimir with unnecessary review. There's also some intertwining on testing (using higher features to help test lower ones).

However you make a good point, and I will see what minimal set of changes I can extract to get the ball rolling. It's probably still pretty significant and helpful.

> Columns should be backed by a BTree, not an array
> -------------------------------------------------
>
>                 Key: CASSANDRA-9471
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9471
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Benedict
>            Assignee: Benedict
>             Fix For: 3.0 beta 1
>
>
> Follow up to 8099. 
> We have pretty terrible lookup performance as the number of columns grows (linear). In at least one location, this results in quadratic performance. 
> We don't however want this structure to be either any more expensive to build, nor to store. Some small modifications to BTree will permit it to serve here, by permitting efficient lookup by index, and calculation _of_ index for a given key.


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