[
https://issues.apache.org/jira/browse/CASSANDRA-10301?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14743383#comment-14743383
]
Branimir Lambov commented on CASSANDRA-10301:
---------------------------------------------
It was not very easy to understand why this is a problem. I think the attempt
to achieve {{binarySearch}} semantics misled us both. That entails less-than
relationship, which in turn makes the {{-1 - index}} return sensible. In the
reverse case we don't have that.
I'm also confused by the use of 'proceed' as a verb meaning follow. I don't
think that's a common meaning of the term, and people can easily interpret it
as a misspelling of 'precede', which isn't what we want. Did you mean 'succeed'?
In the comment to {{seekTo}} I'd turn the reference to {{binarySearch}}
semantics to state more that this does _not_ follow it, and be even more
explicit and state that on inexact match it returns {{-2 - index}}, where
{{index}} is such that
* {{tree\[index - 1\] < key < tree\[index\]}} in the forward case
* {{tree\[index\] < key < tree\[index + 1\]}} in the reverse case
which would show why {{-1 = -2 - (-1)}} is necessary.
I'm not very happy with this solution as it's error-prone and confusing. Have
you considered {{seekTo}} returning just whether it matched or not, and
exposing the current index separately?
> Search for items past end of descending BTreeSearchIterator can fail
> --------------------------------------------------------------------
>
> Key: CASSANDRA-10301
> URL: https://issues.apache.org/jira/browse/CASSANDRA-10301
> Project: Cassandra
> Issue Type: Bug
> Components: Core
> Reporter: Benedict
> Assignee: Benedict
> Priority: Blocker
> Fix For: 3.0.0 rc1
>
>
> A very simple problem, but obvious and with simple fix once it is made
> apparent.
> The internal {{seekTo}} method uses {{binarySearch}} semantics for its return
> value, however when searching backwards {{-1}} is a real value that should be
> returned to the client, as it indicates "past the end" - so basing inexact
> matches from -1 leads to a conflicting meaning, and so it gets
> misinterpreted. Rebasing inexact results to -2 fixes the problem.
> This was not caught because the randomized testing apparently did not test
> for values outside the bounds of the btree. This has been fixed as well, and
> the tests did easily exhibit the problem without the fix.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
