[
https://issues.apache.org/jira/browse/HBASE-14269?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14706896#comment-14706896
]
Ted Yu commented on HBASE-14269:
--------------------------------
If more time is needed to arrive at a benchmark that everybody agrees, we
should revert HBASE-13761.
Otherwise we can go with the patch in this issue.
> FuzzyRowFilter omits certain rows when multiple fuzzy key exist
> ---------------------------------------------------------------
>
> Key: HBASE-14269
> URL: https://issues.apache.org/jira/browse/HBASE-14269
> Project: HBase
> Issue Type: Bug
> Components: Filters
> Reporter: hongbin ma
> Assignee: hongbin ma
> Attachments: HBASE-14269-v1.patch, HBASE-14269-v2.patch,
> HBASE-14269.patch
>
>
> https://issues.apache.org/jira/browse/HBASE-13761 introduced a RowTracker in
> FuzzyRowFilter to avoid performing getNextForFuzzyRule() for each fuzzy key
> on each getNextCellHint() by maintaining a list of possible row matches for
> each fuzzy key. The implementation assumes that the prepared rows will be
> matched one by one, so it removes the first row in the list as soon as it is
> used. However, this approach may lead to omitting rows in some cases:
> Consider a case where we have two fuzzy keys:
> 1?1
> 2?2
> and the data is like:
> 000
> 111
> 112
> 121
> 122
> 211
> 212
> when the first row 000 fails to match, RowTracker will update possible row
> matches with cell 000 and fuzzy keys 1?1,2?2. This will populate RowTracker
> with 101 and 202. Then 101 is popped out of RowTracker, hint the scanner to
> go to row 101. The scanner will get 111 and find it is a match, and continued
> to find that 112 is not a match, getNextCellHint will be called again. Then
> comes the bug: Row 101 has been removed out of RowTracker, so RowTracker will
> jump to 202. As you see row 121 will be omitted, but it is actually a match
> for fuzzy key 1?1.
> I will illustrate the bug by adding a new test case in
> TestFuzzyRowFilterEndToEnd. Also I will provide the bug fix in my patch. The
> idea of the new solution is to maintain a priority queue for all the possible
> match rows for each fuzzy key, and whenever getNextCellHint is called, the
> elements in the queue that are smaller than the parameter currentCell will be
> updated(and re-insert into the queue). The head of queue will always be the
> "Next cell hint".
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
