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 Mon, 07 Aug 2017 20:31:01 GMT

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

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

Hi [~benedict] thanks for the quick response.

The graph is the search performance (throughput) for searching target on the different positions.
The X axis is the position, the Y axis is the throughput, the bigger is the better. For multi-seeks,
we can assume the current position is 0, so if the next search value is the next adjacent
one (position 1), expSearch is 3 times better than binSearch, but binSearchOptimized could
actually do slightly better than expSearch in that case.

{quote}
if we want just a random 8 items in a 32 item iterator, we should expect exp. search to win
on average
{quote}
Yes, I agree. expSearch should out perform binSearch if we choose random 8 items out of 32,
as these 8 items should be close to each other.

{quote}
I did indicate my changes assumed your implementation was valid (I did not attempt to verify
it, and the original looks to be the source of the bug).
{quote}
The original implementation is valid. I think that's another example shows the code is not
that easy to understand.
If you follows the original implementation, it should be: {{return Arrays.binarySearch(keys,
lb, Math.min(ub + 1, probe_ub {color:red}+ 1{color}), key, comparator);}} baiscally it's just
one-off issue.

{quote}
I will, separately, note that I suspect we're both well past interest in this discussion.
So if you'd rather just go with binary search, feel free.
{quote}
Yes, I agree, and I'm really appreciated your reviews and comments. Let's create another JIRA
to look into the adoption of expSearch, not only for this case, it may improve performance
for other places too. and it should be in util/

> 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-3tests.png, 9988-data.png, 9988-result2.png, 9988-result3.png,
9988-result.png, 9988-test-result3.png, 9988-test-result-expsearch.xlsx, 9988-test-result-raw.png,
9988-test-result.xlsx, 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