[
https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14514183#comment-14514183
]
Branimir Lambov commented on CASSANDRA-8915:
--------------------------------------------
[~benedict]: I invested some time exploring the linked list of colliding
iterators idea.
[Here|https://github.com/apache/cassandra/compare/trunk...blambov:mergeiterator-comparison]
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 iterators
- 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 discussion.
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: 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)
