Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@cassandra.apache.org
Date: Tue, 26 Jan 2016 14:02:39 +0000 (UTC)
From: "Benedict (JIRA)" <jira@apache.org>
To: commits@cassandra.apache.org
Message-ID: <JIRA.12851642.1438769472000.211587.1453816959843@Atlassian.JIRA>
In-Reply-To: <JIRA.12851642.1438769472000@Atlassian.JIRA>
References: <JIRA.12851642.1438769472000@Atlassian.JIRA>
 <JIRA.12851642.1438769472247@arcas>
Subject: [jira] [Commented] (CASSANDRA-9988) Introduce leaf-only iterator
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Benedict commented on CASSANDRA-9988:
-------------------------------------

Hi Piotr,

Thanks for your patch.  A few comments:

# It would be great to have just one Leaf iterator, so that we can benefit from efficient method despatch, as there will be only two search iterator implementations
# We could probably get uniformly better behaviour by implementing [exponential search|https://en.wikipedia.org/wiki/Exponential_search] for the leaf iterator; this would bring our total number of comparisons down from {{n lg n}} to {{n}} when searching an approximately equal set of items, without harming our best case complexity.
# It would be preferable to get numbers using JMH, and comparing a codebase that only contains the full search iterator, versus one that contains both (and performs searches that cross the boundaries, so it's unknown which will be returned), as method despatch will potentially be harmed


> Introduce leaf-only iterator
> ----------------------------
>
>                 Key: CASSANDRA-9988
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9988
>             Project: Cassandra
>          Issue Type: Sub-task
>            Reporter: Benedict
>            Priority: Minor
>              Labels: patch
>             Fix For: 3.x
>
>         Attachments: trunk-9988.txt
>
>
> In many cases we have small btrees, small enough to fit in a single leaf page. In this case it _may_ be more efficient to specialise our iterator.


--
This message was sent by Atlassian JIRA
(v6.3.4#6332)