[jira] [Updated] (CASSANDRA-8915) Improve MergeIterator performance
[ https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Wei Deng updated CASSANDRA-8915: Labels: compaction lcs performance (was: compaction 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 > Labels: compaction, lcs, performance > Fix For: 3.0 alpha 1 > > 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)
[jira] [Updated] (CASSANDRA-8915) Improve MergeIterator performance
[ https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Aleksey Yeschenko updated CASSANDRA-8915: - Fix Version/s: (was: 3.x) 3.0 beta 1 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.0 beta 1 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)
[jira] [Updated] (CASSANDRA-8915) Improve MergeIterator performance
[ https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] T Jake Luciani updated CASSANDRA-8915: -- Fix Version/s: 3.x 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 Fix For: 3.x 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)
[jira] [Updated] (CASSANDRA-8915) Improve MergeIterator performance
[ https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Benedict updated CASSANDRA-8915: Reviewer: Benedict 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)