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 Wed, 26 Jul 2017 22:07:01 GMT

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

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

So, I took a quick peek at your actual test cases, and it seems you're only ever seeking into
an iterator the once with a uniform key across its domain, then discarding it.  In this scenario,
yes, you would expect exponential search to be more costly.

However, these are iterators, and the expectation is that there will be multiple seeks during
the iterator's lifetime.  I had assumed that your searchFound and searchNotFound enumerated
(searched for) a sequence of found / not found keys.  There should probably be such variants.

All that said, I feel like this ticket has dragged on long enough and we're probably well
past diminishing returns for the change itself.  But these benchmarks are likely to persist
a lot better than this discussion, so it is probably worthwhile getting them right.  It's
also the case that we already use exponential search for the branch iterator (though this
was decided back on 2.2 storage format, so our N was much larger), and we should probably
be consistent and settle it once and for all.

> 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