This is an automated email from the ASF dual-hosted git repository.
junegunn pushed a commit to branch branch-2.5
in repository https://gitbox.apache.org/repos/asf/hbase.git
The following commit(s) were added to refs/heads/branch-2.5 by this push:
new 901808ad38b HBASE-30226 Avoid same-row reverse FuzzyRowFilter hints
(#8360)
901808ad38b is described below
commit 901808ad38b5ef451b46c5a96a8f39d49feb83ed
Author: EungsopYoo <[email protected]>
AuthorDate: Fri Jun 19 11:46:32 2026 +0900
HBASE-30226 Avoid same-row reverse FuzzyRowFilter hints (#8360)
Signed-off-by: Junegunn Choi <[email protected]>
Signed-off-by: Dávid Paksy <[email protected]>
---
.../apache/hadoop/hbase/filter/FuzzyRowFilter.java | 34 ++++++-
.../hadoop/hbase/filter/TestFuzzyRowFilter.java | 80 +++++++++++++--
.../hbase/filter/TestFuzzyRowFilterEndToEnd.java | 107 ++++++++++++++++++++-
3 files changed, 207 insertions(+), 14 deletions(-)
diff --git
a/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
b/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
index 86b4f7de9d2..e32cbbc1dd1 100644
---
a/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
+++
b/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/FuzzyRowFilter.java
@@ -97,7 +97,7 @@ public class FuzzyRowFilter extends FilterBase implements
HintingFilter {
private int lastFoundIndex = -1;
/**
- * Row tracker (keeps all next rows after SEEK_NEXT_USING_HINT was returned)
+ * Row tracker for next row hints and reverse same-row hint detection.
*/
private final RowTracker tracker;
@@ -240,9 +240,14 @@ public class FuzzyRowFilter extends FilterBase implements
HintingFilter {
return ReturnCode.INCLUDE;
}
}
- // NOT FOUND -> seek next using hint
+ // NOT FOUND -> seek next using hint or skip the current row.
lastFoundIndex = -1;
filterRow = true;
+ // For reverse scans, a non-matching row can recreate itself as the next
hint. Since fuzzy
+ // matching is row-key based, skip the whole non-matching row instead of
seeking to it again.
+ if (isReversed() && tracker.updateTracker(c) &&
tracker.isNextRowSameAs(c)) {
+ return ReturnCode.NEXT_ROW;
+ }
return ReturnCode.SEEK_NEXT_USING_HINT;
}
@@ -263,6 +268,12 @@ public class FuzzyRowFilter extends FilterBase implements
HintingFilter {
return null;
}
byte[] nextRowKey = tracker.nextRow();
+ if (isReversed() && !tracker.lessThan(currentCell, nextRowKey)) {
+ // filterCell normally handles same-row reverse hints with NEXT_ROW. If
a non-progressing
+ // hint still reaches here, keep the current-row boundary to avoid
skipping matching rows
+ // under it, but return a non-seeking hint so StoreScanner advances
normally.
+ return PrivateCellUtil.createLastOnRow(currentCell);
+ }
return PrivateCellUtil.createFirstOnRow(nextRowKey, 0, (short)
nextRowKey.length);
}
@@ -310,7 +321,12 @@ public class FuzzyRowFilter extends FilterBase implements
HintingFilter {
while (!nextRows.isEmpty() && !lessThan(currentCell,
nextRows.peek().getFirst())) {
Pair<byte[], Pair<byte[], byte[]>> head = nextRows.poll();
Pair<byte[], byte[]> fuzzyData = head.getSecond();
- updateWith(currentCell, fuzzyData);
+ byte[] nextRowKeyCandidate = updateWith(currentCell, fuzzyData);
+ if (nextRowKeyCandidate != null && !lessThan(currentCell,
nextRowKeyCandidate)) {
+ // The candidate still does not make progress for this row. Keep
it in the queue so
+ // filterCell can skip the row or getNextCellHint can return a
non-seeking hint.
+ break;
+ }
}
}
return !nextRows.isEmpty();
@@ -322,13 +338,23 @@ public class FuzzyRowFilter extends FilterBase implements
HintingFilter {
return (!isReversed() && compareResult < 0) || (isReversed() &&
compareResult > 0);
}
- void updateWith(Cell currentCell, Pair<byte[], byte[]> fuzzyData) {
+ boolean isNextRowSameAs(Cell currentCell) {
+ if (nextRows.isEmpty()) {
+ return false;
+ }
+ byte[] candidateRowKey = nextRows.peek().getFirst();
+ return CellComparator.getInstance().compareRows(currentCell,
candidateRowKey, 0,
+ candidateRowKey.length) == 0;
+ }
+
+ byte[] updateWith(Cell currentCell, Pair<byte[], byte[]> fuzzyData) {
byte[] nextRowKeyCandidate =
getNextForFuzzyRule(isReversed(), currentCell.getRowArray(),
currentCell.getRowOffset(),
currentCell.getRowLength(), fuzzyData.getFirst(),
fuzzyData.getSecond());
if (nextRowKeyCandidate != null) {
nextRows.add(new Pair<>(nextRowKeyCandidate, fuzzyData));
}
+ return nextRowKeyCandidate;
}
}
diff --git
a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
index 2a6d7cb28ff..7501acd1e84 100644
---
a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
+++
b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilter.java
@@ -22,12 +22,15 @@ import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertThrows;
+import java.io.IOException;
import java.util.Arrays;
+import org.apache.hadoop.hbase.Cell;
import org.apache.hadoop.hbase.KeyValue;
import org.apache.hadoop.hbase.KeyValueUtil;
import org.apache.hadoop.hbase.testclassification.FilterTests;
import org.apache.hadoop.hbase.testclassification.SmallTests;
import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.util.Pair;
import org.junit.jupiter.api.Tag;
import org.junit.jupiter.api.Test;
import org.opentest4j.AssertionFailedError;
@@ -277,6 +280,12 @@ public class TestFuzzyRowFilter {
new byte[] { 1, 2, 1, 0, 1 }, // current
new byte[] { 1, 1, 3 }); // expected next
+ // Preserve HBASE-28634 boundary hints. Lowering 1115 to 1114 would skip
rows such as 111444.
+ assertNext(true, Bytes.toBytes("111433"), // fuzzy row
+ new byte[] { -1, -1, -1, -1, 0, 0 }, // mask
+ Bytes.toBytes("1115"), // current
+ Bytes.toBytes("1115")); // expected next
+
assertNext(true, new byte[] { 0, 1, 0, 2, 0 }, // fuzzy row
new byte[] { 0, -1, 0, -1, 0 }, // mask
new byte[] { 1, 2, 1, 3, 1 }, // current
@@ -292,11 +301,6 @@ public class TestFuzzyRowFilter {
new byte[] { 5, 1, 0, 2, 1 }, // current
new byte[] { 5, 1, 0, 2 }); // expected next
- assertNext(true, new byte[] { 0, 1, 0, 0 }, // fuzzy row
- new byte[] { 0, -1, 0, 0 }, // mask
- new byte[] { 5, 1, (byte) 255, 1 }, // current
- new byte[] { 5, 1, (byte) 255, 1 }); // expected next
-
assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
new byte[] { 0, -1, 0, -1 }, // mask
new byte[] { 5, 1, 0, 1 }, // current
@@ -332,6 +336,24 @@ public class TestFuzzyRowFilter {
new byte[] { 2, 1, 1, 1, 0 }, // row to check
new byte[] { 1, 2, (byte) 255, 4 }); // expected next
+ // No cell before the current one satisfies the fuzzy row -> null.
+ assertNull(FuzzyRowFilter.getNextForFuzzyRule(true, new byte[] { 1, 1, 1,
3, 0 },
+ new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
+ }
+
+ @Test
+ public void testGetNextForFuzzyRuleReverseCanReturnCurrentRow() {
+ // HBASE-28634 reverse adjustment can intentionally return the current row
as a boundary hint.
+ assertNext(true, new byte[] { 'a', 'a', 'a' }, // fuzzy row
+ new byte[] { -1, 0, -1 }, // mask
+ new byte[] { 'a', 'b', 'b' }, // current
+ new byte[] { 'a', 'b', 'b' }); // expected next
+
+ assertNext(true, new byte[] { 0, 1, 0, 0 }, // fuzzy row
+ new byte[] { 0, -1, 0, 0 }, // mask
+ new byte[] { 5, 1, (byte) 255, 1 }, // current
+ new byte[] { 5, 1, (byte) 255, 1 }); // expected next
+
assertNext(true, new byte[] { 1, 0, 1 }, // fuzzy row
new byte[] { -1, 0, -1 }, // mask
new byte[] { 1, (byte) 128, 2 }, // row to check
@@ -356,10 +378,6 @@ public class TestFuzzyRowFilter {
new byte[] { 0, 0, 0, 0 }, // mask
new byte[] { 1, 1, 2, 3 }, // row to check
new byte[] { 1, 1, 2, 3 }); // expected next
-
- // no before cell than current which satisfies the fuzzy row -> null
- assertNull(FuzzyRowFilter.getNextForFuzzyRule(true, new byte[] { 1, 1, 1,
3, 0 },
- new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
}
private static void assertNext(boolean reverse, byte[] fuzzyRow, byte[]
mask, byte[] current,
@@ -369,4 +387,48 @@ public class TestFuzzyRowFilter {
kv.getRowOffset(), kv.getRowLength(), fuzzyRow, mask);
assertEquals(Bytes.toStringBinary(expected),
Bytes.toStringBinary(nextForFuzzyRule));
}
+
+ @Test
+ public void testReverseFilterCellSkipsSameRowHint() {
+ // The first non-matching row can seek to abb, but abb would recreate abb
as its reverse hint.
+ // The scanner should skip that non-matching row instead of seeking to the
same row again.
+ FuzzyRowFilter filter = newReverseFuzzyRowFilter();
+
+ KeyValue abc = KeyValueUtil.createFirstOnRow(Bytes.toBytes("abc"));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT,
filter.filterCell(abc));
+ Cell hint = filter.getNextCellHint(abc);
+ assertRow("abb", hint);
+
+ KeyValue abb = KeyValueUtil.createFirstOnRow(Bytes.toBytes("abb"));
+ // filterCell handles the same-row hint by skipping the current
non-matching row.
+ assertEquals(Filter.ReturnCode.NEXT_ROW, filter.filterCell(abb));
+ }
+
+ @Test
+ public void testReverseFilterListSkipsSameRowFuzzyHint() throws IOException {
+ for (FilterList.Operator operator :
Arrays.asList(FilterList.Operator.MUST_PASS_ALL,
+ FilterList.Operator.MUST_PASS_ONE)) {
+ FilterList filterList =
+ new FilterList(operator, newReverseFuzzyRowFilter(),
newReverseFuzzyRowFilter());
+
+ KeyValue abc = KeyValueUtil.createFirstOnRow(Bytes.toBytes("abc"));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT,
filterList.filterCell(abc));
+ assertRow("abb", filterList.getNextCellHint(abc));
+
+ KeyValue abb = KeyValueUtil.createFirstOnRow(Bytes.toBytes("abb"));
+ assertEquals(Filter.ReturnCode.NEXT_ROW, filterList.filterCell(abb));
+ }
+ }
+
+ private static FuzzyRowFilter newReverseFuzzyRowFilter() {
+ FuzzyRowFilter filter =
+ new FuzzyRowFilter(Arrays.asList(new Pair<>(Bytes.toBytes("aaa"), new
byte[] { 0, 1, 0 })));
+ filter.setReversed(true);
+ return filter;
+ }
+
+ private static void assertRow(String expected, Cell cell) {
+ assertEquals(expected,
+ Bytes.toString(cell.getRowArray(), cell.getRowOffset(),
cell.getRowLength()));
+ }
}
diff --git
a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilterEndToEnd.java
b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilterEndToEnd.java
index d2547b3f52f..2e56df9424f 100644
---
a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilterEndToEnd.java
+++
b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFuzzyRowFilterEndToEnd.java
@@ -18,6 +18,7 @@
package org.apache.hadoop.hbase.filter;
import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
import java.io.IOException;
@@ -345,6 +346,103 @@ public class TestFuzzyRowFilterEndToEnd {
TEST_UTIL.deleteTable(TableName.valueOf(name));
}
+ @Test
+ public void testReverseScanMovesPastSameRowFuzzyHint(TestInfo testInfo)
throws IOException {
+ final String cf = "f";
+ final String cq = "q";
+
+ String name =
testInfo.getTestMethod().orElseThrow(AssertionError::new).getName();
+ try (Table ht = TEST_UTIL.createTable(TableName.valueOf(name),
Bytes.toBytes(cf))) {
+ List<Put> puts = Lists.newArrayList();
+ puts.add(new Put(Bytes.toBytes("aaa")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes(cq),
+ Bytes.toBytes("v")));
+ puts.add(new Put(Bytes.toBytes("aba")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes(cq),
+ Bytes.toBytes("v")));
+ puts.add(new Put(Bytes.toBytes("abaa")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes(cq),
+ Bytes.toBytes("v")));
+ puts.add(new Put(Bytes.toBytes("abb")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes(cq),
+ Bytes.toBytes("v")));
+ puts.add(new Put(Bytes.toBytes("abc")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes(cq),
+ Bytes.toBytes("v")));
+ ht.put(puts);
+
+ TEST_UTIL.flush();
+
+ List<Pair<byte[], byte[]>> fuzzyList = new LinkedList<>();
+ fuzzyList.add(new Pair<>(Bytes.toBytes("aaa"), new byte[] { 0, 1, 0 }));
+
+ Scan scan = new Scan();
+ scan.setReversed(true);
+ scan.setFilter(new FuzzyRowFilter(fuzzyList));
+
+ try (ResultScanner scanner = ht.getScanner(scan)) {
+ Result result = scanner.next();
+ assertNotNull(result);
+ assertEquals("abaa", Bytes.toString(result.getRow()));
+ result = scanner.next();
+ assertNotNull(result);
+ assertEquals("aba", Bytes.toString(result.getRow()));
+ result = scanner.next();
+ assertNotNull(result);
+ assertEquals("aaa", Bytes.toString(result.getRow()));
+ assertNull(scanner.next());
+ }
+ }
+
+ TEST_UTIL.deleteTable(TableName.valueOf(name));
+ }
+
+ @Test
+ public void
testReverseScanMovesPastSameRowFuzzyHintAcrossMultipleCells(TestInfo testInfo)
+ throws IOException {
+ final String cf = "f";
+
+ String name =
testInfo.getTestMethod().orElseThrow(AssertionError::new).getName();
+ try (Table ht = TEST_UTIL.createTable(TableName.valueOf(name),
Bytes.toBytes(cf))) {
+ List<Put> puts = Lists.newArrayList();
+ puts.add(new Put(Bytes.toBytes("aaa")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes("q1"),
+ Bytes.toBytes("v")));
+ puts.add(new Put(Bytes.toBytes("aba")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes("q1"),
+ Bytes.toBytes("v")));
+ puts.add(new Put(Bytes.toBytes("abaa")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes("q1"),
+ Bytes.toBytes("v")));
+ // The same-row reverse hint can be recreated for each cell on this
non-matching row.
+ // Before the fix, the first cell could loop inside RowTracker and never
return to
+ // StoreScanner. After the fix, NEXT_ROW skips the whole row without
skipping abaa.
+ puts.add(new Put(Bytes.toBytes("abb"))
+ .addColumn(Bytes.toBytes(cf), Bytes.toBytes("q1"), Bytes.toBytes("v1"))
+ .addColumn(Bytes.toBytes(cf), Bytes.toBytes("q2"), Bytes.toBytes("v2"))
+ .addColumn(Bytes.toBytes(cf), Bytes.toBytes("q3"),
Bytes.toBytes("v3")));
+ puts.add(new Put(Bytes.toBytes("abc")).addColumn(Bytes.toBytes(cf),
Bytes.toBytes("q1"),
+ Bytes.toBytes("v")));
+ ht.put(puts);
+
+ TEST_UTIL.flush();
+
+ List<Pair<byte[], byte[]>> fuzzyList = new LinkedList<>();
+ fuzzyList.add(new Pair<>(Bytes.toBytes("aaa"), new byte[] { 0, 1, 0 }));
+
+ Scan scan = new Scan();
+ scan.setReversed(true);
+ scan.setFilter(new FuzzyRowFilter(fuzzyList));
+
+ try (ResultScanner scanner = ht.getScanner(scan)) {
+ Result result = scanner.next();
+ assertNotNull(result);
+ assertEquals("abaa", Bytes.toString(result.getRow()));
+ result = scanner.next();
+ assertNotNull(result);
+ assertEquals("aba", Bytes.toString(result.getRow()));
+ result = scanner.next();
+ assertNotNull(result);
+ assertEquals("aaa", Bytes.toString(result.getRow()));
+ assertNull(scanner.next());
+ }
+ }
+
+ TEST_UTIL.deleteTable(TableName.valueOf(name));
+ }
+
@Test
public void testHBASE28634(TestInfo testInfo) throws IOException {
final String CF = "f";
@@ -365,8 +463,11 @@ public class TestFuzzyRowFilterEndToEnd {
Bytes.toBytes("a4")));
puts.add(new Put(Bytes.toBytes("111446")).addColumn(Bytes.toBytes(CF),
Bytes.toBytes(CQ),
Bytes.toBytes("a5")));
- puts.add(new Put(Bytes.toBytes("111777")).addColumn(Bytes.toBytes(CF),
Bytes.toBytes(CQ),
+ // Keep a real boundary row at the reverse hint target so this test also
guards HBASE-28634.
+ puts.add(new Put(Bytes.toBytes("1115")).addColumn(Bytes.toBytes(CF),
Bytes.toBytes(CQ),
Bytes.toBytes("a6")));
+ puts.add(new Put(Bytes.toBytes("111777")).addColumn(Bytes.toBytes(CF),
Bytes.toBytes(CQ),
+ Bytes.toBytes("a7")));
puts.add(new Put(Bytes.toBytes("111777")).addColumn(Bytes.toBytes(CF),
Bytes.toBytes(CQ),
Bytes.toBytes("a")));
ht.put(puts);
@@ -391,6 +492,8 @@ public class TestFuzzyRowFilterEndToEnd {
}
assertEquals(2, actualRowsList.size());
+ assertEquals("111444", Bytes.toString(actualRowsList.get(0)));
+ assertEquals("111446", Bytes.toString(actualRowsList.get(1)));
// Reverse scan
scan = new Scan();
@@ -405,6 +508,8 @@ public class TestFuzzyRowFilterEndToEnd {
}
assertEquals(2, actualRowsList.size());
+ assertEquals("111446", Bytes.toString(actualRowsList.get(0)));
+ assertEquals("111444", Bytes.toString(actualRowsList.get(1)));
TEST_UTIL.deleteTable(TableName.valueOf(name));
}
