cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-8915) Improve MergeIterator performance
Date Thu, 16 Jul 2015 11:46:04 GMT


Benedict commented on CASSANDRA-8915:

Thanks. [Committed|].

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:
>             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

View raw message