[jira] [Commented] (CASSANDRA-10301) Search for items past end of descending BTreeSearchIterator can fail

["Branimir Lambov (JIRA)" <ji...@apache.org>]

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