[
https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14358560#comment-14358560
]
Branimir Lambov commented on CASSANDRA-8915:
--------------------------------------------
Patch is available
[here|https://github.com/apache/cassandra/compare/trunk...blambov:8915-mergeiterator].
The code turned out to be somewhat more complicated than I expected because of
the need to support lazy advance of the underlying iterators. The new iterator
is between several times and 10-20% faster depending on the overlap of the
inputs and the complexity of comparisons. I wasn't able to demonstrate the
effect in cstar_perf (see
[this|http://cstar.datastax.com/graph?stats=fb747232-c819-11e4-91b4-42010af0688f&metric=op_rate&operation=1_write]
but also
[this|http://cstar.datastax.com/graph?stats=ad2dbdb6-c843-11e4-a8b4-42010af0688f&metric=op_rate&operation=1_write]).
Any suggestions on how to test compaction performance?
At the moment the patch fails {{BlacklistingCompactionsTest}} because of
CASSANDRA-8960.
> Improve MergeIterator performance
> ---------------------------------
>
> Key: CASSANDRA-8915
> URL: https://issues.apache.org/jira/browse/CASSANDRA-8915
> Project: Cassandra
> Issue Type: Improvement
> Reporter: Branimir Lambov
> Assignee: Branimir Lambov
> Priority: Minor
>
> The implementation of {{MergeIterator}} uses a priority queue and applies a
> pair of {{poll}}+{{add}} operations for every item in the resulting sequence.
> This is quite inefficient as {{poll}} necessarily applies at least {{log N}}
> comparisons (up to {{2log N}}), and {{add}} often requires another {{log N}},
> for example in the case where the inputs largely don't overlap (where {{N}}
> is the number of iterators being merged).
> This can easily be replaced with a simple custom structure that can perform
> replacement of the top of the queue in a single step, which will very often
> complete after a couple of comparisons and in the worst case scenarios will
> match the complexity of the current implementation.
> This should significantly improve merge performance for iterators with
> limited overlap (e.g. levelled compaction).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
