1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.hadoop.hbase.regionserver;
21
22 import java.io.IOException;
23 import java.util.NavigableSet;
24
25 import org.apache.hadoop.hbase.KeyValue.Type;
26 import org.apache.hadoop.hbase.classification.InterfaceAudience;
27 import org.apache.hadoop.hbase.Cell;
28 import org.apache.hadoop.hbase.CellUtil;
29 import org.apache.hadoop.hbase.HConstants;
30 import org.apache.hadoop.hbase.KeepDeletedCells;
31 import org.apache.hadoop.hbase.KeyValue;
32 import org.apache.hadoop.hbase.KeyValueUtil;
33 import org.apache.hadoop.hbase.client.Scan;
34 import org.apache.hadoop.hbase.filter.Filter;
35 import org.apache.hadoop.hbase.filter.Filter.ReturnCode;
36 import org.apache.hadoop.hbase.io.TimeRange;
37 import org.apache.hadoop.hbase.regionserver.DeleteTracker.DeleteResult;
38 import org.apache.hadoop.hbase.util.Bytes;
39 import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
40
41 import com.google.common.base.Preconditions;
42
43
44
45
46 @InterfaceAudience.Private
47 public class ScanQueryMatcher {
48
49
50 private boolean stickyNextRow;
51 private final byte[] stopRow;
52
53 private final TimeRange tr;
54
55 private final Filter filter;
56
57
58 private final DeleteTracker deletes;
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74 private boolean retainDeletesInOutput;
75
76
77 private final KeepDeletedCells keepDeletedCells;
78
79 private final boolean seePastDeleteMarkers;
80
81
82
83 private final ColumnTracker columns;
84
85
86 private final Cell startKey;
87
88
89 private final KeyValue.KVComparator rowComparator;
90
91
92
93 byte [] row;
94 int rowOffset;
95 short rowLength;
96
97
98
99
100
101
102
103 private final long earliestPutTs;
104 private final long ttl;
105
106
107 private final long oldestUnexpiredTS;
108 private final long now;
109
110
111 protected long maxReadPointToTrackVersions;
112
113 private byte[] dropDeletesFromRow = null, dropDeletesToRow = null;
114
115
116
117
118
119
120
121 private boolean hasNullColumn = true;
122
123 private RegionCoprocessorHost regionCoprocessorHost= null;
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142 private final long timeToPurgeDeletes;
143
144 private final boolean isUserScan;
145
146 private final boolean isReversed;
147
148
149
150
151
152
153
154
155
156
157
158
159
160 public ScanQueryMatcher(Scan scan, ScanInfo scanInfo, NavigableSet<byte[]> columns,
161 ScanType scanType, long readPointToUse, long earliestPutTs, long oldestUnexpiredTS,
162 long now, RegionCoprocessorHost regionCoprocessorHost) throws IOException {
163 this.tr = scan.getTimeRange();
164 this.rowComparator = scanInfo.getComparator();
165 this.regionCoprocessorHost = regionCoprocessorHost;
166 this.deletes = instantiateDeleteTracker();
167 this.stopRow = scan.getStopRow();
168 this.startKey = KeyValueUtil.createFirstDeleteFamilyOnRow(scan.getStartRow(),
169 scanInfo.getFamily());
170 this.filter = scan.getFilter();
171 this.earliestPutTs = earliestPutTs;
172 this.oldestUnexpiredTS = oldestUnexpiredTS;
173 this.now = now;
174
175 this.maxReadPointToTrackVersions = readPointToUse;
176 this.timeToPurgeDeletes = scanInfo.getTimeToPurgeDeletes();
177 this.ttl = oldestUnexpiredTS;
178
179
180 this.isUserScan = scanType == ScanType.USER_SCAN;
181
182 this.keepDeletedCells = scan.isRaw() ? KeepDeletedCells.TRUE :
183 isUserScan ? KeepDeletedCells.FALSE : scanInfo.getKeepDeletedCells();
184
185 this.retainDeletesInOutput = scanType == ScanType.COMPACT_RETAIN_DELETES || scan.isRaw();
186
187 this.seePastDeleteMarkers =
188 scanInfo.getKeepDeletedCells() != KeepDeletedCells.FALSE && isUserScan;
189
190 int maxVersions =
191 scan.isRaw() ? scan.getMaxVersions() : Math.min(scan.getMaxVersions(),
192 scanInfo.getMaxVersions());
193
194
195 if (columns == null || columns.size() == 0) {
196
197 hasNullColumn = true;
198
199
200 this.columns = new ScanWildcardColumnTracker(
201 scanInfo.getMinVersions(), maxVersions, oldestUnexpiredTS);
202 } else {
203
204 hasNullColumn = (columns.first().length == 0);
205
206
207
208 this.columns = new ExplicitColumnTracker(columns, scanInfo.getMinVersions(), maxVersions,
209 oldestUnexpiredTS);
210 }
211 this.isReversed = scan.isReversed();
212 }
213
214 private DeleteTracker instantiateDeleteTracker() throws IOException {
215 DeleteTracker tracker = new ScanDeleteTracker();
216 if (regionCoprocessorHost != null) {
217 tracker = regionCoprocessorHost.postInstantiateDeleteTracker(tracker);
218 }
219 return tracker;
220 }
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235 public ScanQueryMatcher(Scan scan, ScanInfo scanInfo, NavigableSet<byte[]> columns,
236 long readPointToUse, long earliestPutTs, long oldestUnexpiredTS, long now,
237 byte[] dropDeletesFromRow, byte[] dropDeletesToRow,
238 RegionCoprocessorHost regionCoprocessorHost) throws IOException {
239 this(scan, scanInfo, columns, ScanType.COMPACT_RETAIN_DELETES, readPointToUse, earliestPutTs,
240 oldestUnexpiredTS, now, regionCoprocessorHost);
241 Preconditions.checkArgument((dropDeletesFromRow != null) && (dropDeletesToRow != null));
242 this.dropDeletesFromRow = dropDeletesFromRow;
243 this.dropDeletesToRow = dropDeletesToRow;
244 }
245
246
247
248
249 ScanQueryMatcher(Scan scan, ScanInfo scanInfo,
250 NavigableSet<byte[]> columns, long oldestUnexpiredTS, long now) throws IOException {
251 this(scan, scanInfo, columns, ScanType.USER_SCAN,
252 Long.MAX_VALUE,
253 HConstants.LATEST_TIMESTAMP, oldestUnexpiredTS, now, null);
254 }
255
256
257
258
259
260 public boolean hasNullColumnInQuery() {
261 return hasNullColumn;
262 }
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277 public MatchCode match(Cell cell) throws IOException {
278 if (filter != null && filter.filterAllRemaining()) {
279 return MatchCode.DONE_SCAN;
280 }
281 int ret = this.rowComparator.compareRows(row, this.rowOffset, this.rowLength,
282 cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
283 if (!this.isReversed) {
284 if (ret <= -1) {
285 return MatchCode.DONE;
286 } else if (ret >= 1) {
287
288
289
290 return MatchCode.SEEK_NEXT_ROW;
291 }
292 } else {
293 if (ret <= -1) {
294 return MatchCode.SEEK_NEXT_ROW;
295 } else if (ret >= 1) {
296 return MatchCode.DONE;
297 }
298 }
299
300
301 if (this.stickyNextRow)
302 return MatchCode.SEEK_NEXT_ROW;
303
304 if (this.columns.done()) {
305 stickyNextRow = true;
306 return MatchCode.SEEK_NEXT_ROW;
307 }
308
309 int qualifierOffset = cell.getQualifierOffset();
310 int qualifierLength = cell.getQualifierLength();
311
312 long timestamp = cell.getTimestamp();
313
314 if (columns.isDone(timestamp)) {
315 return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
316 qualifierLength);
317 }
318
319 if (HStore.isCellTTLExpired(cell, this.oldestUnexpiredTS, this.now)) {
320 return MatchCode.SKIP;
321 }
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336 byte typeByte = cell.getTypeByte();
337 long mvccVersion = cell.getMvccVersion();
338 if (CellUtil.isDelete(cell)) {
339 if (keepDeletedCells == KeepDeletedCells.FALSE
340 || (keepDeletedCells == KeepDeletedCells.TTL && timestamp < ttl)) {
341
342
343
344
345
346
347 boolean includeDeleteMarker = seePastDeleteMarkers ?
348 tr.withinTimeRange(timestamp) :
349 tr.withinOrAfterTimeRange(timestamp);
350 if (includeDeleteMarker
351 && mvccVersion <= maxReadPointToTrackVersions) {
352 this.deletes.add(cell);
353 }
354
355 }
356
357 if ((!isUserScan)
358 && timeToPurgeDeletes > 0
359 && (EnvironmentEdgeManager.currentTime() - timestamp)
360 <= timeToPurgeDeletes) {
361 return MatchCode.INCLUDE;
362 } else if (retainDeletesInOutput || mvccVersion > maxReadPointToTrackVersions) {
363
364
365 if (!isUserScan) {
366
367
368 return MatchCode.INCLUDE;
369 }
370 } else if (keepDeletedCells == KeepDeletedCells.TRUE
371 || (keepDeletedCells == KeepDeletedCells.TTL && timestamp >= ttl)) {
372 if (timestamp < earliestPutTs) {
373
374
375 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
376 qualifierOffset, qualifierLength);
377 }
378
379
380 } else {
381 return MatchCode.SKIP;
382 }
383
384
385 } else if (!this.deletes.isEmpty()) {
386 DeleteResult deleteResult = deletes.isDeleted(cell);
387 switch (deleteResult) {
388 case FAMILY_DELETED:
389 case COLUMN_DELETED:
390 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
391 qualifierOffset, qualifierLength);
392 case VERSION_DELETED:
393 case FAMILY_VERSION_DELETED:
394 return MatchCode.SKIP;
395 case NOT_DELETED:
396 break;
397 default:
398 throw new RuntimeException("UNEXPECTED");
399 }
400 }
401
402 int timestampComparison = tr.compare(timestamp);
403 if (timestampComparison >= 1) {
404 return MatchCode.SKIP;
405 } else if (timestampComparison <= -1) {
406 return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
407 qualifierLength);
408 }
409
410
411 MatchCode colChecker = columns.checkColumn(cell.getQualifierArray(),
412 qualifierOffset, qualifierLength, typeByte);
413 if (colChecker == MatchCode.INCLUDE) {
414 ReturnCode filterResponse = ReturnCode.SKIP;
415
416 if (filter != null) {
417
418 filterResponse = filter.filterKeyValue(cell);
419 switch (filterResponse) {
420 case SKIP:
421 return MatchCode.SKIP;
422 case NEXT_COL:
423 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
424 qualifierOffset, qualifierLength);
425 case NEXT_ROW:
426 stickyNextRow = true;
427 return MatchCode.SEEK_NEXT_ROW;
428 case SEEK_NEXT_USING_HINT:
429 return MatchCode.SEEK_NEXT_USING_HINT;
430 default:
431
432 break;
433 }
434 }
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454 colChecker =
455 columns.checkVersions(cell.getQualifierArray(), qualifierOffset,
456 qualifierLength, timestamp, typeByte,
457 mvccVersion > maxReadPointToTrackVersions);
458
459 stickyNextRow = colChecker == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW ? true : stickyNextRow;
460 return (filterResponse == ReturnCode.INCLUDE_AND_NEXT_COL &&
461 colChecker == MatchCode.INCLUDE) ? MatchCode.INCLUDE_AND_SEEK_NEXT_COL
462 : colChecker;
463 }
464 stickyNextRow = (colChecker == MatchCode.SEEK_NEXT_ROW) ? true
465 : stickyNextRow;
466 return colChecker;
467 }
468
469
470
471
472 private void checkPartialDropDeleteRange(byte [] row, int offset, short length) {
473
474
475
476
477 if ((dropDeletesFromRow != null)
478 && ((dropDeletesFromRow == HConstants.EMPTY_START_ROW)
479 || (Bytes.compareTo(row, offset, length,
480 dropDeletesFromRow, 0, dropDeletesFromRow.length) >= 0))) {
481 retainDeletesInOutput = false;
482 dropDeletesFromRow = null;
483 }
484
485
486
487 if ((dropDeletesFromRow == null)
488 && (dropDeletesToRow != null) && (dropDeletesToRow != HConstants.EMPTY_END_ROW)
489 && (Bytes.compareTo(row, offset, length,
490 dropDeletesToRow, 0, dropDeletesToRow.length) >= 0)) {
491 retainDeletesInOutput = true;
492 dropDeletesToRow = null;
493 }
494 }
495
496 public boolean moreRowsMayExistAfter(Cell kv) {
497 if (this.isReversed) {
498 if (rowComparator.compareRows(kv.getRowArray(), kv.getRowOffset(),
499 kv.getRowLength(), stopRow, 0, stopRow.length) <= 0) {
500 return false;
501 } else {
502 return true;
503 }
504 }
505 if (!Bytes.equals(stopRow , HConstants.EMPTY_END_ROW) &&
506 rowComparator.compareRows(kv.getRowArray(),kv.getRowOffset(),
507 kv.getRowLength(), stopRow, 0, stopRow.length) >= 0) {
508
509
510 return false;
511 } else {
512 return true;
513 }
514 }
515
516
517
518
519
520 public void setRow(byte [] row, int offset, short length) {
521 checkPartialDropDeleteRange(row, offset, length);
522 this.row = row;
523 this.rowOffset = offset;
524 this.rowLength = length;
525 reset();
526 }
527
528 public void reset() {
529 this.deletes.reset();
530 this.columns.reset();
531
532 stickyNextRow = false;
533 }
534
535
536
537
538
539 public Cell getStartKey() {
540 return this.startKey;
541 }
542
543
544
545
546
547 Filter getFilter() {
548 return this.filter;
549 }
550
551 public Cell getNextKeyHint(Cell kv) throws IOException {
552 if (filter == null) {
553 return null;
554 } else {
555 return filter.getNextCellHint(kv);
556 }
557 }
558
559 public Cell getKeyForNextColumn(Cell kv) {
560
561
562
563 if (kv.getQualifierLength() == 0) {
564 Cell nextKey = createNextOnRowCol(kv);
565 if (nextKey != kv) {
566 return nextKey;
567 }
568
569
570 }
571 ColumnCount nextColumn = columns.getColumnHint();
572 if (nextColumn == null) {
573 return KeyValueUtil.createLastOnRow(
574 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
575 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
576 kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength());
577 } else {
578 return KeyValueUtil.createFirstOnRow(
579 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
580 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
581 nextColumn.getBuffer(), nextColumn.getOffset(), nextColumn.getLength());
582 }
583 }
584
585 public Cell getKeyForNextRow(Cell kv) {
586 return KeyValueUtil.createLastOnRow(
587 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
588 null, 0, 0,
589 null, 0, 0);
590 }
591
592
593
594
595
596
597 public int compareKeyForNextRow(Cell nextIndexed, Cell kv) {
598 return rowComparator.compareKey(nextIndexed,
599 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
600 null, 0, 0,
601 null, 0, 0,
602 HConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
603 }
604
605
606
607
608
609
610 public int compareKeyForNextColumn(Cell nextIndexed, Cell kv) {
611 ColumnCount nextColumn = columns.getColumnHint();
612 if (nextColumn == null) {
613 return rowComparator.compareKey(nextIndexed,
614 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
615 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
616 kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength(),
617 HConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
618 } else {
619 return rowComparator.compareKey(nextIndexed,
620 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
621 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
622 nextColumn.getBuffer(), nextColumn.getOffset(), nextColumn.getLength(),
623 HConstants.LATEST_TIMESTAMP, Type.Maximum.getCode());
624 }
625 }
626
627
628 static MatchCode checkColumn(ColumnTracker columnTracker, byte[] bytes, int offset,
629 int length, long ttl, byte type, boolean ignoreCount) throws IOException {
630 MatchCode matchCode = columnTracker.checkColumn(bytes, offset, length, type);
631 if (matchCode == MatchCode.INCLUDE) {
632 return columnTracker.checkVersions(bytes, offset, length, ttl, type, ignoreCount);
633 }
634 return matchCode;
635 }
636
637
638
639
640
641
642
643
644 public static enum MatchCode {
645
646
647
648 INCLUDE,
649
650
651
652
653 SKIP,
654
655
656
657
658 NEXT,
659
660
661
662
663 DONE,
664
665
666
667
668
669
670
671
672 SEEK_NEXT_ROW,
673
674
675
676 SEEK_NEXT_COL,
677
678
679
680
681 DONE_SCAN,
682
683
684
685
686 SEEK_NEXT_USING_HINT,
687
688
689
690
691 INCLUDE_AND_SEEK_NEXT_COL,
692
693
694
695
696 INCLUDE_AND_SEEK_NEXT_ROW,
697 }
698
699
700
701
702
703 private static Cell createNextOnRowCol(Cell cell) {
704 long ts = cell.getTimestamp();
705 byte type = cell.getTypeByte();
706 if (type != Type.Minimum.getCode()) {
707 type = KeyValue.Type.values()[KeyValue.Type.codeToType(type).ordinal() - 1].getCode();
708 } else if (ts != HConstants.OLDEST_TIMESTAMP) {
709 ts = ts - 1;
710 type = Type.Maximum.getCode();
711 } else {
712 return cell;
713 }
714 return createNextOnRowCol(cell, ts, type);
715 }
716
717 private static Cell createNextOnRowCol(final Cell cell, final long ts, final byte type) {
718 return new Cell() {
719 @Override
720 public byte[] getRowArray() { return cell.getRowArray(); }
721
722 @Override
723 public int getRowOffset() { return cell.getRowOffset(); }
724
725 @Override
726 public short getRowLength() { return cell.getRowLength(); }
727
728 @Override
729 public byte[] getFamilyArray() { return cell.getFamilyArray(); }
730
731 @Override
732 public int getFamilyOffset() { return cell.getFamilyOffset(); }
733
734 @Override
735 public byte getFamilyLength() { return cell.getFamilyLength(); }
736
737 @Override
738 public byte[] getQualifierArray() { return cell.getQualifierArray(); }
739
740 @Override
741 public int getQualifierOffset() { return cell.getQualifierOffset(); }
742
743 @Override
744 public int getQualifierLength() { return cell.getQualifierLength(); }
745
746 @Override
747 public long getTimestamp() { return ts; }
748
749 @Override
750 public byte getTypeByte() {return type; }
751
752 @Override
753 public long getMvccVersion() { return cell.getMvccVersion(); }
754
755 @Override
756 public long getSequenceId() { return cell.getSequenceId(); }
757
758 @Override
759 public byte[] getValueArray() { return cell.getValueArray(); }
760
761 @Override
762 public int getValueOffset() { return cell.getValueOffset(); }
763
764 @Override
765 public int getValueLength() { return cell.getValueLength(); }
766
767 @Override
768 public byte[] getTagsArray() { return cell.getTagsArray(); }
769
770 @Override
771 public int getTagsOffset() { return cell.getTagsOffset(); }
772
773 @Override
774 public int getTagsLength() { return cell.getTagsLength(); }
775
776 @Override
777 public byte[] getValue() { return cell.getValue(); }
778
779 @Override
780 public byte[] getFamily() { return cell.getFamily(); }
781
782 @Override
783 public byte[] getQualifier() { return cell.getQualifier(); }
784
785 @Override
786 public byte[] getRow() {return cell.getRow(); }
787 };
788 }
789 }