cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jay Zhuang (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9988) Introduce leaf-only iterator
Date Wed, 26 Jul 2017 21:46:00 GMT

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

Jay Zhuang commented on CASSANDRA-9988:
---------------------------------------

They're good feedbacks. I did the tests for expSearch:
!9988-test-result3.png|test!
I think the exponentialSearch didn't out perform the binaraySearch is because:
# data size is too small. In this case, it only searches inside of one leaf, the maximum data
size is 32 (default node size).
In theroy, the performance of exponential search is {{[O(log( i ) + log( i ))|https://en.wikipedia.org/wiki/Exponential_search#Performance]}}
({{i}} is where the target is), vs. binary search is {{O(log( n ))}}.
Because exponentialSearch has 2 stages, it could do more compares when the {{n}} is small.
# Maybe Java API {{Arrays.binarySearch()}} is already doing some optimizations.

So for this JIRA, I don't think it worth doing exponentialSearch.

> Introduce leaf-only iterator
> ----------------------------
>
>                 Key: CASSANDRA-9988
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9988
>             Project: Cassandra
>          Issue Type: Sub-task
>            Reporter: Benedict
>            Assignee: Jay Zhuang
>            Priority: Minor
>              Labels: patch
>             Fix For: 4.0
>
>         Attachments: 9988-data.png, 9988-result2.png, 9988-result3.png, 9988-result.png,
9988-test-result3.png, 9988-trunk-new.txt, 9988-trunk-new-update.txt, 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.4.14#64029)

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org


Mime
View raw message