[jira] [Commented] (CASSANDRA-8915) Improve MergeIterator performance

["Benedict (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/CASSANDRA-8915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14523745#comment-14523745 ] 

Benedict commented on CASSANDRA-8915:
-------------------------------------

First off, I agree that the MergeIteratorAllEqual is unfortunately complex, though I haven't yet attempted to fully reason about its behaviour. Are we certain there's no way to reduce its complexity? If you don't think it can be improved complexity-wise from its current position, I'll find some time to chew on it myself as well, so we have at least had two distinct attempts to reduce that burden.

However from a performance point of view, I have two major quibbles:

* There is a simple optimisation of AllEqual, which I have introduced, and it is now universally faster (or as fast)
* I don't _think_ that's the best characterisation of LCS (please feel free to prove me wrong, though, as I may have a poor mental model of LCS)

My optimisation as stands is actually pretty rubbish; it could be done much better. What I do is construct a new heap from the equal candidates, and then push down the top element and bubble up the remainder. All this does really is compress the equal items, push down the one most likely to stay at the head, and expand the remainder from the smallest item upwards so minimizing the number of swaps. We could instead perform a merge, but even with this imperfect implementation the result is typically half as many comparisons as NoEqual, and never more.

As to LCS: to my knowledge, it only ever compacts two levels together, but within each level there is no compaction/comparison, they are simply concatenated together. Between the levels there's no guarantee of overlap, and the values will typically be randomly distributed since we default to hashed partitioning. Given each level is 10 times larger than the previous, we can also expect that the number of _runs_ of equality are very low. I've introduced simulation of varying numbers of levels being compacted together, along with varying numbers of L0 sstables in the mix, and with varying levels of overlap between the levels (100%, 50%, 0%; here I mean percentage of values in a level which definitely occur in a lower level). These all come out as either the same or faster under both versions of AllEqual.

Of course the statement likely stands for a variety of workloads with many CQL row overwrites, so catering for the case of many runs of overlaps is still an important one.

bq.  but please do not hesitate to disagree or bring other concerns/questions/scenarios to the discussion.

ditto :)

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