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