View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.hadoop.hbase.filter;
19  
20  import org.apache.hadoop.hbase.KeyValue;
21  import org.apache.hadoop.hbase.KeyValueUtil;
22  import org.apache.hadoop.hbase.testclassification.SmallTests;
23  import org.apache.hadoop.hbase.util.Bytes;
24  import org.junit.Assert;
25  import org.junit.Test;
26  import org.junit.experimental.categories.Category;
27  
28  @Category(SmallTests.class)
29  public class TestFuzzyRowFilter {
30    @Test
31    public void testSatisfiesNoUnsafeForward() {
32  
33      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
34              FuzzyRowFilter.satisfiesNoUnsafe(false,
35                                       new byte[]{1, (byte) -128, 1, 0, 1},
36                                       0, 5,
37                                       new byte[]{1, 0, 1},
38                                       new byte[]{0, 1, 0}));
39  
40      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
41              FuzzyRowFilter.satisfiesNoUnsafe(false,
42                                       new byte[]{1, (byte) -128, 2, 0, 1},
43                                       0, 5,
44                                       new byte[]{1, 0, 1},
45                                       new byte[]{0, 1, 0}));
46  
47  
48      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
49              FuzzyRowFilter.satisfiesNoUnsafe(false,
50                                       new byte[]{1, 2, 1, 3, 3},
51                                       0, 5,
52                                       new byte[]{1, 2, 0, 3},
53                                       new byte[]{0, 0, 1, 0}));
54  
55      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
56              FuzzyRowFilter.satisfiesNoUnsafe(false,
57                                       new byte[]{1, 1, 1, 3, 0}, // row to check
58                                       0, 5,
59                                       new byte[]{1, 2, 0, 3}, // fuzzy row
60                                       new byte[]{0, 0, 1, 0})); // mask
61  
62      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
63              FuzzyRowFilter.satisfiesNoUnsafe(false,
64                                       new byte[]{1, 1, 1, 3, 0},
65                                       0, 5,
66                                       new byte[]{1, (byte) 245, 0, 3},
67                                       new byte[]{0, 0, 1, 0}));
68  
69      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
70              FuzzyRowFilter.satisfiesNoUnsafe(false,
71                                       new byte[]{1, 2, 1, 0, 1},
72                                       0, 5,
73                                       new byte[]{0, 1, 2},
74                                       new byte[]{1, 0, 0}));
75    }
76  
77    @Test
78    public void testSatisfiesForward() {
79  
80      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
81              FuzzyRowFilter.satisfies(false,
82                                       new byte[]{1, (byte) -128, 1, 0, 1},
83                                       new byte[]{1, 0, 1},
84                                       new byte[]{-1, 0, -1}));
85  
86      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
87              FuzzyRowFilter.satisfies(false,
88                                       new byte[]{1, (byte) -128, 2, 0, 1},
89                                       new byte[]{1, 0, 1},
90                                       new byte[]{-1, 0, -1}));
91  
92  
93      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
94              FuzzyRowFilter.satisfies(false,
95                                       new byte[]{1, 2, 1, 3, 3},
96                                       new byte[]{1, 2, 0, 3},
97                                       new byte[]{-1, -1, 0, -1}));
98  
99      Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
100             FuzzyRowFilter.satisfies(false,
101                                      new byte[]{1, 1, 1, 3, 0}, // row to check
102                                      new byte[]{1, 2, 0, 3}, // fuzzy row
103                                      new byte[]{-1, -1, 0, -1})); // mask
104 
105     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
106             FuzzyRowFilter.satisfies(false,
107                                      new byte[]{1, 1, 1, 3, 0},
108                                      new byte[]{1, (byte) 245, 0, 3},
109                                      new byte[]{-1, -1, 0, -1}));
110 
111     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
112             FuzzyRowFilter.satisfies(false,
113                                      new byte[]{1, 2, 1, 0, 1},
114                                      new byte[]{0, 1, 2},
115                                      new byte[]{0, -1, -1}));
116   }
117 
118   @Test
119   public void testSatisfiesReverse() {
120     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
121       FuzzyRowFilter.satisfies(true,
122         new byte[]{1, (byte) -128, 1, 0, 1},
123         new byte[]{1, 0, 1},
124         new byte[]{-1, 0, -1}));
125 
126     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
127       FuzzyRowFilter.satisfies(true,
128         new byte[]{1, (byte) -128, 2, 0, 1},
129         new byte[]{1, 0, 1},
130         new byte[]{-1, 0, -1}));
131 
132     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
133       FuzzyRowFilter.satisfies(true,
134         new byte[]{2, 3, 1, 1, 1},
135         new byte[]{1, 0, 1},
136         new byte[]{-1, 0, -1}));
137 
138     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
139       FuzzyRowFilter.satisfies(true,
140         new byte[]{1, 2, 1, 3, 3},
141         new byte[]{1, 2, 0, 3},
142         new byte[]{-1, -1, 0, -1}));
143 
144     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
145       FuzzyRowFilter.satisfies(true,
146         new byte[]{1, (byte) 245, 1, 3, 0},
147         new byte[]{1, 1, 0, 3},
148         new byte[]{-1, -1, 0, -1}));
149 
150     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
151       FuzzyRowFilter.satisfies(true,
152         new byte[]{1, 3, 1, 3, 0},
153         new byte[]{1, 2, 0, 3},
154         new byte[]{-1, -1, 0, -1}));
155 
156     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
157       FuzzyRowFilter.satisfies(true,
158         new byte[]{2, 1, 1, 1, 0},
159         new byte[]{1, 2, 0, 3},
160         new byte[]{-1, -1, 0, -1}));
161 
162     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
163       FuzzyRowFilter.satisfies(true,
164         new byte[]{1, 2, 1, 0, 1},
165         new byte[]{0, 1, 2},
166         new byte[]{0, -1, -1}));
167   }
168 
169   @Test
170   public void testSatisfiesNoUnsafeReverse() {
171     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
172       FuzzyRowFilter.satisfiesNoUnsafe(true,
173         new byte[]{1, (byte) -128, 1, 0, 1},
174         0, 5,
175         new byte[]{1, 0, 1},
176         new byte[]{0, 1, 0}));
177 
178     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
179       FuzzyRowFilter.satisfiesNoUnsafe(true,
180         new byte[]{1, (byte) -128, 2, 0, 1},
181         0, 5,
182         new byte[]{1, 0, 1},
183         new byte[]{0, 1, 0}));
184 
185     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
186       FuzzyRowFilter.satisfiesNoUnsafe(true,
187         new byte[]{2, 3, 1, 1, 1},
188         0, 5,
189         new byte[]{1, 0, 1},
190         new byte[]{0, 1, 0}));
191 
192     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.YES,
193       FuzzyRowFilter.satisfiesNoUnsafe(true,
194         new byte[]{1, 2, 1, 3, 3},
195         0, 5,
196         new byte[]{1, 2, 0, 3},
197         new byte[]{0, 0, 1, 0}));
198 
199     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
200       FuzzyRowFilter.satisfiesNoUnsafe(true,
201         new byte[]{1, (byte) 245, 1, 3, 0},
202         0, 5,
203         new byte[]{1, 1, 0, 3},
204         new byte[]{0, 0, 1, 0}));
205 
206     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
207       FuzzyRowFilter.satisfiesNoUnsafe(true,
208         new byte[]{1, 3, 1, 3, 0},
209         0, 5,
210         new byte[]{1, 2, 0, 3},
211         new byte[]{0, 0, 1, 0}));
212 
213     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
214       FuzzyRowFilter.satisfiesNoUnsafe(true,
215         new byte[]{2, 1, 1, 1, 0},
216         0, 5,
217         new byte[]{1, 2, 0, 3},
218         new byte[]{0, 0, 1, 0}));
219 
220     Assert.assertEquals(FuzzyRowFilter.SatisfiesCode.NEXT_EXISTS,
221       FuzzyRowFilter.satisfiesNoUnsafe(true,
222         new byte[]{1, 2, 1, 0, 1},
223         0, 5,
224         new byte[]{0, 1, 2},
225         new byte[]{1, 0, 0}));
226   }  
227   @Test
228   public void testGetNextForFuzzyRuleForward() {
229     assertNext(false,
230             new byte[]{0, 1, 2}, // fuzzy row
231             new byte[]{0, -1, -1}, // mask
232             new byte[]{1, 2, 1, 0, 1}, // current
233             new byte[]{2, 1, 2}); // expected next
234 
235     assertNext(false,
236             new byte[]{0, 1, 2}, // fuzzy row
237             new byte[]{0, -1, -1}, // mask
238             new byte[]{1, 1, 2, 0, 1}, // current
239             new byte[]{1, 1, 2, 0, 2}); // expected next
240 
241     assertNext(false,
242             new byte[]{0, 1, 0, 2, 0}, // fuzzy row
243             new byte[]{0, -1, 0, -1, 0}, // mask
244             new byte[]{1, 0, 2, 0, 1}, // current
245             new byte[]{1, 1, 0, 2}); // expected next
246 
247     assertNext(false,
248             new byte[]{1, 0, 1},
249             new byte[]{-1, 0, -1},
250             new byte[]{1, (byte) 128, 2, 0, 1},
251             new byte[]{1, (byte) 129, 1});
252 
253     assertNext(false,
254             new byte[]{0, 1, 0, 1},
255             new byte[]{0, -1, 0, -1},
256             new byte[]{5, 1, 0, 1},
257             new byte[]{5, 1, 1, 1});
258 
259     assertNext(false,
260             new byte[]{0, 1, 0, 1},
261             new byte[]{0, -1, 0, -1},
262             new byte[]{5, 1, 0, 1, 1},
263             new byte[]{5, 1, 0, 1, 2});
264 
265     assertNext(false,
266             new byte[]{0, 1, 0, 0}, // fuzzy row
267             new byte[]{0, -1, 0, 0}, // mask
268             new byte[]{5, 1, (byte) 255, 1}, // current
269             new byte[]{5, 1, (byte) 255, 2}); // expected next
270 
271     assertNext(false,
272             new byte[]{0, 1, 0, 1}, // fuzzy row
273             new byte[]{0, -1, 0, -1}, // mask
274             new byte[]{5, 1, (byte) 255, 1}, // current
275             new byte[]{6, 1, 0, 1}); // expected next
276 
277     assertNext(false,
278             new byte[]{0, 1, 0, 1}, // fuzzy row
279             new byte[]{0, -1, 0, -1}, // mask
280             new byte[]{5, 1, (byte) 255, 0}, // current
281             new byte[]{5, 1, (byte) 255, 1}); // expected next
282 
283     assertNext(false,
284             new byte[]{5, 1, 1, 0},
285             new byte[]{-1, -1, 0, 0},
286             new byte[]{5, 1, (byte) 255, 1},
287             new byte[]{5, 1, (byte) 255, 2});
288 
289     assertNext(false,
290             new byte[]{1, 1, 1, 1},
291             new byte[]{-1, -1, 0, 0},
292             new byte[]{1, 1, 2, 2},
293             new byte[]{1, 1, 2, 3});
294 
295     assertNext(false,
296             new byte[]{1, 1, 1, 1},
297             new byte[]{-1, -1, 0, 0},
298             new byte[]{1, 1, 3, 2},
299             new byte[]{1, 1, 3, 3});
300 
301     assertNext(false,
302             new byte[]{1, 1, 1, 1},
303             new byte[]{0, 0, 0, 0},
304             new byte[]{1, 1, 2, 3},
305             new byte[]{1, 1, 2, 4});
306 
307     assertNext(false,
308             new byte[]{1, 1, 1, 1},
309             new byte[]{0, 0, 0, 0},
310             new byte[]{1, 1, 3, 2},
311             new byte[]{1, 1, 3, 3});
312 
313     assertNext(false,
314             new byte[]{1, 1, 0, 0},
315             new byte[]{-1, -1, 0, 0},
316             new byte[]{0, 1, 3, 2},
317             new byte[]{1, 1});
318 
319     // No next for this one
320     Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
321             new byte[]{2, 3, 1, 1, 1}, // row to check
322             new byte[]{1, 0, 1}, // fuzzy row
323             new byte[]{-1, 0, -1})); // mask
324     Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
325             new byte[]{1, (byte) 245, 1, 3, 0},
326             new byte[]{1, 1, 0, 3},
327             new byte[]{-1, -1, 0, -1}));
328     Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
329             new byte[]{1, 3, 1, 3, 0},
330             new byte[]{1, 2, 0, 3},
331             new byte[]{-1, -1, 0, -1}));
332     Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(
333             new byte[]{2, 1, 1, 1, 0},
334             new byte[]{1, 2, 0, 3},
335             new byte[]{-1, -1, 0, -1}));
336   }
337 
338   @Test
339   public void testGetNextForFuzzyRuleReverse() {
340     assertNext(true,
341       new byte[]{0, 1, 2}, // fuzzy row
342       new byte[]{0, -1, -1}, // mask
343       new byte[]{1, 2, 1, 0, 1}, // current
344       // TODO: should be {1, 1, 3} ?
345       new byte[]{1, 1, 2, (byte) 0xFF, (byte) 0xFF}); // expected next
346 
347     assertNext(true,
348       new byte[]{0, 1, 0, 2, 0}, // fuzzy row
349       new byte[]{0, -1, 0, -1, 0}, // mask
350       new byte[]{1, 2, 1, 3, 1}, // current
351       // TODO: should be {1, 1, 1, 3} ?
352       new byte[]{1, 1, 0, 2, 0}); // expected next
353 
354     assertNext(true,
355       new byte[]{1, 0, 1},
356       new byte[]{-1, 0, -1},
357       new byte[]{1, (byte) 128, 2, 0, 1},
358       // TODO: should be {1, (byte) 128, 2} ?
359       new byte[]{1, (byte) 128, 1, (byte) 0xFF, (byte) 0xFF});
360 
361     assertNext(true,
362       new byte[]{0, 1, 0, 1},
363       new byte[]{0, -1, 0, -1},
364       new byte[]{5, 1, 0, 2, 1},
365       // TODO: should be {5, 1, 0, 2} ?
366       new byte[]{5, 1, 0, 1, (byte) 0xFF});
367 
368     assertNext(true,
369       new byte[]{0, 1, 0, 0}, // fuzzy row
370       new byte[]{0, -1, 0, 0}, // mask
371       new byte[]{5, 1, (byte) 255, 1}, // current
372       new byte[]{5, 1, (byte) 255, 0}); // expected next
373 
374     assertNext(true,
375       new byte[]{0, 1, 0, 1}, // fuzzy row
376       new byte[]{0, -1, 0, -1}, // mask
377       new byte[]{5, 1, 0, 1}, // current
378       new byte[]{4, 1, (byte) 255, 1}); // expected next
379 
380     assertNext(true,
381       new byte[]{0, 1, 0, 1}, // fuzzy row
382       new byte[]{0, -1, 0, -1}, // mask
383       new byte[]{5, 1, (byte) 255, 0}, // current
384       new byte[]{5, 1, (byte) 254, 1}); // expected next
385 
386     assertNext(true,
387       new byte[]{1, 1, 0, 0},
388       new byte[]{-1, -1, 0, 0},
389       new byte[]{2, 1, 3, 2},
390       // TODO: should be {1, 0} ?
391       new byte[]{1, 1, 0, 0});
392 
393     assertNext(true,
394       new byte[]{1, 0, 1}, // fuzzy row
395       new byte[]{-1, 0, -1}, // mask
396       new byte[]{2, 3, 1, 1, 1}, // row to check
397       // TODO: should be {1, (byte) 0xFF, 2} ?
398       new byte[]{1, 0, 1, (byte) 0xFF, (byte) 0xFF});
399 
400     assertNext(true,
401       new byte[]{1, 1, 0, 3},
402       new byte[]{-1, -1, 0, -1},
403       new byte[]{1, (byte) 245, 1, 3, 0},
404       // TODO: should be {1, 1, (byte) 255, 4} ?
405       new byte[]{1, 1, 0, 3, (byte) 0xFF});
406 
407     assertNext(true,
408       new byte[]{1, 2, 0, 3},
409       new byte[]{-1, -1, 0, -1},
410       new byte[]{1, 3, 1, 3, 0},
411       // TODO: should be 1, 2, (byte) 255, 4 ?
412       new byte[]{1, 2, 0, 3, (byte) 0xFF});
413 
414     assertNext(true,
415       new byte[]{1, 2, 0, 3},
416       new byte[]{-1, -1, 0, -1},
417       new byte[]{2, 1, 1, 1, 0},
418       // TODO: should be {1, 2, (byte) 255, 4} ?
419       new byte[]{1, 2, 0, 3, (byte) 0xFF});
420 
421     assertNext(true,
422       // TODO: should be null?
423       new byte[]{1, 0, 1},
424       new byte[]{-1, 0, -1},
425       new byte[]{1, (byte) 128, 2},
426       new byte[]{1, (byte) 128, 1});
427 
428     assertNext(true,
429       // TODO: should be null?
430       new byte[]{0, 1, 0, 1},
431       new byte[]{0, -1, 0, -1},
432       new byte[]{5, 1, 0, 2},
433       new byte[]{5, 1, 0, 1});
434 
435     assertNext(true,
436       // TODO: should be null?
437       new byte[]{5, 1, 1, 0},
438       new byte[]{-1, -1, 0, 0},
439       new byte[]{5, 1, (byte) 0xFF, 1},
440       new byte[]{5, 1, (byte) 0xFF, 0});
441 
442     assertNext(true,
443       // TODO: should be null?
444       new byte[]{1, 1, 1, 1},
445       new byte[]{-1, -1, 0, 0},
446       new byte[]{1, 1, 2, 2},
447       new byte[]{1, 1, 2, 1});
448 
449     assertNext(true,
450       // TODO: should be null?
451       new byte[]{1, 1, 1, 1},
452       new byte[]{0, 0, 0, 0},
453       new byte[]{1, 1, 2, 3},
454       new byte[]{1, 1, 2, 2});
455 
456     Assert.assertNull(FuzzyRowFilter.getNextForFuzzyRule(true,
457       new byte[]{1, 1, 1, 3, 0},
458       new byte[]{1, 2, 0, 3},
459       new byte[]{-1, -1, 0, -1}));
460   }
461 
462   private static void assertNext(boolean reverse, byte[] fuzzyRow, byte[] mask, byte[] current,
463       byte[] expected) {
464     KeyValue kv = KeyValueUtil.createFirstOnRow(current);
465     byte[] nextForFuzzyRule = FuzzyRowFilter.getNextForFuzzyRule(reverse, kv.getRowArray(),
466         kv.getRowOffset(), kv.getRowLength(), fuzzyRow, mask);
467     Assert.assertEquals(Bytes.toStringBinary(expected), Bytes.toStringBinary(nextForFuzzyRule));
468   }
469 }