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 org.apache.hadoop.hbase.HBaseClassTestRule;
021import org.apache.hadoop.hbase.KeyValue;
022import org.apache.hadoop.hbase.KeyValueUtil;
023import org.apache.hadoop.hbase.testclassification.FilterTests;
024import org.apache.hadoop.hbase.testclassification.SmallTests;
025import org.apache.hadoop.hbase.util.Bytes;
026import org.junit.Assert;
027import org.junit.ClassRule;
028import org.junit.Test;
029import org.junit.experimental.categories.Category;
030
031@Category({ FilterTests.class, SmallTests.class })
032public class TestFuzzyRowFilter {
033
034  @ClassRule
035  public static final HBaseClassTestRule CLASS_RULE =
036    HBaseClassTestRule.forClass(TestFuzzyRowFilter.class);
037
038  @Test
039  public void testSatisfiesNoUnsafeForward() {
040
041    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
042      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, (byte) -128, 1, 0, 1 }, 0, 5,
043        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
044
045    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
046      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, (byte) -128, 2, 0, 1 }, 0, 5,
047        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
048
049    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfiesNoUnsafe(false,
050      new byte[] { 1, 2, 1, 3, 3 }, 0, 5, new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
051
052    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
053      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, 1, 1, 3, 0 }, // row to check
054        0, 5, new byte[] { 1, 2, 0, 3 }, // fuzzy row
055        new byte[] { 0, 0, 1, 0 })); // mask
056
057    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
058      FuzzyRowFilter.satisfiesNoUnsafe(false, new byte[] { 1, 1, 1, 3, 0 }, 0, 5,
059        new byte[] { 1, (byte) 245, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
060
061    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfiesNoUnsafe(
062      false, new byte[] { 1, 2, 1, 0, 1 }, 0, 5, new byte[] { 0, 1, 2 }, new byte[] { 1, 0, 0 }));
063  }
064
065  @Test
066  public void testSatisfiesForward() {
067
068    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(false,
069      new byte[] { 1, (byte) -128, 1, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
070
071    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(false,
072      new byte[] { 1, (byte) -128, 2, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
073
074    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(false,
075      new byte[] { 1, 2, 1, 3, 3 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
076
077    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
078      FuzzyRowFilter.satisfies(false, new byte[] { 1, 1, 1, 3, 0 }, // row to check
079        new byte[] { 1, 2, 0, 3 }, // fuzzy row
080        new byte[] { -1, -1, 0, -1 })); // mask
081
082    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
083      FuzzyRowFilter.satisfies(false, new byte[] { 1, 1, 1, 3, 0 },
084        new byte[] { 1, (byte) 245, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
085
086    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(false,
087      new byte[] { 1, 2, 1, 0, 1 }, new byte[] { 0, 1, 2 }, new byte[] { 0, -1, -1 }));
088  }
089
090  @Test
091  public void testSatisfiesReverse() {
092    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(true,
093      new byte[] { 1, (byte) -128, 1, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
094
095    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
096      new byte[] { 1, (byte) -128, 2, 0, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
097
098    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
099      new byte[] { 2, 3, 1, 1, 1 }, new byte[] { 1, 0, 1 }, new byte[] { -1, 0, -1 }));
100
101    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfies(true,
102      new byte[] { 1, 2, 1, 3, 3 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
103
104    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
105      FuzzyRowFilter.satisfies(true, new byte[] { 1, (byte) 245, 1, 3, 0 },
106        new byte[] { 1, 1, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
107
108    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
109      new byte[] { 1, 3, 1, 3, 0 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
110
111    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
112      new byte[] { 2, 1, 1, 1, 0 }, new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
113
114    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfies(true,
115      new byte[] { 1, 2, 1, 0, 1 }, new byte[] { 0, 1, 2 }, new byte[] { 0, -1, -1 }));
116  }
117
118  @Test
119  public void testSatisfiesNoUnsafeReverse() {
120    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
121      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, (byte) -128, 1, 0, 1 }, 0, 5,
122        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
123
124    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
125      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, (byte) -128, 2, 0, 1 }, 0, 5,
126        new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
127
128    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfiesNoUnsafe(
129      true, new byte[] { 2, 3, 1, 1, 1 }, 0, 5, new byte[] { 1, 0, 1 }, new byte[] { 0, 1, 0 }));
130
131    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES, FuzzyRowFilter.satisfiesNoUnsafe(true,
132      new byte[] { 1, 2, 1, 3, 3 }, 0, 5, new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
133
134    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
135      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, (byte) 245, 1, 3, 0 }, 0, 5,
136        new byte[] { 1, 1, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
137
138    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
139      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 1, 3, 1, 3, 0 }, 0, 5,
140        new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
141
142    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
143      FuzzyRowFilter.satisfiesNoUnsafe(true, new byte[] { 2, 1, 1, 1, 0 }, 0, 5,
144        new byte[] { 1, 2, 0, 3 }, new byte[] { 0, 0, 1, 0 }));
145
146    Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS, FuzzyRowFilter.satisfiesNoUnsafe(
147      true, new byte[] { 1, 2, 1, 0, 1 }, 0, 5, new byte[] { 0, 1, 2 }, new byte[] { 1, 0, 0 }));
148  }
149
150  @Test
151  public void testGetNextForFuzzyRuleForward() {
152    assertNext(false, new byte[] { 0, 1, 2 }, // fuzzy row
153      new byte[] { 0, -1, -1 }, // mask
154      new byte[] { 1, 2, 1, 0, 1 }, // current
155      new byte[] { 2, 1, 2 }); // expected next
156
157    assertNext(false, new byte[] { 0, 1, 2 }, // fuzzy row
158      new byte[] { 0, -1, -1 }, // mask
159      new byte[] { 1, 1, 2, 0, 1 }, // current
160      new byte[] { 1, 1, 2, 0, 2 }); // expected next
161
162    assertNext(false, new byte[] { 0, 1, 0, 2, 0 }, // fuzzy row
163      new byte[] { 0, -1, 0, -1, 0 }, // mask
164      new byte[] { 1, 0, 2, 0, 1 }, // current
165      new byte[] { 1, 1, 0, 2 }); // expected next
166
167    assertNext(false, new byte[] { 1, 0, 1 }, // fuzzy row
168      new byte[] { -1, 0, -1 }, // mask
169      new byte[] { 1, (byte) 128, 2, 0, 1 }, // current
170      new byte[] { 1, (byte) 129, 1 }); // expected next
171
172    assertNext(false, new byte[] { 0, 1, 0, 1 }, // fuzzy row
173      new byte[] { 0, -1, 0, -1 }, // mask
174      new byte[] { 5, 1, 0, 1 }, // current
175      new byte[] { 5, 1, 1, 1 }); // expected next
176
177    assertNext(false, new byte[] { 0, 1, 0, 1 }, // fuzzy row
178      new byte[] { 0, -1, 0, -1 }, // mask
179      new byte[] { 5, 1, 0, 1, 1 }, // current
180      new byte[] { 5, 1, 0, 1, 2 }); // expected next
181
182    assertNext(false, new byte[] { 0, 1, 0, 0 }, // fuzzy row
183      new byte[] { 0, -1, 0, 0 }, // mask
184      new byte[] { 5, 1, (byte) 255, 1 }, // current
185      new byte[] { 5, 1, (byte) 255, 2 }); // expected next
186
187    assertNext(false, new byte[] { 0, 1, 0, 1 }, // fuzzy row
188      new byte[] { 0, -1, 0, -1 }, // mask
189      new byte[] { 5, 1, (byte) 255, 1 }, // current
190      new byte[] { 6, 1, 0, 1 }); // expected next
191
192    assertNext(false, new byte[] { 0, 1, 0, 1 }, // fuzzy row
193      new byte[] { 0, -1, 0, -1 }, // mask
194      new byte[] { 5, 1, (byte) 255, 0 }, // current
195      new byte[] { 5, 1, (byte) 255, 1 }); // expected next
196
197    assertNext(false, new byte[] { 5, 1, 1, 0 }, // fuzzy row
198      new byte[] { -1, -1, 0, 0 }, // mask
199      new byte[] { 5, 1, (byte) 255, 1 }, // current
200      new byte[] { 5, 1, (byte) 255, 2 }); // expected next
201
202    assertNext(false, new byte[] { 1, 1, 1, 1 }, // fuzzy row
203      new byte[] { -1, -1, 0, 0 }, // mask
204      new byte[] { 1, 1, 2, 2 }, // current
205      new byte[] { 1, 1, 2, 3 }); // expected next
206
207    assertNext(false, new byte[] { 1, 1, 1, 1 }, // fuzzy row
208      new byte[] { -1, -1, 0, 0 }, // mask
209      new byte[] { 1, 1, 3, 2 }, // current
210      new byte[] { 1, 1, 3, 3 }); // expected next
211
212    assertNext(false, new byte[] { 1, 1, 1, 1 }, // fuzzy row
213      new byte[] { 0, 0, 0, 0 }, // mask
214      new byte[] { 1, 1, 2, 3 }, // current
215      new byte[] { 1, 1, 2, 4 }); // expected next
216
217    assertNext(false, new byte[] { 1, 1, 1, 1 }, // fuzzy row
218      new byte[] { 0, 0, 0, 0 }, // mask
219      new byte[] { 1, 1, 3, 2 }, // current
220      new byte[] { 1, 1, 3, 3 }); // expected next
221
222    assertNext(false, new byte[] { 1, 1, 0, 0 }, // fuzzy row
223      new byte[] { -1, -1, 0, 0 }, // mask
224      new byte[] { 0, 1, 3, 2 }, // current
225      new byte[] { 1, 1 }); // expected next
226
227    // No next for this one
228    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 2, 3, 1, 1, 1 }, // row to
229                                                                                       // check
230      new byte[] { 1, 0, 1 }, // fuzzy row
231      new byte[] { -1, 0, -1 })); // mask
232    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 1, (byte) 245, 1, 3, 0 },
233      new byte[] { 1, 1, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
234    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 1, 3, 1, 3, 0 },
235      new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
236    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(new byte[] { 2, 1, 1, 1, 0 },
237      new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
238  }
239
240  @Test
241  public void testGetNextForFuzzyRuleReverse() {
242    // In these reverse cases for the next row key the last non-max byte should be increased
243    // to make sure that the proper row is selected next by the scanner.
244    // For example:
245    // fuzzy row: 0,1,2
246    // mask: 0,-1,-1
247    // current: 1,2,1,0,1
248    // next would be: 1,1,2
249    // this has to be increased to 1,1,3 to make sure that the proper row is selected next.
250    assertNext(true, new byte[] { 0, 1, 2 }, // fuzzy row
251      new byte[] { 0, -1, -1 }, // mask
252      new byte[] { 1, 2, 1, 0, 1 }, // current
253      new byte[] { 1, 1, 3 }); // expected next
254
255    assertNext(true, new byte[] { 0, 1, 0, 2, 0 }, // fuzzy row
256      new byte[] { 0, -1, 0, -1, 0 }, // mask
257      new byte[] { 1, 2, 1, 3, 1 }, // current
258      new byte[] { 1, 1, (byte) 255, 3 }); // expected next
259
260    assertNext(true, new byte[] { 1, 0, 1 }, // fuzzy row
261      new byte[] { -1, 0, -1 }, // mask
262      new byte[] { 1, (byte) 128, 2, 0, 1 }, // current
263      new byte[] { 1, (byte) 128, 2 }); // expected next
264
265    assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
266      new byte[] { 0, -1, 0, -1 }, // mask
267      new byte[] { 5, 1, 0, 2, 1 }, // current
268      new byte[] { 5, 1, 0, 2 }); // expected next
269
270    assertNext(true, new byte[] { 0, 1, 0, 0 }, // fuzzy row
271      new byte[] { 0, -1, 0, 0 }, // mask
272      new byte[] { 5, 1, (byte) 255, 1 }, // current
273      new byte[] { 5, 1, (byte) 255, 1 }); // expected next
274
275    assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
276      new byte[] { 0, -1, 0, -1 }, // mask
277      new byte[] { 5, 1, 0, 1 }, // current
278      new byte[] { 4, 1, (byte) 255, 2 }); // expected next
279
280    assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
281      new byte[] { 0, -1, 0, -1 }, // mask
282      new byte[] { 5, 1, (byte) 255, 0 }, // current
283      new byte[] { 5, 1, (byte) 254, 2 }); // expected next
284
285    assertNext(true, new byte[] { 1, 1, 0, 0 }, // fuzzy row
286      new byte[] { -1, -1, 0, 0 }, // mask
287      new byte[] { 2, 1, 3, 2 }, // current
288      new byte[] { 1, 2 }); // expected next
289
290    assertNext(true, new byte[] { 1, 0, 1 }, // fuzzy row
291      new byte[] { -1, 0, -1 }, // mask
292      new byte[] { 2, 3, 1, 1, 1 }, // row to check
293      new byte[] { 1, (byte) 255, 2 }); // expected next
294
295    assertNext(true, new byte[] { 1, 1, 0, 3 }, // fuzzy row
296      new byte[] { -1, -1, 0, -1 }, // mask
297      new byte[] { 1, (byte) 245, 1, 3, 0 }, // row to check
298      new byte[] { 1, 1, (byte) 255, 4 }); // expected next
299
300    assertNext(true, new byte[] { 1, 2, 0, 3 }, // fuzzy row
301      new byte[] { -1, -1, 0, -1 }, // mask
302      new byte[] { 1, 3, 1, 3, 0 }, // row to check
303      new byte[] { 1, 2, (byte) 255, 4 }); // expected next
304
305    assertNext(true, new byte[] { 1, 2, 0, 3 }, // fuzzy row
306      new byte[] { -1, -1, 0, -1 }, // mask
307      new byte[] { 2, 1, 1, 1, 0 }, // row to check
308      new byte[] { 1, 2, (byte) 255, 4 }); // expected next
309
310    assertNext(true, new byte[] { 1, 0, 1 }, // fuzzy row
311      new byte[] { -1, 0, -1 }, // mask
312      new byte[] { 1, (byte) 128, 2 }, // row to check
313      new byte[] { 1, (byte) 128, 2 }); // expected next
314
315    assertNext(true, new byte[] { 0, 1, 0, 1 }, // fuzzy row
316      new byte[] { 0, -1, 0, -1 }, // mask
317      new byte[] { 5, 1, 0, 2 }, // row to check
318      new byte[] { 5, 1, 0, 2 }); // expected next
319
320    assertNext(true, new byte[] { 5, 1, 1, 0 }, // fuzzy row
321      new byte[] { -1, -1, 0, 0 }, // mask
322      new byte[] { 5, 1, (byte) 0xFF, 1 }, // row to check
323      new byte[] { 5, 1, (byte) 0xFF, 1 }); // expected next
324
325    assertNext(true, new byte[] { 1, 1, 1, 1 }, // fuzzy row
326      new byte[] { -1, -1, 0, 0 }, // mask
327      new byte[] { 1, 1, 2, 2 }, // row to check
328      new byte[] { 1, 1, 2, 2 }); // expected next
329
330    assertNext(true, new byte[] { 1, 1, 1, 1 }, // fuzzy row
331      new byte[] { 0, 0, 0, 0 }, // mask
332      new byte[] { 1, 1, 2, 3 }, // row to check
333      new byte[] { 1, 1, 2, 3 }); // expected next
334
335    // no before cell than current which satisfies the fuzzy row -> null
336    Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(true, new byte[] { 1, 1, 1, 3, 0 },
337      new byte[] { 1, 2, 0, 3 }, new byte[] { -1, -1, 0, -1 }));
338  }
339
340  private static void assertNext(boolean reverse, byte[] fuzzyRow, byte[] mask, byte[] current,
341    byte[] expected) {
342    KeyValue kv = KeyValueUtil.createFirstOnRow(current);
343    byte[] nextForFuzzyRule = FuzzyRowFilter.getNextForFuzzyRule(reverse, kv.getRowArray(),
344      kv.getRowOffset(), kv.getRowLength(), fuzzyRow, mask);
345    Assert.assertEquals(Bytes.toStringBinary(expected), Bytes.toStringBinary(nextForFuzzyRule));
346  }
347}