[
https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14348732#comment-14348732
]
Benedict commented on CASSANDRA-8915:
-------------------------------------
It sounds like you're suggesting a full priority queue implementation with a
swapHead() (or similar) method that heapifies the new value (possibly
terminating immediately), but could you confirm? This seems preferable to me,
but it could be taken that this proposal is for a simple wrapper that just
extracts the head of the queue and wraps an existing implementation, which
would only help situations with mostly disjoint files (so any single file with
wide overlap would result in close to prior performance).
> 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)
