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 java.util.ArrayList; 021import java.util.Arrays; 022import java.util.Comparator; 023import java.util.List; 024import java.util.Objects; 025import java.util.PriorityQueue; 026 027import org.apache.hadoop.hbase.Cell; 028import org.apache.hadoop.hbase.CellComparator; 029import org.apache.hadoop.hbase.PrivateCellUtil; 030import org.apache.yetus.audience.InterfaceAudience; 031import org.apache.hadoop.hbase.exceptions.DeserializationException; 032import org.apache.hbase.thirdparty.com.google.protobuf.InvalidProtocolBufferException; 033import org.apache.hbase.thirdparty.com.google.protobuf.UnsafeByteOperations; 034import org.apache.hadoop.hbase.shaded.protobuf.generated.FilterProtos; 035import org.apache.hadoop.hbase.shaded.protobuf.generated.HBaseProtos.BytesBytesPair; 036import org.apache.hadoop.hbase.util.Bytes; 037import org.apache.hadoop.hbase.util.Pair; 038import org.apache.hadoop.hbase.util.UnsafeAvailChecker; 039 040/** 041 * This is optimized version of a standard FuzzyRowFilter Filters data based on fuzzy row key. 042 * Performs fast-forwards during scanning. It takes pairs (row key, fuzzy info) to match row keys. 043 * Where fuzzy info is a byte array with 0 or 1 as its values: 044 * <ul> 045 * <li>0 - means that this byte in provided row key is fixed, i.e. row key's byte at same position 046 * must match</li> 047 * <li>1 - means that this byte in provided row key is NOT fixed, i.e. row key's byte at this 048 * position can be different from the one in provided row key</li> 049 * </ul> 050 * Example: Let's assume row key format is userId_actionId_year_month. Length of userId is fixed and 051 * is 4, length of actionId is 2 and year and month are 4 and 2 bytes long respectively. Let's 052 * assume that we need to fetch all users that performed certain action (encoded as "99") in Jan of 053 * any year. Then the pair (row key, fuzzy info) would be the following: row key = "????_99_????_01" 054 * (one can use any value instead of "?") fuzzy info = 055 * "\x01\x01\x01\x01\x00\x00\x00\x00\x01\x01\x01\x01\x00\x00\x00" I.e. fuzzy info tells the matching 056 * mask is "????_99_????_01", where at ? can be any value. 057 */ 058@InterfaceAudience.Public 059public class FuzzyRowFilter extends FilterBase { 060 private static final boolean UNSAFE_UNALIGNED = UnsafeAvailChecker.unaligned(); 061 private List<Pair<byte[], byte[]>> fuzzyKeysData; 062 private boolean done = false; 063 064 /** 065 * The index of a last successfully found matching fuzzy string (in fuzzyKeysData). We will start 066 * matching next KV with this one. If they do not match then we will return back to the one-by-one 067 * iteration over fuzzyKeysData. 068 */ 069 private int lastFoundIndex = -1; 070 071 /** 072 * Row tracker (keeps all next rows after SEEK_NEXT_USING_HINT was returned) 073 */ 074 private RowTracker tracker; 075 076 public FuzzyRowFilter(List<Pair<byte[], byte[]>> fuzzyKeysData) { 077 List<Pair<byte[], byte[]>> fuzzyKeyDataCopy = new ArrayList<>(fuzzyKeysData.size()); 078 079 for (Pair<byte[], byte[]> aFuzzyKeysData : fuzzyKeysData) { 080 if (aFuzzyKeysData.getFirst().length != aFuzzyKeysData.getSecond().length) { 081 Pair<String, String> readable = 082 new Pair<>(Bytes.toStringBinary(aFuzzyKeysData.getFirst()), Bytes.toStringBinary(aFuzzyKeysData.getSecond())); 083 throw new IllegalArgumentException("Fuzzy pair lengths do not match: " + readable); 084 } 085 086 Pair<byte[], byte[]> p = new Pair<>(); 087 // create a copy of pair bytes so that they are not modified by the filter. 088 p.setFirst(Arrays.copyOf(aFuzzyKeysData.getFirst(), aFuzzyKeysData.getFirst().length)); 089 p.setSecond(Arrays.copyOf(aFuzzyKeysData.getSecond(), aFuzzyKeysData.getSecond().length)); 090 091 // update mask ( 0 -> -1 (0xff), 1 -> 2) 092 p.setSecond(preprocessMask(p.getSecond())); 093 preprocessSearchKey(p); 094 095 fuzzyKeyDataCopy.add(p); 096 } 097 this.fuzzyKeysData = fuzzyKeyDataCopy; 098 this.tracker = new RowTracker(); 099 } 100 101 private void preprocessSearchKey(Pair<byte[], byte[]> p) { 102 if (!UNSAFE_UNALIGNED) { 103 // do nothing 104 return; 105 } 106 byte[] key = p.getFirst(); 107 byte[] mask = p.getSecond(); 108 for (int i = 0; i < mask.length; i++) { 109 // set non-fixed part of a search key to 0. 110 if (mask[i] == 2) { 111 key[i] = 0; 112 } 113 } 114 } 115 116 /** 117 * We need to preprocess mask array, as since we treat 2's as unfixed positions and -1 (0xff) as 118 * fixed positions 119 * @param mask 120 * @return mask array 121 */ 122 private byte[] preprocessMask(byte[] mask) { 123 if (!UNSAFE_UNALIGNED) { 124 // do nothing 125 return mask; 126 } 127 if (isPreprocessedMask(mask)) return mask; 128 for (int i = 0; i < mask.length; i++) { 129 if (mask[i] == 0) { 130 mask[i] = -1; // 0 -> -1 131 } else if (mask[i] == 1) { 132 mask[i] = 2;// 1 -> 2 133 } 134 } 135 return mask; 136 } 137 138 private boolean isPreprocessedMask(byte[] mask) { 139 for (int i = 0; i < mask.length; i++) { 140 if (mask[i] != -1 && mask[i] != 2) { 141 return false; 142 } 143 } 144 return true; 145 } 146 147 @Deprecated 148 @Override 149 public ReturnCode filterKeyValue(final Cell c) { 150 return filterCell(c); 151 } 152 153 @Override 154 public ReturnCode filterCell(final Cell c) { 155 final int startIndex = lastFoundIndex >= 0 ? lastFoundIndex : 0; 156 final int size = fuzzyKeysData.size(); 157 for (int i = startIndex; i < size + startIndex; i++) { 158 final int index = i % size; 159 Pair<byte[], byte[]> fuzzyData = fuzzyKeysData.get(index); 160 // This shift is idempotent - always end up with 0 and -1 as mask values. 161 for (int j = 0; j < fuzzyData.getSecond().length; j++) { 162 fuzzyData.getSecond()[j] >>= 2; 163 } 164 SatisfiesCode satisfiesCode = 165 satisfies(isReversed(), c.getRowArray(), c.getRowOffset(), c.getRowLength(), 166 fuzzyData.getFirst(), fuzzyData.getSecond()); 167 if (satisfiesCode == SatisfiesCode.YES) { 168 lastFoundIndex = index; 169 return ReturnCode.INCLUDE; 170 } 171 } 172 // NOT FOUND -> seek next using hint 173 lastFoundIndex = -1; 174 175 return ReturnCode.SEEK_NEXT_USING_HINT; 176 177 } 178 179 @Override 180 public Cell getNextCellHint(Cell currentCell) { 181 boolean result = tracker.updateTracker(currentCell); 182 if (result == false) { 183 done = true; 184 return null; 185 } 186 byte[] nextRowKey = tracker.nextRow(); 187 return PrivateCellUtil.createFirstOnRow(nextRowKey, 0, (short) nextRowKey.length); 188 } 189 190 /** 191 * If we have multiple fuzzy keys, row tracker should improve overall performance. It calculates 192 * all next rows (one per every fuzzy key) and put them (the fuzzy key is bundled) into a priority 193 * queue so that the smallest row key always appears at queue head, which helps to decide the 194 * "Next Cell Hint". As scanning going on, the number of candidate rows in the RowTracker will 195 * remain the size of fuzzy keys until some of the fuzzy keys won't possibly have matches any 196 * more. 197 */ 198 private class RowTracker { 199 private final PriorityQueue<Pair<byte[], Pair<byte[], byte[]>>> nextRows; 200 private boolean initialized = false; 201 202 RowTracker() { 203 nextRows = new PriorityQueue<>(fuzzyKeysData.size(), 204 new Comparator<Pair<byte[], Pair<byte[], byte[]>>>() { 205 @Override 206 public int compare(Pair<byte[], Pair<byte[], byte[]>> o1, 207 Pair<byte[], Pair<byte[], byte[]>> o2) { 208 return isReversed()? Bytes.compareTo(o2.getFirst(), o1.getFirst()): 209 Bytes.compareTo(o1.getFirst(), o2.getFirst()); 210 } 211 }); 212 } 213 214 byte[] nextRow() { 215 if (nextRows.isEmpty()) { 216 throw new IllegalStateException( 217 "NextRows should not be empty, make sure to call nextRow() after updateTracker() return true"); 218 } else { 219 return nextRows.peek().getFirst(); 220 } 221 } 222 223 boolean updateTracker(Cell currentCell) { 224 if (!initialized) { 225 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) { 226 updateWith(currentCell, fuzzyData); 227 } 228 initialized = true; 229 } else { 230 while (!nextRows.isEmpty() && !lessThan(currentCell, nextRows.peek().getFirst())) { 231 Pair<byte[], Pair<byte[], byte[]>> head = nextRows.poll(); 232 Pair<byte[], byte[]> fuzzyData = head.getSecond(); 233 updateWith(currentCell, fuzzyData); 234 } 235 } 236 return !nextRows.isEmpty(); 237 } 238 239 boolean lessThan(Cell currentCell, byte[] nextRowKey) { 240 int compareResult = CellComparator.getInstance().compareRows(currentCell, nextRowKey, 0, nextRowKey.length); 241 return (!isReversed() && compareResult < 0) || (isReversed() && compareResult > 0); 242 } 243 244 void updateWith(Cell currentCell, Pair<byte[], byte[]> fuzzyData) { 245 byte[] nextRowKeyCandidate = 246 getNextForFuzzyRule(isReversed(), currentCell.getRowArray(), currentCell.getRowOffset(), 247 currentCell.getRowLength(), fuzzyData.getFirst(), fuzzyData.getSecond()); 248 if (nextRowKeyCandidate != null) { 249 nextRows.add(new Pair<>(nextRowKeyCandidate, fuzzyData)); 250 } 251 } 252 253 } 254 255 @Override 256 public boolean filterAllRemaining() { 257 return done; 258 } 259 260 /** 261 * @return The filter serialized using pb 262 */ 263 @Override 264 public byte[] toByteArray() { 265 FilterProtos.FuzzyRowFilter.Builder builder = FilterProtos.FuzzyRowFilter.newBuilder(); 266 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) { 267 BytesBytesPair.Builder bbpBuilder = BytesBytesPair.newBuilder(); 268 bbpBuilder.setFirst(UnsafeByteOperations.unsafeWrap(fuzzyData.getFirst())); 269 bbpBuilder.setSecond(UnsafeByteOperations.unsafeWrap(fuzzyData.getSecond())); 270 builder.addFuzzyKeysData(bbpBuilder); 271 } 272 return builder.build().toByteArray(); 273 } 274 275 /** 276 * @param pbBytes A pb serialized {@link FuzzyRowFilter} instance 277 * @return An instance of {@link FuzzyRowFilter} made from <code>bytes</code> 278 * @throws DeserializationException 279 * @see #toByteArray 280 */ 281 public static FuzzyRowFilter parseFrom(final byte[] pbBytes) throws DeserializationException { 282 FilterProtos.FuzzyRowFilter proto; 283 try { 284 proto = FilterProtos.FuzzyRowFilter.parseFrom(pbBytes); 285 } catch (InvalidProtocolBufferException e) { 286 throw new DeserializationException(e); 287 } 288 int count = proto.getFuzzyKeysDataCount(); 289 ArrayList<Pair<byte[], byte[]>> fuzzyKeysData = new ArrayList<>(count); 290 for (int i = 0; i < count; ++i) { 291 BytesBytesPair current = proto.getFuzzyKeysData(i); 292 byte[] keyBytes = current.getFirst().toByteArray(); 293 byte[] keyMeta = current.getSecond().toByteArray(); 294 fuzzyKeysData.add(new Pair<>(keyBytes, keyMeta)); 295 } 296 return new FuzzyRowFilter(fuzzyKeysData); 297 } 298 299 @Override 300 public String toString() { 301 final StringBuilder sb = new StringBuilder(); 302 sb.append("FuzzyRowFilter"); 303 sb.append("{fuzzyKeysData="); 304 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) { 305 sb.append('{').append(Bytes.toStringBinary(fuzzyData.getFirst())).append(":"); 306 sb.append(Bytes.toStringBinary(fuzzyData.getSecond())).append('}'); 307 } 308 sb.append("}, "); 309 return sb.toString(); 310 } 311 312 // Utility methods 313 314 static enum SatisfiesCode { 315 /** row satisfies fuzzy rule */ 316 YES, 317 /** row doesn't satisfy fuzzy rule, but there's possible greater row that does */ 318 NEXT_EXISTS, 319 /** row doesn't satisfy fuzzy rule and there's no greater row that does */ 320 NO_NEXT 321 } 322 323 @InterfaceAudience.Private 324 static SatisfiesCode satisfies(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 325 return satisfies(false, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 326 } 327 328 @InterfaceAudience.Private 329 static SatisfiesCode satisfies(boolean reverse, byte[] row, byte[] fuzzyKeyBytes, 330 byte[] fuzzyKeyMeta) { 331 return satisfies(reverse, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 332 } 333 334 static SatisfiesCode satisfies(boolean reverse, byte[] row, int offset, int length, 335 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 336 337 if (!UNSAFE_UNALIGNED) { 338 return satisfiesNoUnsafe(reverse, row, offset, length, fuzzyKeyBytes, fuzzyKeyMeta); 339 } 340 341 if (row == null) { 342 // do nothing, let scan to proceed 343 return SatisfiesCode.YES; 344 } 345 length = Math.min(length, fuzzyKeyBytes.length); 346 int numWords = length / Bytes.SIZEOF_LONG; 347 348 int j = numWords << 3; // numWords * SIZEOF_LONG; 349 350 for (int i = 0; i < j; i += Bytes.SIZEOF_LONG) { 351 long fuzzyBytes = Bytes.toLong(fuzzyKeyBytes, i); 352 long fuzzyMeta = Bytes.toLong(fuzzyKeyMeta, i); 353 long rowValue = Bytes.toLong(row, offset + i); 354 if ((rowValue & fuzzyMeta) != (fuzzyBytes)) { 355 // We always return NEXT_EXISTS 356 return SatisfiesCode.NEXT_EXISTS; 357 } 358 } 359 360 int off = j; 361 362 if (length - off >= Bytes.SIZEOF_INT) { 363 int fuzzyBytes = Bytes.toInt(fuzzyKeyBytes, off); 364 int fuzzyMeta = Bytes.toInt(fuzzyKeyMeta, off); 365 int rowValue = Bytes.toInt(row, offset + off); 366 if ((rowValue & fuzzyMeta) != (fuzzyBytes)) { 367 // We always return NEXT_EXISTS 368 return SatisfiesCode.NEXT_EXISTS; 369 } 370 off += Bytes.SIZEOF_INT; 371 } 372 373 if (length - off >= Bytes.SIZEOF_SHORT) { 374 short fuzzyBytes = Bytes.toShort(fuzzyKeyBytes, off); 375 short fuzzyMeta = Bytes.toShort(fuzzyKeyMeta, off); 376 short rowValue = Bytes.toShort(row, offset + off); 377 if ((rowValue & fuzzyMeta) != (fuzzyBytes)) { 378 // We always return NEXT_EXISTS 379 // even if it does not (in this case getNextForFuzzyRule 380 // will return null) 381 return SatisfiesCode.NEXT_EXISTS; 382 } 383 off += Bytes.SIZEOF_SHORT; 384 } 385 386 if (length - off >= Bytes.SIZEOF_BYTE) { 387 int fuzzyBytes = fuzzyKeyBytes[off] & 0xff; 388 int fuzzyMeta = fuzzyKeyMeta[off] & 0xff; 389 int rowValue = row[offset + off] & 0xff; 390 if ((rowValue & fuzzyMeta) != (fuzzyBytes)) { 391 // We always return NEXT_EXISTS 392 return SatisfiesCode.NEXT_EXISTS; 393 } 394 } 395 return SatisfiesCode.YES; 396 } 397 398 static SatisfiesCode satisfiesNoUnsafe(boolean reverse, byte[] row, int offset, int length, 399 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 400 if (row == null) { 401 // do nothing, let scan to proceed 402 return SatisfiesCode.YES; 403 } 404 405 Order order = Order.orderFor(reverse); 406 boolean nextRowKeyCandidateExists = false; 407 408 for (int i = 0; i < fuzzyKeyMeta.length && i < length; i++) { 409 // First, checking if this position is fixed and not equals the given one 410 boolean byteAtPositionFixed = fuzzyKeyMeta[i] == 0; 411 boolean fixedByteIncorrect = byteAtPositionFixed && fuzzyKeyBytes[i] != row[i + offset]; 412 if (fixedByteIncorrect) { 413 // in this case there's another row that satisfies fuzzy rule and bigger than this row 414 if (nextRowKeyCandidateExists) { 415 return SatisfiesCode.NEXT_EXISTS; 416 } 417 418 // If this row byte is less than fixed then there's a byte array bigger than 419 // this row and which satisfies the fuzzy rule. Otherwise there's no such byte array: 420 // this row is simply bigger than any byte array that satisfies the fuzzy rule 421 boolean rowByteLessThanFixed = (row[i + offset] & 0xFF) < (fuzzyKeyBytes[i] & 0xFF); 422 if (rowByteLessThanFixed && !reverse) { 423 return SatisfiesCode.NEXT_EXISTS; 424 } else if (!rowByteLessThanFixed && reverse) { 425 return SatisfiesCode.NEXT_EXISTS; 426 } else { 427 return SatisfiesCode.NO_NEXT; 428 } 429 } 430 431 // Second, checking if this position is not fixed and byte value is not the biggest. In this 432 // case there's a byte array bigger than this row and which satisfies the fuzzy rule. To get 433 // bigger byte array that satisfies the rule we need to just increase this byte 434 // (see the code of getNextForFuzzyRule below) by one. 435 // Note: if non-fixed byte is already at biggest value, this doesn't allow us to say there's 436 // bigger one that satisfies the rule as it can't be increased. 437 if (fuzzyKeyMeta[i] == 1 && !order.isMax(fuzzyKeyBytes[i])) { 438 nextRowKeyCandidateExists = true; 439 } 440 } 441 return SatisfiesCode.YES; 442 } 443 444 @InterfaceAudience.Private 445 static byte[] getNextForFuzzyRule(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 446 return getNextForFuzzyRule(false, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 447 } 448 449 @InterfaceAudience.Private 450 static byte[] getNextForFuzzyRule(boolean reverse, byte[] row, byte[] fuzzyKeyBytes, 451 byte[] fuzzyKeyMeta) { 452 return getNextForFuzzyRule(reverse, row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta); 453 } 454 455 /** Abstracts directional comparisons based on scan direction. */ 456 private enum Order { 457 ASC { 458 @Override 459 public boolean lt(int lhs, int rhs) { 460 return lhs < rhs; 461 } 462 463 @Override 464 public boolean gt(int lhs, int rhs) { 465 return lhs > rhs; 466 } 467 468 @Override 469 public byte inc(byte val) { 470 // TODO: what about over/underflow? 471 return (byte) (val + 1); 472 } 473 474 @Override 475 public boolean isMax(byte val) { 476 return val == (byte) 0xff; 477 } 478 479 @Override 480 public byte min() { 481 return 0; 482 } 483 }, 484 DESC { 485 @Override 486 public boolean lt(int lhs, int rhs) { 487 return lhs > rhs; 488 } 489 490 @Override 491 public boolean gt(int lhs, int rhs) { 492 return lhs < rhs; 493 } 494 495 @Override 496 public byte inc(byte val) { 497 // TODO: what about over/underflow? 498 return (byte) (val - 1); 499 } 500 501 @Override 502 public boolean isMax(byte val) { 503 return val == 0; 504 } 505 506 @Override 507 public byte min() { 508 return (byte) 0xFF; 509 } 510 }; 511 512 public static Order orderFor(boolean reverse) { 513 return reverse ? DESC : ASC; 514 } 515 516 /** Returns true when {@code lhs < rhs}. */ 517 public abstract boolean lt(int lhs, int rhs); 518 519 /** Returns true when {@code lhs > rhs}. */ 520 public abstract boolean gt(int lhs, int rhs); 521 522 /** Returns {@code val} incremented by 1. */ 523 public abstract byte inc(byte val); 524 525 /** Return true when {@code val} is the maximum value */ 526 public abstract boolean isMax(byte val); 527 528 /** Return the minimum value according to this ordering scheme. */ 529 public abstract byte min(); 530 } 531 532 /** 533 * @return greater byte array than given (row) which satisfies the fuzzy rule if it exists, null 534 * otherwise 535 */ 536 @InterfaceAudience.Private 537 static byte[] getNextForFuzzyRule(boolean reverse, byte[] row, int offset, int length, 538 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) { 539 // To find out the next "smallest" byte array that satisfies fuzzy rule and "greater" than 540 // the given one we do the following: 541 // 1. setting values on all "fixed" positions to the values from fuzzyKeyBytes 542 // 2. if during the first step given row did not increase, then we increase the value at 543 // the first "non-fixed" position (where it is not maximum already) 544 545 // It is easier to perform this by using fuzzyKeyBytes copy and setting "non-fixed" position 546 // values than otherwise. 547 byte[] result = 548 Arrays.copyOf(fuzzyKeyBytes, length > fuzzyKeyBytes.length ? length : fuzzyKeyBytes.length); 549 if (reverse && length > fuzzyKeyBytes.length) { 550 // we need trailing 0xff's instead of trailing 0x00's 551 for (int i = fuzzyKeyBytes.length; i < result.length; i++) { 552 result[i] = (byte) 0xFF; 553 } 554 } 555 int toInc = -1; 556 final Order order = Order.orderFor(reverse); 557 558 boolean increased = false; 559 for (int i = 0; i < result.length; i++) { 560 if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 0 /* non-fixed */) { 561 result[i] = row[offset + i]; 562 if (!order.isMax(row[offset + i])) { 563 // this is "non-fixed" position and is not at max value, hence we can increase it 564 toInc = i; 565 } 566 } else if (i < fuzzyKeyMeta.length && fuzzyKeyMeta[i] == -1 /* fixed */) { 567 if (order.lt((row[i + offset] & 0xFF), (fuzzyKeyBytes[i] & 0xFF))) { 568 // if setting value for any fixed position increased the original array, 569 // we are OK 570 increased = true; 571 break; 572 } 573 574 if (order.gt((row[i + offset] & 0xFF), (fuzzyKeyBytes[i] & 0xFF))) { 575 // if setting value for any fixed position makes array "smaller", then just stop: 576 // in case we found some non-fixed position to increase we will do it, otherwise 577 // there's no "next" row key that satisfies fuzzy rule and "greater" than given row 578 break; 579 } 580 } 581 } 582 583 if (!increased) { 584 if (toInc < 0) { 585 return null; 586 } 587 result[toInc] = order.inc(result[toInc]); 588 589 // Setting all "non-fixed" positions to zeroes to the right of the one we increased so 590 // that found "next" row key is the smallest possible 591 for (int i = toInc + 1; i < result.length; i++) { 592 if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 0 /* non-fixed */) { 593 result[i] = order.min(); 594 } 595 } 596 } 597 598 return reverse? result: trimTrailingZeroes(result, fuzzyKeyMeta, toInc); 599 } 600 601 /** 602 * For forward scanner, next cell hint should not contain any trailing zeroes 603 * unless they are part of fuzzyKeyMeta 604 * hint = '\x01\x01\x01\x00\x00' 605 * will skip valid row '\x01\x01\x01' 606 * 607 * @param result 608 * @param fuzzyKeyMeta 609 * @param toInc - position of incremented byte 610 * @return trimmed version of result 611 */ 612 613 private static byte[] trimTrailingZeroes(byte[] result, byte[] fuzzyKeyMeta, int toInc) { 614 int off = fuzzyKeyMeta.length >= result.length? result.length -1: 615 fuzzyKeyMeta.length -1; 616 for( ; off >= 0; off--){ 617 if(fuzzyKeyMeta[off] != 0) break; 618 } 619 if (off < toInc) off = toInc; 620 byte[] retValue = new byte[off+1]; 621 System.arraycopy(result, 0, retValue, 0, retValue.length); 622 return retValue; 623 } 624 625 /** 626 * @return true if and only if the fields of the filter that are serialized are equal to the 627 * corresponding fields in other. Used for testing. 628 */ 629 @Override 630 boolean areSerializedFieldsEqual(Filter o) { 631 if (o == this) return true; 632 if (!(o instanceof FuzzyRowFilter)) return false; 633 634 FuzzyRowFilter other = (FuzzyRowFilter) o; 635 if (this.fuzzyKeysData.size() != other.fuzzyKeysData.size()) return false; 636 for (int i = 0; i < fuzzyKeysData.size(); ++i) { 637 Pair<byte[], byte[]> thisData = this.fuzzyKeysData.get(i); 638 Pair<byte[], byte[]> otherData = other.fuzzyKeysData.get(i); 639 if (!(Bytes.equals(thisData.getFirst(), otherData.getFirst()) && Bytes.equals( 640 thisData.getSecond(), otherData.getSecond()))) { 641 return false; 642 } 643 } 644 return true; 645 } 646 647 @Override 648 public boolean equals(Object obj) { 649 return obj instanceof Filter && areSerializedFieldsEqual((Filter) obj); 650 } 651 652 @Override 653 public int hashCode() { 654 return Objects.hash(this.fuzzyKeysData); 655 } 656}