cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9471) Columns should be backed by a BTree, not an array
Date Fri, 03 Jul 2015 10:02:05 GMT

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

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

Well, performance-wise the difference is negligible. There is an extra lg(N/32) cost for the
current implementation, which amortizes to imperceptible (and literally zero for small sets).
The fact we don't use higher/lower/ceil/floor very commonly means I'm confident this extra
cost is better to incur for the simplicity of implementation. 

The reason I say "better" is exclusively because there is a more direct implementation for
the inequality lookups. If we don't have _another_ reason for indexing it seems better practice
to implement that directly, and leave out the indexing feature.

The indexability is actually surprisingly simple, and doesn't introduce significant complexity
IMO. I'm just a little wary of introducing features we don't use _directly_ (even if I have
an attachment to it), for the normal worries of code atrophy. I certainly won't argue against
its inclusion, though, as I agree it seems like it _should_ be more generally useful. I'm
just not yet aware of another place for it.

> 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)

Mime
View raw message