[
https://issues.apache.org/jira/browse/HBASE-14269?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14706991#comment-14706991
]
Vladimir Rodionov commented on HBASE-14269:
-------------------------------------------
Yes, the logic inside optimization for getNextHint is broken when fuzzy row has
more than one fixed area, when fuzzy row has one fixed area (the most common
case, I suppose) - it works and has significant performance gain, the more
fuzzy rows - the more gain. One can run test with fuzzy rows such this: ?X?, or
?X. I would not revert HBASE-13761 completely, unsafe implementation for
satisfies is correct and 8x times faster than the previous one. It is a shame
that scanner's overhead makes this improvement negligible though. [~honma],
please revert genNextCellHint, but leave satisfies. I will work on a new patch
for HBASE-13761 when I will have time. The most common case of usage is still
correct - fuzzy row with one fixed area.
> 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)
