cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (CASSANDRA-9988) Introduce leaf-only iterator
Date Thu, 27 Jul 2017 10:10:00 GMT

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

Benedict edited comment on CASSANDRA-9988 at 7/27/17 10:09 AM:
---------------------------------------------------------------

Well, it's been a while since I looked at the internals, but iirc there is an extremely common
scenario in which we enumerate most of the contents of such an iterator via search, and that
is in the case of selecting columns from a row.

Since we already have binary search's best case and exponential search's worst case in the
benchmarks, and given we can expect the inverse scenario to be common, why not supplement
with that so we can see the two extremes?

Also, FTR: a properly implemented exponential search should only incur 1 comparison for each
search in its best case, as the result of the most recent boundary comparison can be saved
- if it is zero then no binary search is needed over the range.


was (Author: benedict):
Well, it's been a while since I looked at the internals, but iirc there is an extremely common
scenario in which we enumerate most of the contents of such an iterator via search, and that
is in the case of selecting columns from a row.

Since we already have binary search's best case and exponential search's worst case in the
benchmarks, and given we can expect the inverse scenario to be common, why not supplement
with that so we can see the two extremes?

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