cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Branimir Lambov (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-8915) Improve MergeIterator performance
Date Wed, 03 Jun 2015 15:12:38 GMT

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

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

Updated above with some of your suggestions.

bq. Perhaps clarify, that σ(P) => σ(R), so already correct.

This is not entirely true, {{(σ(P) & P = R) => σ(R)}}. I would find it confusing
to put that info there, though, I prefer to split actions from proof.

bq. It would help to state {{P ≙ ep-heap(M,N)}} ... and more.

I hesitate to add this; I think the way it is now is enough to convince people that it is
sound even if it is not very precise (esp wrt bottom).

> 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
>              Labels: compaction, performance
>             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)

Mime
View raw message