Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@cassandra.apache.org
Date: Tue, 5 May 2015 14:19:00 +0000 (UTC)
From: "Branimir Lambov (JIRA)" <jira@apache.org>
To: commits@cassandra.apache.org
Message-ID: <JIRA.12779758.1425550560000.2818.1430835540007@Atlassian.JIRA>
In-Reply-To: <JIRA.12779758.1425550560000@Atlassian.JIRA>
References: <JIRA.12779758.1425550560000@Atlassian.JIRA>
 <JIRA.12779758.1425550560611@arcas>
Subject: [jira] [Commented] (CASSANDRA-8915) Improve MergeIterator
 performance
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Branimir Lambov commented on CASSANDRA-8915:
--------------------------------------------

bq. My optimisation... 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.

I think this is better served by other heap types (e.g. Fibonacci), which I was planning to explore at a later time. Do you prefer to do this now?

You have convinced me, though, that avoiding that second comparison for {{consume}} is something that must be done, so I added a [{{FlagEqual}} variation|https://github.com/apache/cassandra/blob/545aa9c66e568b853673ea40da05f13bd3c86a73/src/java/org/apache/cassandra/utils/MergeIteratorFlagEqual.java] of the non-collapsing approach that flags equality when it finds it. The flag is then sufficient for {{consume}} and skipping over equal elements in the heap, providing equal comparison complexity with {{AllEqual}} but without the need to remove/readd iterators. The benchmarks show it to be on par with {{AllEqual}} in the random cases, and better than {{NoEqual}} in the limited overlap scenarios.

Also, I don't see any links in your comment. Could I also look at your experiments?

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