cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9988) Introduce leaf-only iterator
Date Tue, 26 Jan 2016 14:02:39 GMT

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

Mime
View raw message