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 TimeRange timeRange = scan.getColumnFamilyTimeRange().get(scanInfo.getFamily());
164 if (timeRange == null) {
165 this.tr = scan.getTimeRange();
166 } else {
167 this.tr = timeRange;
168 }
169 this.rowComparator = scanInfo.getComparator();
170 this.regionCoprocessorHost = regionCoprocessorHost;
171 this.deletes = instantiateDeleteTracker();
172 this.stopRow = scan.getStopRow();
173 this.startKey = KeyValueUtil.createFirstDeleteFamilyOnRow(scan.getStartRow(),
174 scanInfo.getFamily());
175 this.filter = scan.getFilter();
176 this.earliestPutTs = earliestPutTs;
177 this.oldestUnexpiredTS = oldestUnexpiredTS;
178 this.now = now;
179
180 this.maxReadPointToTrackVersions = readPointToUse;
181 this.timeToPurgeDeletes = scanInfo.getTimeToPurgeDeletes();
182 this.ttl = oldestUnexpiredTS;
183
184
185 this.isUserScan = scanType == ScanType.USER_SCAN;
186
187 this.keepDeletedCells = scan.isRaw() ? KeepDeletedCells.TRUE :
188 isUserScan ? KeepDeletedCells.FALSE : scanInfo.getKeepDeletedCells();
189
190 this.retainDeletesInOutput = scanType == ScanType.COMPACT_RETAIN_DELETES || scan.isRaw();
191
192 this.seePastDeleteMarkers =
193 scanInfo.getKeepDeletedCells() != KeepDeletedCells.FALSE && isUserScan;
194
195 int maxVersions =
196 scan.isRaw() ? scan.getMaxVersions() : Math.min(scan.getMaxVersions(),
197 scanInfo.getMaxVersions());
198
199
200 if (columns == null || columns.size() == 0) {
201
202 hasNullColumn = true;
203
204
205 this.columns = new ScanWildcardColumnTracker(
206 scanInfo.getMinVersions(), maxVersions, oldestUnexpiredTS);
207 } else {
208
209 hasNullColumn = (columns.first().length == 0);
210
211
212
213 this.columns = new ExplicitColumnTracker(columns, scanInfo.getMinVersions(), maxVersions,
214 oldestUnexpiredTS);
215 }
216 this.isReversed = scan.isReversed();
217 }
218
219 private DeleteTracker instantiateDeleteTracker() throws IOException {
220 DeleteTracker tracker = new ScanDeleteTracker();
221 if (regionCoprocessorHost != null) {
222 tracker = regionCoprocessorHost.postInstantiateDeleteTracker(tracker);
223 }
224 return tracker;
225 }
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240 public ScanQueryMatcher(Scan scan, ScanInfo scanInfo, NavigableSet<byte[]> columns,
241 long readPointToUse, long earliestPutTs, long oldestUnexpiredTS, long now,
242 byte[] dropDeletesFromRow, byte[] dropDeletesToRow,
243 RegionCoprocessorHost regionCoprocessorHost) throws IOException {
244 this(scan, scanInfo, columns, ScanType.COMPACT_RETAIN_DELETES, readPointToUse, earliestPutTs,
245 oldestUnexpiredTS, now, regionCoprocessorHost);
246 Preconditions.checkArgument((dropDeletesFromRow != null) && (dropDeletesToRow != null));
247 this.dropDeletesFromRow = dropDeletesFromRow;
248 this.dropDeletesToRow = dropDeletesToRow;
249 }
250
251
252
253
254 ScanQueryMatcher(Scan scan, ScanInfo scanInfo,
255 NavigableSet<byte[]> columns, long oldestUnexpiredTS, long now) throws IOException {
256 this(scan, scanInfo, columns, ScanType.USER_SCAN,
257 Long.MAX_VALUE,
258 HConstants.LATEST_TIMESTAMP, oldestUnexpiredTS, now, null);
259 }
260
261
262
263
264
265 public boolean hasNullColumnInQuery() {
266 return hasNullColumn;
267 }
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282 public MatchCode match(Cell cell) throws IOException {
283 if (filter != null && filter.filterAllRemaining()) {
284 return MatchCode.DONE_SCAN;
285 }
286 if (row != null) {
287 int ret = this.rowComparator.compareRows(row, this.rowOffset, this.rowLength,
288 cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
289 if (!this.isReversed) {
290 if (ret <= -1) {
291 return MatchCode.DONE;
292 } else if (ret >= 1) {
293
294
295
296 return MatchCode.SEEK_NEXT_ROW;
297 }
298 } else {
299 if (ret <= -1) {
300 return MatchCode.SEEK_NEXT_ROW;
301 } else if (ret >= 1) {
302 return MatchCode.DONE;
303 }
304 }
305 } else {
306 return MatchCode.DONE;
307 }
308
309
310 if (this.stickyNextRow)
311 return MatchCode.SEEK_NEXT_ROW;
312
313 if (this.columns.done()) {
314 stickyNextRow = true;
315 return MatchCode.SEEK_NEXT_ROW;
316 }
317
318 int qualifierOffset = cell.getQualifierOffset();
319 int qualifierLength = cell.getQualifierLength();
320
321 long timestamp = cell.getTimestamp();
322
323 if (columns.isDone(timestamp)) {
324 return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
325 qualifierLength);
326 }
327
328 if (HStore.isCellTTLExpired(cell, this.oldestUnexpiredTS, this.now)) {
329 return MatchCode.SKIP;
330 }
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345 byte typeByte = cell.getTypeByte();
346 long mvccVersion = cell.getMvccVersion();
347 if (CellUtil.isDelete(cell)) {
348 if (keepDeletedCells == KeepDeletedCells.FALSE
349 || (keepDeletedCells == KeepDeletedCells.TTL && timestamp < ttl)) {
350
351
352
353
354
355
356 boolean includeDeleteMarker = seePastDeleteMarkers ?
357 tr.withinTimeRange(timestamp) :
358 tr.withinOrAfterTimeRange(timestamp);
359 if (includeDeleteMarker
360 && mvccVersion <= maxReadPointToTrackVersions) {
361 this.deletes.add(cell);
362 }
363
364 }
365
366 if ((!isUserScan)
367 && timeToPurgeDeletes > 0
368 && (EnvironmentEdgeManager.currentTime() - timestamp)
369 <= timeToPurgeDeletes) {
370 return MatchCode.INCLUDE;
371 } else if (retainDeletesInOutput || mvccVersion > maxReadPointToTrackVersions) {
372
373
374 if (!isUserScan) {
375
376
377 return MatchCode.INCLUDE;
378 }
379 } else if (keepDeletedCells == KeepDeletedCells.TRUE
380 || (keepDeletedCells == KeepDeletedCells.TTL && timestamp >= ttl)) {
381 if (timestamp < earliestPutTs) {
382
383
384 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
385 qualifierOffset, qualifierLength);
386 }
387
388
389 } else {
390 return MatchCode.SKIP;
391 }
392
393
394 } else if (!this.deletes.isEmpty()) {
395 DeleteResult deleteResult = deletes.isDeleted(cell);
396 switch (deleteResult) {
397 case FAMILY_DELETED:
398 case COLUMN_DELETED:
399 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
400 qualifierOffset, qualifierLength);
401 case VERSION_DELETED:
402 case FAMILY_VERSION_DELETED:
403 return MatchCode.SKIP;
404 case NOT_DELETED:
405 break;
406 default:
407 throw new RuntimeException("UNEXPECTED");
408 }
409 }
410
411 int timestampComparison = tr.compare(timestamp);
412 if (timestampComparison >= 1) {
413 return MatchCode.SKIP;
414 } else if (timestampComparison <= -1) {
415 return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
416 qualifierLength);
417 }
418
419
420 MatchCode colChecker = columns.checkColumn(cell.getQualifierArray(),
421 qualifierOffset, qualifierLength, typeByte);
422 if (colChecker == MatchCode.INCLUDE) {
423 ReturnCode filterResponse = ReturnCode.SKIP;
424
425 if (filter != null) {
426
427 filterResponse = filter.filterKeyValue(cell);
428 switch (filterResponse) {
429 case SKIP:
430 return MatchCode.SKIP;
431 case NEXT_COL:
432 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
433 qualifierOffset, qualifierLength);
434 case NEXT_ROW:
435 stickyNextRow = true;
436 return MatchCode.SEEK_NEXT_ROW;
437 case SEEK_NEXT_USING_HINT:
438 return MatchCode.SEEK_NEXT_USING_HINT;
439 default:
440
441 break;
442 }
443 }
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463 colChecker =
464 columns.checkVersions(cell.getQualifierArray(), qualifierOffset,
465 qualifierLength, timestamp, typeByte,
466 mvccVersion > 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(Cell 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 Cell 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 Cell getKeyForNextColumn(Cell kv) {
569 ColumnCount nextColumn = columns.getColumnHint();
570 if (nextColumn == null) {
571 return KeyValueUtil.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 KeyValueUtil.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 Cell getKeyForNextRow(Cell kv) {
584 return KeyValueUtil.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(Cell nextIndexed, Cell kv) {
596 return rowComparator.compareKey(nextIndexed,
597 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
598 null, 0, 0,
599 null, 0, 0,
600 HConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
601 }
602
603
604
605
606
607
608 public int compareKeyForNextColumn(Cell nextIndexed, Cell kv) {
609 ColumnCount nextColumn = columns.getColumnHint();
610 if (nextColumn == null) {
611 return rowComparator.compareKey(nextIndexed,
612 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
613 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
614 kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength(),
615 HConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
616 } else {
617 return rowComparator.compareKey(nextIndexed,
618 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
619 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
620 nextColumn.getBuffer(), nextColumn.getOffset(), nextColumn.getLength(),
621 HConstants.LATEST_TIMESTAMP, Type.Maximum.getCode());
622 }
623 }
624
625
626 static MatchCode checkColumn(ColumnTracker columnTracker, byte[] bytes, int offset,
627 int length, long ttl, byte type, boolean ignoreCount) throws IOException {
628 MatchCode matchCode = columnTracker.checkColumn(bytes, offset, length, type);
629 if (matchCode == MatchCode.INCLUDE) {
630 return columnTracker.checkVersions(bytes, offset, length, ttl, type, ignoreCount);
631 }
632 return matchCode;
633 }
634
635
636
637
638
639
640
641
642 public static enum MatchCode {
643
644
645
646 INCLUDE,
647
648
649
650
651 SKIP,
652
653
654
655
656 NEXT,
657
658
659
660
661 DONE,
662
663
664
665
666
667
668
669
670 SEEK_NEXT_ROW,
671
672
673
674 SEEK_NEXT_COL,
675
676
677
678
679 DONE_SCAN,
680
681
682
683
684 SEEK_NEXT_USING_HINT,
685
686
687
688
689 INCLUDE_AND_SEEK_NEXT_COL,
690
691
692
693
694 INCLUDE_AND_SEEK_NEXT_ROW,
695 }
696 }