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