cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Branimir Lambov (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-8915) Improve MergeIterator performance
Date Mon, 27 Apr 2015 14:19:38 GMT


Branimir Lambov commented on CASSANDRA-8915:

[~benedict]: I invested some time exploring the linked list of colliding iterators idea. [Here|]
you can find a branch that includes and can be used to compare four versions of the iterator:
- {{MergeIteratorNoEqual}}: my initial implementation, without collapsing equal iterators
- {{MergeIteratorAllEqual}}: fully implements collapse of equal iterators
- {{MergeIterator.ManyToOne}}: mixture of the two above, only collapsing when it is easy
- {{MergeIteratorComparisonTest.MergeIteratorPQ}}: the old implementation

What I can tell from the performance tests:
- AllEqual is noticeably faster for randomly spaced inputs, as well as for completely non-colliding
- NoEqual, on the other hand, is better when the overlap is organized in sections (as in LeveledCompaction)
- the mixture is always slower than either

The explanation is that AllEqual can avoid the equality comparisons in {{consume}} (halving
the number of comparisons in the no-overlap case), but if there are collisions it must pay
the price when advancing multiple equal iterators, having to place all but one at the end
of the heap and possibly having to pull them up all the way to the top. The latter is not
a disadvantage for random data, but IMHO Cassandra's use cases do produce or impose structure
where it would be. As the AllEqual implementation is also quite a bit more complicated and
harder to follow, the code I would choose to continue with is the original, NoEqual version,
but please do not hesitate to disagree or bring other concerns/questions/scenarios to the

Other heap structures may improve this further, perhaps this can be revisited when there is
need to go further and/or we have more time on our hands?

[~Stefania]: Good stuff! It is orthogonal to this improvement-- it will work just as well
or even better here, in practically the same way that you have implemented it. The bound-to-actual
transition will only sink it down from the top, which is not going to be wasting much, practically
nothing if the bound is good enough. We don't want to open iterators before they have reached
the top as opening is incomparably slower than any waste the mergeIterator can have.

> Improve MergeIterator performance
> ---------------------------------
>                 Key: CASSANDRA-8915
>                 URL:
>             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

View raw message