Branimir Lambov created CASSANDRA-8915:
------------------------------------------
Summary: 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)
