cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-9471) Columns should be backed by a BTree, not an array
Date Thu, 30 Jul 2015 21:30:04 GMT


Benedict commented on CASSANDRA-9471:

[~aweisberg] said:
It would be nice to see a microbenchmark and benchmark demonstrating that the use of BTree
is a win. I am wondering how many additional instructions and branches are hidden inside BTree
that you pay for in the common case of small Columns set. A BTree is more instructions for
more cache locality, but in the common case will there be enough columns to benefit?

If we want to go down that avenue, we should IMO simply look into specialising the btree iterator
for the situation where we have just one leaf, and this is something I've considered. That's
pretty much the only likely win. We don't really have time to do the kind of microbenchmarking
you're talking about though, and it is of limited use anyway, since one of the main benefits
_performancewise_ (in the common case) is improved icache\* occupancy, which cannot be accounted
for in a microbenchmark. In the uncommon case this also gives us better lower bounds on behaviour,
and access to a more powerfully expressive toolkit. For instance, it permits us to trivially
deliver a more efficient multi-way merge (which we do very often), and that can be improved
further still with less trivial enhancements.

Mostly, though, this patch simply guarantees us a good lower bound on performance, with improved
code clarity. Right now I would very much expect performance in the common case to be a wash,
especially on any of our existing workloads.

> Columns should be backed by a BTree, not an array
> -------------------------------------------------
>                 Key: CASSANDRA-9471
>                 URL:
>             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

View raw message