001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.filter;
019
020import static org.junit.jupiter.api.Assertions.assertEquals;
021import static org.junit.jupiter.api.Assertions.assertNotNull;
022import static org.junit.jupiter.api.Assertions.assertNull;
023
024import java.io.IOException;
025import java.nio.ByteBuffer;
026import java.util.ArrayList;
027import java.util.Arrays;
028import java.util.LinkedList;
029import java.util.List;
030import org.apache.hadoop.conf.Configuration;
031import org.apache.hadoop.hbase.Cell;
032import org.apache.hadoop.hbase.CellUtil;
033import org.apache.hadoop.hbase.CompareOperator;
034import org.apache.hadoop.hbase.HBaseTestingUtil;
035import org.apache.hadoop.hbase.HConstants;
036import org.apache.hadoop.hbase.TableName;
037import org.apache.hadoop.hbase.client.Durability;
038import org.apache.hadoop.hbase.client.Put;
039import org.apache.hadoop.hbase.client.Result;
040import org.apache.hadoop.hbase.client.ResultScanner;
041import org.apache.hadoop.hbase.client.Scan;
042import org.apache.hadoop.hbase.client.Table;
043import org.apache.hadoop.hbase.filter.FilterList.Operator;
044import org.apache.hadoop.hbase.regionserver.ConstantSizeRegionSplitPolicy;
045import org.apache.hadoop.hbase.testclassification.FilterTests;
046import org.apache.hadoop.hbase.testclassification.MediumTests;
047import org.apache.hadoop.hbase.util.Bytes;
048import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
049import org.apache.hadoop.hbase.util.Pair;
050import org.junit.jupiter.api.AfterAll;
051import org.junit.jupiter.api.BeforeAll;
052import org.junit.jupiter.api.Tag;
053import org.junit.jupiter.api.Test;
054import org.junit.jupiter.api.TestInfo;
055import org.slf4j.Logger;
056import org.slf4j.LoggerFactory;
057
058import org.apache.hbase.thirdparty.com.google.common.collect.Lists;
059
060@Tag(FilterTests.TAG)
061@Tag(MediumTests.TAG)
062public class TestFuzzyRowFilterEndToEnd {
063
064  private static final Logger LOG = LoggerFactory.getLogger(TestFuzzyRowFilterEndToEnd.class);
065
066  private static final HBaseTestingUtil TEST_UTIL = new HBaseTestingUtil();
067
068  private static final byte fuzzyValue = (byte) 63;
069
070  @BeforeAll
071  public static void setUpBeforeClass() throws Exception {
072    Configuration conf = TEST_UTIL.getConfiguration();
073    conf.setInt("hbase.client.scanner.caching", 1000);
074    conf.set(HConstants.HBASE_REGION_SPLIT_POLICY_KEY,
075      ConstantSizeRegionSplitPolicy.class.getName());
076    // set no splits
077    conf.setLong(HConstants.HREGION_MAX_FILESIZE, (1024L) * 1024 * 1024 * 10);
078
079    TEST_UTIL.startMiniCluster();
080  }
081
082  @AfterAll
083  public static void tearDownAfterClass() throws Exception {
084    TEST_UTIL.shutdownMiniCluster();
085  }
086
087  // HBASE-15676 Test that fuzzy info of all fixed bits (0s) finds matching row.
088  @Test
089  public void testAllFixedBits(TestInfo testInfo) throws IOException {
090    String cf = "f";
091    String cq = "q";
092
093    String name = testInfo.getTestMethod().get().getName();
094    Table ht = TEST_UTIL.createTable(TableName.valueOf(name), Bytes.toBytes(cf), Integer.MAX_VALUE);
095    // Load data
096    String[] rows = new String[] { "\\x9C\\x00\\x044\\x00\\x00\\x00\\x00",
097      "\\x9C\\x00\\x044\\x01\\x00\\x00\\x00", "\\x9C\\x00\\x044\\x00\\x01\\x00\\x00",
098      "\\x9B\\x00\\x044e\\x9B\\x02\\xBB", "\\x9C\\x00\\x044\\x00\\x00\\x01\\x00",
099      "\\x9C\\x00\\x044\\x00\\x01\\x00\\x01", "\\x9B\\x00\\x044e\\xBB\\xB2\\xBB", };
100
101    for (int i = 0; i < rows.length; i++) {
102      Put p = new Put(Bytes.toBytesBinary(rows[i]));
103      p.addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq), Bytes.toBytes("value"));
104      ht.put(p);
105    }
106
107    TEST_UTIL.flush();
108
109    List<Pair<byte[], byte[]>> data = new ArrayList<>();
110    byte[] fuzzyKey = Bytes.toBytesBinary("\\x9B\\x00\\x044e");
111    byte[] mask = new byte[] { 0, 0, 0, 0, 0 };
112
113    // copy the fuzzy key and mask to test HBASE-18617
114    byte[] copyFuzzyKey = Arrays.copyOf(fuzzyKey, fuzzyKey.length);
115    byte[] copyMask = Arrays.copyOf(mask, mask.length);
116
117    data.add(new Pair<>(fuzzyKey, mask));
118    FuzzyRowFilter filter = new FuzzyRowFilter(data);
119
120    Scan scan = new Scan();
121    scan.setFilter(filter);
122
123    ResultScanner scanner = ht.getScanner(scan);
124    int total = 0;
125    while (scanner.next() != null) {
126      total++;
127    }
128    assertEquals(2, total);
129
130    assertEquals(true, Arrays.equals(copyFuzzyKey, fuzzyKey));
131    assertEquals(true, Arrays.equals(copyMask, mask));
132
133    TEST_UTIL.deleteTable(TableName.valueOf(name));
134  }
135
136  @Test
137  public void testHBASE14782(TestInfo testInfo) throws IOException {
138    String cf = "f";
139    String cq = "q";
140
141    String name = testInfo.getTestMethod().get().getName();
142    Table ht = TEST_UTIL.createTable(TableName.valueOf(name), Bytes.toBytes(cf), Integer.MAX_VALUE);
143    // Load data
144    String[] rows =
145      new String[] { "\\x9C\\x00\\x044\\x00\\x00\\x00\\x00", "\\x9C\\x00\\x044\\x01\\x00\\x00\\x00",
146        "\\x9C\\x00\\x044\\x00\\x01\\x00\\x00", "\\x9C\\x00\\x044\\x00\\x00\\x01\\x00",
147        "\\x9C\\x00\\x044\\x00\\x01\\x00\\x01", "\\x9B\\x00\\x044e\\xBB\\xB2\\xBB", };
148
149    String badRow = "\\x9C\\x00\\x03\\xE9e\\xBB{X\\x1Fwts\\x1F\\x15vRX";
150
151    for (int i = 0; i < rows.length; i++) {
152      Put p = new Put(Bytes.toBytesBinary(rows[i]));
153      p.addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq), Bytes.toBytes("value"));
154      ht.put(p);
155    }
156
157    Put p = new Put(Bytes.toBytesBinary(badRow));
158    p.addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq), Bytes.toBytes("value"));
159    ht.put(p);
160
161    TEST_UTIL.flush();
162
163    List<Pair<byte[], byte[]>> data = new ArrayList<>();
164    byte[] fuzzyKey = Bytes.toBytesBinary("\\x00\\x00\\x044");
165    byte[] mask = new byte[] { 1, 0, 0, 0 };
166    data.add(new Pair<>(fuzzyKey, mask));
167    FuzzyRowFilter filter = new FuzzyRowFilter(data);
168
169    Scan scan = new Scan();
170    scan.setFilter(filter);
171
172    ResultScanner scanner = ht.getScanner(scan);
173    int total = 0;
174    while (scanner.next() != null) {
175      total++;
176    }
177    assertEquals(rows.length, total);
178    TEST_UTIL.deleteTable(TableName.valueOf(name));
179  }
180
181  @Test
182  public void testFilterList(TestInfo testInfo) throws Exception {
183    String cf = "f";
184    Table ht = TEST_UTIL.createTable(TableName.valueOf(testInfo.getTestMethod().get().getName()),
185      Bytes.toBytes(cf), Integer.MAX_VALUE);
186
187    // 10 byte row key - (2 bytes 4 bytes 4 bytes)
188    // 4 byte qualifier
189    // 4 byte value
190
191    for (int i1 = 0; i1 < 5; i1++) {
192      for (int i2 = 0; i2 < 5; i2++) {
193        byte[] rk = new byte[10];
194
195        ByteBuffer buf = ByteBuffer.wrap(rk);
196        buf.clear();
197        buf.putShort((short) 2);
198        buf.putInt(i1);
199        buf.putInt(i2);
200
201        // Each row contains 5 columns
202        for (int c = 0; c < 5; c++) {
203          byte[] cq = new byte[4];
204          Bytes.putBytes(cq, 0, Bytes.toBytes(c), 0, 4);
205
206          Put p = new Put(rk);
207          p.setDurability(Durability.SKIP_WAL);
208          p.addColumn(Bytes.toBytes(cf), cq, Bytes.toBytes(c));
209          ht.put(p);
210          LOG.info(
211            "Inserting: rk: " + Bytes.toStringBinary(rk) + " cq: " + Bytes.toStringBinary(cq));
212        }
213      }
214    }
215
216    TEST_UTIL.flush();
217
218    // test passes if we get back 5 KV's (1 row)
219    runTest(ht, 5);
220
221  }
222
223  private void runTest(Table hTable, int expectedSize) throws IOException {
224    // [0, 2, ?, ?, ?, ?, 0, 0, 0, 1]
225    byte[] fuzzyKey1 = new byte[10];
226    ByteBuffer buf = ByteBuffer.wrap(fuzzyKey1);
227    buf.clear();
228    buf.putShort((short) 2);
229    for (int i = 0; i < 4; i++)
230      buf.put(fuzzyValue);
231    buf.putInt((short) 1);
232    byte[] mask1 = new byte[] { 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 };
233
234    byte[] fuzzyKey2 = new byte[10];
235    buf = ByteBuffer.wrap(fuzzyKey2);
236    buf.clear();
237    buf.putShort((short) 2);
238    buf.putInt((short) 2);
239    for (int i = 0; i < 4; i++)
240      buf.put(fuzzyValue);
241
242    byte[] mask2 = new byte[] { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
243
244    Pair<byte[], byte[]> pair1 = new Pair<>(fuzzyKey1, mask1);
245    Pair<byte[], byte[]> pair2 = new Pair<>(fuzzyKey2, mask2);
246
247    FuzzyRowFilter fuzzyRowFilter1 = new FuzzyRowFilter(Lists.newArrayList(pair1));
248    FuzzyRowFilter fuzzyRowFilter2 = new FuzzyRowFilter(Lists.newArrayList(pair2));
249    // regular test - we expect 1 row back (5 KVs)
250    runScanner(hTable, expectedSize, fuzzyRowFilter1, fuzzyRowFilter2);
251  }
252
253  private void runScanner(Table hTable, int expectedSize, Filter filter1, Filter filter2)
254    throws IOException {
255    String cf = "f";
256    Scan scan = new Scan();
257    scan.addFamily(Bytes.toBytes(cf));
258    FilterList filterList = new FilterList(Operator.MUST_PASS_ALL, filter1, filter2);
259    scan.setFilter(filterList);
260
261    ResultScanner scanner = hTable.getScanner(scan);
262    List<Cell> results = new ArrayList<>();
263    Result result;
264    long timeBeforeScan = EnvironmentEdgeManager.currentTime();
265    while ((result = scanner.next()) != null) {
266      for (Cell kv : result.listCells()) {
267        LOG.info("Got rk: " + Bytes.toStringBinary(CellUtil.cloneRow(kv)) + " cq: "
268          + Bytes.toStringBinary(CellUtil.cloneQualifier(kv)));
269        results.add(kv);
270      }
271    }
272    long scanTime = EnvironmentEdgeManager.currentTime() - timeBeforeScan;
273    scanner.close();
274
275    LOG.info("scan time = " + scanTime + "ms");
276    LOG.info("found " + results.size() + " results");
277
278    assertEquals(expectedSize, results.size());
279  }
280
281  @Test
282  public void testHBASE26967(TestInfo testInfo) throws IOException {
283    byte[] row1 = Bytes.toBytes("1");
284    byte[] row2 = Bytes.toBytes("2");
285    String cf1 = "f1";
286    String cf2 = "f2";
287    String cq1 = "col1";
288    String cq2 = "col2";
289
290    String name = testInfo.getTestMethod().get().getName();
291    Table ht = TEST_UTIL.createTable(TableName.valueOf(name), new String[] { cf1, cf2 });
292
293    // Put data
294    List<Put> puts = Lists.newArrayList();
295    puts.add(new Put(row1).addColumn(Bytes.toBytes(cf1), Bytes.toBytes(cq1), Bytes.toBytes("a1")));
296    puts.add(new Put(row1).addColumn(Bytes.toBytes(cf2), Bytes.toBytes(cq2), Bytes.toBytes("a2")));
297    puts.add(new Put(row2).addColumn(Bytes.toBytes(cf1), Bytes.toBytes(cq1), Bytes.toBytes("b1")));
298    puts.add(new Put(row2).addColumn(Bytes.toBytes(cf2), Bytes.toBytes(cq2), Bytes.toBytes("b2")));
299    ht.put(puts);
300
301    TEST_UTIL.flush();
302
303    // FuzzyRowFilter
304    List<Pair<byte[], byte[]>> data = Lists.newArrayList();
305    byte[] fuzzyKey = Bytes.toBytes("1");
306    byte[] mask = new byte[] { 0 };
307    data.add(new Pair<>(fuzzyKey, mask));
308    FuzzyRowFilter fuzzyRowFilter = new FuzzyRowFilter(data);
309
310    // SingleColumnValueFilter
311    Filter singleColumnValueFilter = new SingleColumnValueFilter(Bytes.toBytes(cf2),
312      Bytes.toBytes(cq2), CompareOperator.EQUAL, Bytes.toBytes("x"));
313
314    // FilterList
315    FilterList filterList = new FilterList(Operator.MUST_PASS_ONE);
316    filterList.addFilter(Lists.newArrayList(fuzzyRowFilter, singleColumnValueFilter));
317
318    Scan scan = new Scan();
319    scan.setFilter(filterList);
320
321    ResultScanner scanner = ht.getScanner(scan);
322    Result rs = scanner.next();
323    assertEquals(0, Bytes.compareTo(row1, rs.getRow()));
324
325    // The two cells (1,f1,col1,a1) (1,f2,col2,a2)
326    assertEquals(2, rs.listCells().size());
327
328    // Only one row who's rowKey=1
329    assertNull(scanner.next());
330
331    TEST_UTIL.deleteTable(TableName.valueOf(name));
332  }
333
334  @Test
335  public void testReverseScanMovesPastSameRowFuzzyHint(TestInfo testInfo) throws IOException {
336    final String cf = "f";
337    final String cq = "q";
338
339    String name = testInfo.getTestMethod().orElseThrow(AssertionError::new).getName();
340    try (Table ht = TEST_UTIL.createTable(TableName.valueOf(name), Bytes.toBytes(cf))) {
341      List<Put> puts = Lists.newArrayList();
342      puts.add(new Put(Bytes.toBytes("aaa")).addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq),
343        Bytes.toBytes("v")));
344      puts.add(new Put(Bytes.toBytes("aba")).addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq),
345        Bytes.toBytes("v")));
346      puts.add(new Put(Bytes.toBytes("abaa")).addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq),
347        Bytes.toBytes("v")));
348      puts.add(new Put(Bytes.toBytes("abb")).addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq),
349        Bytes.toBytes("v")));
350      puts.add(new Put(Bytes.toBytes("abc")).addColumn(Bytes.toBytes(cf), Bytes.toBytes(cq),
351        Bytes.toBytes("v")));
352      ht.put(puts);
353
354      TEST_UTIL.flush();
355
356      List<Pair<byte[], byte[]>> fuzzyList = new LinkedList<>();
357      fuzzyList.add(new Pair<>(Bytes.toBytes("aaa"), new byte[] { 0, 1, 0 }));
358
359      Scan scan = new Scan();
360      scan.setReversed(true);
361      scan.setFilter(new FuzzyRowFilter(fuzzyList));
362
363      try (ResultScanner scanner = ht.getScanner(scan)) {
364        Result result = scanner.next();
365        assertNotNull(result);
366        assertEquals("abaa", Bytes.toString(result.getRow()));
367        result = scanner.next();
368        assertNotNull(result);
369        assertEquals("aba", Bytes.toString(result.getRow()));
370        result = scanner.next();
371        assertNotNull(result);
372        assertEquals("aaa", Bytes.toString(result.getRow()));
373        assertNull(scanner.next());
374      }
375    }
376
377    TEST_UTIL.deleteTable(TableName.valueOf(name));
378  }
379
380  @Test
381  public void testReverseScanMovesPastSameRowFuzzyHintAcrossMultipleCells(TestInfo testInfo)
382    throws IOException {
383    final String cf = "f";
384
385    String name = testInfo.getTestMethod().orElseThrow(AssertionError::new).getName();
386    try (Table ht = TEST_UTIL.createTable(TableName.valueOf(name), Bytes.toBytes(cf))) {
387      List<Put> puts = Lists.newArrayList();
388      puts.add(new Put(Bytes.toBytes("aaa")).addColumn(Bytes.toBytes(cf), Bytes.toBytes("q1"),
389        Bytes.toBytes("v")));
390      puts.add(new Put(Bytes.toBytes("aba")).addColumn(Bytes.toBytes(cf), Bytes.toBytes("q1"),
391        Bytes.toBytes("v")));
392      puts.add(new Put(Bytes.toBytes("abaa")).addColumn(Bytes.toBytes(cf), Bytes.toBytes("q1"),
393        Bytes.toBytes("v")));
394      // The same-row reverse hint can be recreated for each cell on this non-matching row.
395      // Before the fix, the first cell could loop inside RowTracker and never return to
396      // StoreScanner. After the fix, NEXT_ROW skips the whole row without skipping abaa.
397      puts.add(new Put(Bytes.toBytes("abb"))
398        .addColumn(Bytes.toBytes(cf), Bytes.toBytes("q1"), Bytes.toBytes("v1"))
399        .addColumn(Bytes.toBytes(cf), Bytes.toBytes("q2"), Bytes.toBytes("v2"))
400        .addColumn(Bytes.toBytes(cf), Bytes.toBytes("q3"), Bytes.toBytes("v3")));
401      puts.add(new Put(Bytes.toBytes("abc")).addColumn(Bytes.toBytes(cf), Bytes.toBytes("q1"),
402        Bytes.toBytes("v")));
403      ht.put(puts);
404
405      TEST_UTIL.flush();
406
407      List<Pair<byte[], byte[]>> fuzzyList = new LinkedList<>();
408      fuzzyList.add(new Pair<>(Bytes.toBytes("aaa"), new byte[] { 0, 1, 0 }));
409
410      Scan scan = new Scan();
411      scan.setReversed(true);
412      scan.setFilter(new FuzzyRowFilter(fuzzyList));
413
414      try (ResultScanner scanner = ht.getScanner(scan)) {
415        Result result = scanner.next();
416        assertNotNull(result);
417        assertEquals("abaa", Bytes.toString(result.getRow()));
418        result = scanner.next();
419        assertNotNull(result);
420        assertEquals("aba", Bytes.toString(result.getRow()));
421        result = scanner.next();
422        assertNotNull(result);
423        assertEquals("aaa", Bytes.toString(result.getRow()));
424        assertNull(scanner.next());
425      }
426    }
427
428    TEST_UTIL.deleteTable(TableName.valueOf(name));
429  }
430
431  @Test
432  public void testHBASE28634(TestInfo testInfo) throws IOException {
433    final String CF = "f";
434    final String CQ = "name";
435
436    String name = testInfo.getTestMethod().get().getName();
437    Table ht = TEST_UTIL.createTable(TableName.valueOf(name), Bytes.toBytes(CF));
438
439    // Put data
440    List<Put> puts = Lists.newArrayList();
441    puts.add(new Put(Bytes.toBytes("111311")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
442      Bytes.toBytes("a1")));
443    puts.add(new Put(Bytes.toBytes("111444")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
444      Bytes.toBytes("a2")));
445    puts.add(new Put(Bytes.toBytes("111511")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
446      Bytes.toBytes("a3")));
447    puts.add(new Put(Bytes.toBytes("111611")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
448      Bytes.toBytes("a4")));
449    puts.add(new Put(Bytes.toBytes("111446")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
450      Bytes.toBytes("a5")));
451    // Keep a real boundary row at the reverse hint target so this test also guards HBASE-28634.
452    puts.add(new Put(Bytes.toBytes("1115")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
453      Bytes.toBytes("a6")));
454    puts.add(new Put(Bytes.toBytes("111777")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
455      Bytes.toBytes("a7")));
456    puts.add(new Put(Bytes.toBytes("111777")).addColumn(Bytes.toBytes(CF), Bytes.toBytes(CQ),
457      Bytes.toBytes("a")));
458    ht.put(puts);
459
460    TEST_UTIL.flush();
461
462    // Forward scan
463    LinkedList<Pair<byte[], byte[]>> fuzzyList = new LinkedList<>();
464    byte[] fuzzyRowKey = Bytes.toBytes("111433");
465    byte[] mask = Bytes.toBytesBinary("\\xFF\\xFF\\xFF\\xFF\\x02\\x02");
466    fuzzyList.add(new Pair<>(fuzzyRowKey, mask));
467    FuzzyRowFilter fuzzyRowFilter = new FuzzyRowFilter(fuzzyList);
468
469    Scan scan = new Scan();
470    scan.setFilter(fuzzyRowFilter);
471
472    ResultScanner scanner = ht.getScanner(scan);
473    List<byte[]> actualRowsList = new ArrayList<>();
474    for (Result result : scanner) {
475      byte[] row = result.getRow();
476      actualRowsList.add(row);
477    }
478
479    assertEquals(2, actualRowsList.size());
480    assertEquals("111444", Bytes.toString(actualRowsList.get(0)));
481    assertEquals("111446", Bytes.toString(actualRowsList.get(1)));
482
483    // Reverse scan
484    scan = new Scan();
485    scan.setFilter(fuzzyRowFilter);
486    scan.setReversed(true);
487
488    scanner = ht.getScanner(scan);
489    actualRowsList = new ArrayList<>();
490    for (Result result : scanner) {
491      byte[] row = result.getRow();
492      actualRowsList.add(row);
493    }
494
495    assertEquals(2, actualRowsList.size());
496    assertEquals("111446", Bytes.toString(actualRowsList.get(0)));
497    assertEquals("111444", Bytes.toString(actualRowsList.get(1)));
498
499    TEST_UTIL.deleteTable(TableName.valueOf(name));
500  }
501}