[ https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14629604#comment-14629604 ]
Benedict commented on CASSANDRA-8915: ------------------------------------- Thanks. [Committed|https://github.com/apache/cassandra/commit/c29001b94df769fe428f414c042daffbb6dd209d]. For future reference, our commit form usually ends with a line like: "patch by branimir; reviewed by benedict for CASSANDRA-8915" It's not a perfect git history, but better to do our best to stick to it when we can (it also helps later analysis of commit/review). I think we should endeavour to create more descriptive commits alongside, though, like you have done here. > 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 > Labels: compaction, performance > Fix For: 3.x > > Time Spent: 0.2h > Remaining Estimate: 0h > > 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)