You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by st...@apache.org on 2024/11/06 07:34:59 UTC
(hbase) branch master updated: HBASE-28621 PrefixFilter should use SEEK_NEXT_USING_HINT (#6361)
This is an automated email from the ASF dual-hosted git repository.
stoty pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/hbase.git
The following commit(s) were added to refs/heads/master by this push:
new 16870182ca1 HBASE-28621 PrefixFilter should use SEEK_NEXT_USING_HINT (#6361)
16870182ca1 is described below
commit 16870182ca1b0307a020448afa0000c24adeafda
Author: Dávid Paksy <pa...@gmail.com>
AuthorDate: Wed Nov 6 08:34:52 2024 +0100
HBASE-28621 PrefixFilter should use SEEK_NEXT_USING_HINT (#6361)
Co-authored-by: Dávid Paksy <pa...@cloudera.com>
Signed-off-by: Istvan Toth <st...@apache.org>
---
.../apache/hadoop/hbase/filter/PrefixFilter.java | 70 +++++++-
.../apache/hadoop/hbase/filter/TestFilterList.java | 4 +-
.../hadoop/hbase/filter/TestPrefixFilter.java | 184 ++++++++++++++++++++-
3 files changed, 243 insertions(+), 15 deletions(-)
diff --git a/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/PrefixFilter.java b/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/PrefixFilter.java
index c6d76a2f0d1..5ef48c62fc6 100644
--- a/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/PrefixFilter.java
+++ b/hbase-client/src/main/java/org/apache/hadoop/hbase/filter/PrefixFilter.java
@@ -18,8 +18,10 @@
package org.apache.hadoop.hbase.filter;
import java.util.ArrayList;
+import java.util.Arrays;
import org.apache.hadoop.hbase.ByteBufferExtendedCell;
import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.PrivateCellUtil;
import org.apache.hadoop.hbase.exceptions.DeserializationException;
import org.apache.hadoop.hbase.util.ByteBufferUtils;
import org.apache.hadoop.hbase.util.Bytes;
@@ -35,13 +37,31 @@ import org.apache.hadoop.hbase.shaded.protobuf.generated.FilterProtos;
* Pass results that have same row prefix.
*/
@InterfaceAudience.Public
-public class PrefixFilter extends FilterBase {
+public class PrefixFilter extends FilterBase implements HintingFilter {
protected byte[] prefix = null;
protected boolean passedPrefix = false;
protected boolean filterRow = true;
+ protected boolean provideHint = false;
+ protected Cell reversedNextCellHint;
+ protected Cell forwardNextCellHint;
public PrefixFilter(final byte[] prefix) {
this.prefix = prefix;
+ // Pre-compute hints at creation to avoid re-computing them several times in the corner
+ // case where there are a lot of cells between the hint and the first real match.
+ createCellHints();
+ }
+
+ private void createCellHints() {
+ if (prefix == null) {
+ return;
+ }
+ // On reversed scan hint should be the prefix with last byte incremented
+ byte[] reversedHintBytes = increaseLastNonMaxByte(this.prefix);
+ this.reversedNextCellHint =
+ PrivateCellUtil.createFirstOnRow(reversedHintBytes, 0, (short) reversedHintBytes.length);
+ // On forward scan hint should be the prefix
+ this.forwardNextCellHint = PrivateCellUtil.createFirstOnRow(prefix, 0, (short) prefix.length);
}
public byte[] getPrefix() {
@@ -50,12 +70,15 @@ public class PrefixFilter extends FilterBase {
@Override
public boolean filterRowKey(Cell firstRowCell) {
- if (firstRowCell == null || this.prefix == null) return true;
- if (filterAllRemaining()) return true;
- int length = firstRowCell.getRowLength();
- if (length < prefix.length) return true;
+ if (firstRowCell == null || this.prefix == null) {
+ return true;
+ }
+ if (filterAllRemaining()) {
+ return true;
+ }
+ // if the cell is before => return false so that getNextCellHint() is invoked.
// if they are equal, return false => pass row
- // else return true, filter row
+ // if the cell is after => return true, filter row
// if we are passed the prefix, set flag
int cmp;
if (firstRowCell instanceof ByteBufferExtendedCell) {
@@ -70,12 +93,18 @@ public class PrefixFilter extends FilterBase {
passedPrefix = true;
}
filterRow = (cmp != 0);
- return filterRow;
+ provideHint = (!isReversed() && cmp < 0) || (isReversed() && cmp > 0);
+ return passedPrefix;
}
@Override
public ReturnCode filterCell(final Cell c) {
- if (filterRow) return ReturnCode.NEXT_ROW;
+ if (provideHint) {
+ return ReturnCode.SEEK_NEXT_USING_HINT;
+ }
+ if (filterRow) {
+ return ReturnCode.NEXT_ROW;
+ }
return ReturnCode.INCLUDE;
}
@@ -94,6 +123,27 @@ public class PrefixFilter extends FilterBase {
return passedPrefix;
}
+ @Override
+ public Cell getNextCellHint(Cell cell) {
+ if (reversed) {
+ return reversedNextCellHint;
+ } else {
+ return forwardNextCellHint;
+ }
+ }
+
+ private byte[] increaseLastNonMaxByte(byte[] bytes) {
+ byte[] result = Arrays.copyOf(bytes, bytes.length);
+ for (int i = bytes.length - 1; i >= 0; i--) {
+ byte b = bytes[i];
+ if (b < Byte.MAX_VALUE) {
+ result[i] = (byte) (b + 1);
+ break;
+ }
+ }
+ return result;
+ }
+
public static Filter createFilterFromArguments(ArrayList<byte[]> filterArguments) {
Preconditions.checkArgument(filterArguments.size() == 1, "Expected 1 but got: %s",
filterArguments.size());
@@ -105,7 +155,9 @@ public class PrefixFilter extends FilterBase {
@Override
public byte[] toByteArray() {
FilterProtos.PrefixFilter.Builder builder = FilterProtos.PrefixFilter.newBuilder();
- if (this.prefix != null) builder.setPrefix(UnsafeByteOperations.unsafeWrap(this.prefix));
+ if (this.prefix != null) {
+ builder.setPrefix(UnsafeByteOperations.unsafeWrap(this.prefix));
+ }
return builder.build().toByteArray();
}
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFilterList.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFilterList.java
index 26144d4adea..ede7b2d2ed2 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFilterList.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestFilterList.java
@@ -169,7 +169,9 @@ public class TestFilterList {
assertTrue(filterMPONE.filterRowKey(KeyValueUtil.createFirstOnRow(rowkey)));
kv = new KeyValue(rowkey, rowkey, Bytes.toBytes(0), Bytes.toBytes(0));
assertFalse(Filter.ReturnCode.INCLUDE == filterMPONE.filterCell(kv));
- assertFalse(filterMPONE.filterRow());
+ // FilterList.filterRow() returns true because previously "z" was filtered out (return true) by
+ // PrefixFilter.filterRowKey()
+ assertTrue(filterMPONE.filterRow());
/* We should filter any row */
rowkey = Bytes.toBytes("z");
diff --git a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestPrefixFilter.java b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestPrefixFilter.java
index 2a23c76bd7f..34e15cf920b 100644
--- a/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestPrefixFilter.java
+++ b/hbase-server/src/test/java/org/apache/hadoop/hbase/filter/TestPrefixFilter.java
@@ -17,9 +17,15 @@
*/
package org.apache.hadoop.hbase.filter;
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import org.apache.hadoop.hbase.Cell;
import org.apache.hadoop.hbase.HBaseClassTestRule;
+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;
@@ -40,7 +46,6 @@ public class TestPrefixFilter {
static final char FIRST_CHAR = 'a';
static final char LAST_CHAR = 'e';
static final String HOST_PREFIX = "org.apache.site-";
- static final byte[] GOOD_BYTES = Bytes.toBytes("abc");
@Before
public void setUp() throws Exception {
@@ -82,13 +87,182 @@ public class TestPrefixFilter {
}
String yahooSite = "com.yahoo.www";
byte[] yahooSiteBytes = Bytes.toBytes(yahooSite);
- assertTrue("Failed with character " + yahooSite,
- filter.filterRowKey(KeyValueUtil.createFirstOnRow(yahooSiteBytes)));
- assertEquals(filter.filterAllRemaining(), lastFilterAllRemaining);
+ KeyValue yahooSiteCell = KeyValueUtil.createFirstOnRow(yahooSiteBytes);
+ assertFalse("Failed with character " + yahooSite, filter.filterRowKey(yahooSiteCell));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT, filter.filterCell(yahooSiteCell));
+ assertEquals(lastFilterAllRemaining, filter.filterAllRemaining());
}
private byte[] createRow(final char c) {
return Bytes.toBytes(HOST_PREFIX + Character.toString(c));
}
+ @Test
+ public void shouldProvideHintWhenKeyBefore() {
+ byte[] prefix = Bytes.toBytes("gg");
+ PrefixFilter filter = new PrefixFilter(prefix);
+
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("aa"));
+
+ // Should include this row so that filterCell() will be invoked.
+ assertFalse(filter.filterRowKey(cell));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT, filter.filterCell(cell));
+ Cell actualCellHint = filter.getNextCellHint(cell);
+ assertNotNull(actualCellHint);
+ Cell expectedCellHint = KeyValueUtil.createFirstOnRow(prefix);
+ assertEquals(expectedCellHint, actualCellHint);
+ assertFalse(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void shouldProvideHintWhenKeyBeforeAndShorter() {
+ byte[] prefix = Bytes.toBytes("gggg");
+ PrefixFilter filter = new PrefixFilter(prefix);
+
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("aa"));
+
+ // Should include this row so that filterCell() will be invoked.
+ assertFalse(filter.filterRowKey(cell));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT, filter.filterCell(cell));
+ Cell actualCellHint = filter.getNextCellHint(cell);
+ assertNotNull(actualCellHint);
+ Cell expectedCellHint = KeyValueUtil.createFirstOnRow(prefix);
+ assertEquals(expectedCellHint, actualCellHint);
+ assertFalse(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void shouldIncludeWhenKeyMatches() {
+ PrefixFilter filter = new PrefixFilter(Bytes.toBytes("gg"));
+
+ KeyValue matchingCell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("gg"));
+
+ assertFalse(filter.filterRowKey(matchingCell));
+ assertEquals(Filter.ReturnCode.INCLUDE, filter.filterCell(matchingCell));
+ assertFalse(filter.filterAllRemaining());
+ assertFalse(filter.filterRow());
+ }
+
+ @Test
+ public void shouldReturnNextRowWhenKeyAfter() {
+ PrefixFilter filter = new PrefixFilter(Bytes.toBytes("gg"));
+
+ KeyValue afterCell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("pp"));
+
+ assertTrue(filter.filterRowKey(afterCell));
+ assertEquals(Filter.ReturnCode.NEXT_ROW, filter.filterCell(afterCell));
+ assertTrue(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void shouldProvideHintWhenKeyBeforeReversed() {
+ PrefixFilter filter = new PrefixFilter(Bytes.toBytes("aa"));
+ filter.setReversed(true);
+
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("x"));
+
+ // Should include this row so that filterCell() will be invoked.
+ assertFalse(filter.filterRowKey(cell));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT, filter.filterCell(cell));
+ Cell actualCellHint = filter.getNextCellHint(cell);
+ assertNotNull(actualCellHint);
+ Cell expectedCellHint = KeyValueUtil.createFirstOnRow(Bytes.toBytes("ab"));
+ assertEquals(expectedCellHint, actualCellHint);
+ assertFalse(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void hintShouldIncreaseLastNonMaxByteWhenReversed() {
+ PrefixFilter filter = new PrefixFilter(new byte[] { 'a', 'a', Byte.MAX_VALUE });
+ filter.setReversed(true);
+
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("x"));
+
+ // Should include this row so that filterCell() will be invoked.
+ assertFalse(filter.filterRowKey(cell));
+ assertEquals(Filter.ReturnCode.SEEK_NEXT_USING_HINT, filter.filterCell(cell));
+ Cell actualCellHint = filter.getNextCellHint(cell);
+ assertNotNull(actualCellHint);
+ Cell expectedCellHint = KeyValueUtil.createFirstOnRow(new byte[] { 'a', 'b', Byte.MAX_VALUE });
+ assertEquals(expectedCellHint, actualCellHint);
+ assertFalse(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void shouldIncludeWhenKeyMatchesReversed() {
+ PrefixFilter filter = new PrefixFilter(Bytes.toBytes("aa"));
+ filter.setReversed(true);
+
+ KeyValue matchingCell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("aa"));
+
+ assertFalse(filter.filterRowKey(matchingCell));
+ assertEquals(Filter.ReturnCode.INCLUDE, filter.filterCell(matchingCell));
+ assertFalse(filter.filterAllRemaining());
+ assertFalse(filter.filterRow());
+ }
+
+ @Test
+ public void shouldReturnNextRowWhenKeyAfterReversed() {
+ PrefixFilter filter = new PrefixFilter(Bytes.toBytes("dd"));
+ filter.setReversed(true);
+
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("aa"));
+
+ assertTrue(filter.filterRowKey(cell));
+ assertEquals(Filter.ReturnCode.NEXT_ROW, filter.filterCell(cell));
+ assertTrue(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void hintShouldNotIncreaseMaxBytesWhenReversed() {
+ PrefixFilter filter =
+ new PrefixFilter(new byte[] { Byte.MAX_VALUE, Byte.MAX_VALUE, Byte.MAX_VALUE });
+ filter.setReversed(true);
+
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("x"));
+
+ assertTrue(filter.filterRowKey(cell));
+ assertEquals(Filter.ReturnCode.NEXT_ROW, filter.filterCell(cell));
+ Cell actualCellHint = filter.getNextCellHint(cell);
+ assertNotNull(actualCellHint);
+ Cell expectedCellHint =
+ KeyValueUtil.createFirstOnRow(new byte[] { Byte.MAX_VALUE, Byte.MAX_VALUE, Byte.MAX_VALUE });
+ assertEquals(expectedCellHint, actualCellHint);
+ assertTrue(filter.filterAllRemaining());
+ assertTrue(filter.filterRow());
+ }
+
+ @Test
+ public void shouldNotThrowWhenCreatedWithNullPrefix() {
+ PrefixFilter filter = new PrefixFilter(null);
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("doesNotMatter"));
+
+ assertNull(filter.getNextCellHint(cell));
+ filter.setReversed(true);
+ assertNull(filter.getNextCellHint(cell));
+ }
+
+ @Test
+ public void shouldNotThrowWhenCreatedWithEmptyByteArrayPrefix() {
+ byte[] emptyPrefix = {};
+ KeyValue emptyPrefixCell = KeyValueUtil.createFirstOnRow(emptyPrefix);
+ KeyValue cell = KeyValueUtil.createFirstOnRow(Bytes.toBytes("doesNotMatter"));
+
+ PrefixFilter filter = new PrefixFilter(emptyPrefix);
+
+ Cell forwardNextCellHint = filter.getNextCellHint(cell);
+ assertNotNull(forwardNextCellHint);
+ assertEquals(emptyPrefixCell, forwardNextCellHint);
+
+ filter.setReversed(true);
+ Cell reverseNextCellHint = filter.getNextCellHint(cell);
+ assertNotNull(reverseNextCellHint);
+ assertEquals(emptyPrefixCell, reverseNextCellHint);
+ }
}