[ https://issues.apache.org/jira/browse/HBASE-14269?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
hongbin ma updated HBASE-14269: ------------------------------- Attachment: HBASE-14269-v1.patch Update patch with Ted Yu's comments > 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.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)