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 if (row != null) {
282 int ret = this.rowComparator.compareRows(row, this.rowOffset, this.rowLength,
283 cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
284 if (!this.isReversed) {
285 if (ret <= -1) {
286 return MatchCode.DONE;
287 } else if (ret >= 1) {
288
289
290
291 return MatchCode.SEEK_NEXT_ROW;
292 }
293 } else {
294 if (ret <= -1) {
295 return MatchCode.SEEK_NEXT_ROW;
296 } else if (ret >= 1) {
297 return MatchCode.DONE;
298 }
299 }
300 } else {
301 return MatchCode.DONE;
302 }
303
304
305 if (this.stickyNextRow)
306 return MatchCode.SEEK_NEXT_ROW;
307
308 if (this.columns.done()) {
309 stickyNextRow = true;
310 return MatchCode.SEEK_NEXT_ROW;
311 }
312
313 int qualifierOffset = cell.getQualifierOffset();
314 int qualifierLength = cell.getQualifierLength();
315
316 long timestamp = cell.getTimestamp();
317
318 if (columns.isDone(timestamp)) {
319 return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
320 qualifierLength);
321 }
322
323 if (HStore.isCellTTLExpired(cell, this.oldestUnexpiredTS, this.now)) {
324 return MatchCode.SKIP;
325 }
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340 byte typeByte = cell.getTypeByte();
341 long mvccVersion = cell.getMvccVersion();
342 if (CellUtil.isDelete(cell)) {
343 if (keepDeletedCells == KeepDeletedCells.FALSE
344 || (keepDeletedCells == KeepDeletedCells.TTL && timestamp < ttl)) {
345
346
347
348
349
350
351 boolean includeDeleteMarker = seePastDeleteMarkers ?
352 tr.withinTimeRange(timestamp) :
353 tr.withinOrAfterTimeRange(timestamp);
354 if (includeDeleteMarker
355 && mvccVersion <= maxReadPointToTrackVersions) {
356 this.deletes.add(cell);
357 }
358
359 }
360
361 if ((!isUserScan)
362 && timeToPurgeDeletes > 0
363 && (EnvironmentEdgeManager.currentTime() - timestamp)
364 <= timeToPurgeDeletes) {
365 return MatchCode.INCLUDE;
366 } else if (retainDeletesInOutput || mvccVersion > maxReadPointToTrackVersions) {
367
368
369 if (!isUserScan) {
370
371
372 return MatchCode.INCLUDE;
373 }
374 } else if (keepDeletedCells == KeepDeletedCells.TRUE
375 || (keepDeletedCells == KeepDeletedCells.TTL && timestamp >= ttl)) {
376 if (timestamp < earliestPutTs) {
377
378
379 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
380 qualifierOffset, qualifierLength);
381 }
382
383
384 } else {
385 return MatchCode.SKIP;
386 }
387
388
389 } else if (!this.deletes.isEmpty()) {
390 DeleteResult deleteResult = deletes.isDeleted(cell);
391 switch (deleteResult) {
392 case FAMILY_DELETED:
393 case COLUMN_DELETED:
394 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
395 qualifierOffset, qualifierLength);
396 case VERSION_DELETED:
397 case FAMILY_VERSION_DELETED:
398 return MatchCode.SKIP;
399 case NOT_DELETED:
400 break;
401 default:
402 throw new RuntimeException("UNEXPECTED");
403 }
404 }
405
406 int timestampComparison = tr.compare(timestamp);
407 if (timestampComparison >= 1) {
408 return MatchCode.SKIP;
409 } else if (timestampComparison <= -1) {
410 return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
411 qualifierLength);
412 }
413
414
415 MatchCode colChecker = columns.checkColumn(cell.getQualifierArray(),
416 qualifierOffset, qualifierLength, typeByte);
417 if (colChecker == MatchCode.INCLUDE) {
418 ReturnCode filterResponse = ReturnCode.SKIP;
419
420 if (filter != null) {
421
422 filterResponse = filter.filterKeyValue(cell);
423 switch (filterResponse) {
424 case SKIP:
425 return MatchCode.SKIP;
426 case NEXT_COL:
427 return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
428 qualifierOffset, qualifierLength);
429 case NEXT_ROW:
430 stickyNextRow = true;
431 return MatchCode.SEEK_NEXT_ROW;
432 case SEEK_NEXT_USING_HINT:
433 return MatchCode.SEEK_NEXT_USING_HINT;
434 default:
435
436 break;
437 }
438 }
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458 colChecker =
459 columns.checkVersions(cell.getQualifierArray(), qualifierOffset,
460 qualifierLength, timestamp, typeByte,
461 mvccVersion > maxReadPointToTrackVersions);
462
463 stickyNextRow = colChecker == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW ? true : stickyNextRow;
464 return (filterResponse == ReturnCode.INCLUDE_AND_NEXT_COL &&
465 colChecker == MatchCode.INCLUDE) ? MatchCode.INCLUDE_AND_SEEK_NEXT_COL
466 : colChecker;
467 }
468 stickyNextRow = (colChecker == MatchCode.SEEK_NEXT_ROW) ? true
469 : stickyNextRow;
470 return colChecker;
471 }
472
473
474
475
476 private void checkPartialDropDeleteRange(byte [] row, int offset, short length) {
477
478
479
480
481 if ((dropDeletesFromRow != null)
482 && ((dropDeletesFromRow == HConstants.EMPTY_START_ROW)
483 || (Bytes.compareTo(row, offset, length,
484 dropDeletesFromRow, 0, dropDeletesFromRow.length) >= 0))) {
485 retainDeletesInOutput = false;
486 dropDeletesFromRow = null;
487 }
488
489
490
491 if ((dropDeletesFromRow == null)
492 && (dropDeletesToRow != null) && (dropDeletesToRow != HConstants.EMPTY_END_ROW)
493 && (Bytes.compareTo(row, offset, length,
494 dropDeletesToRow, 0, dropDeletesToRow.length) >= 0)) {
495 retainDeletesInOutput = true;
496 dropDeletesToRow = null;
497 }
498 }
499
500 public boolean moreRowsMayExistAfter(Cell kv) {
501 if (this.isReversed) {
502 if (rowComparator.compareRows(kv.getRowArray(), kv.getRowOffset(),
503 kv.getRowLength(), stopRow, 0, stopRow.length) <= 0) {
504 return false;
505 } else {
506 return true;
507 }
508 }
509 if (!Bytes.equals(stopRow , HConstants.EMPTY_END_ROW) &&
510 rowComparator.compareRows(kv.getRowArray(),kv.getRowOffset(),
511 kv.getRowLength(), stopRow, 0, stopRow.length) >= 0) {
512
513
514 return false;
515 } else {
516 return true;
517 }
518 }
519
520
521
522
523
524 public void setRow(byte [] row, int offset, short length) {
525 checkPartialDropDeleteRange(row, offset, length);
526 this.row = row;
527 this.rowOffset = offset;
528 this.rowLength = length;
529 reset();
530 }
531
532 public void reset() {
533 this.deletes.reset();
534 this.columns.reset();
535
536 stickyNextRow = false;
537 }
538
539
540
541
542
543 public Cell getStartKey() {
544 return this.startKey;
545 }
546
547
548
549
550
551 Filter getFilter() {
552 return this.filter;
553 }
554
555 public Cell getNextKeyHint(Cell kv) throws IOException {
556 if (filter == null) {
557 return null;
558 } else {
559 return filter.getNextCellHint(kv);
560 }
561 }
562
563 public Cell getKeyForNextColumn(Cell kv) {
564 ColumnCount nextColumn = columns.getColumnHint();
565 if (nextColumn == null) {
566 return KeyValueUtil.createLastOnRow(
567 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
568 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
569 kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength());
570 } else {
571 return KeyValueUtil.createFirstOnRow(
572 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
573 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
574 nextColumn.getBuffer(), nextColumn.getOffset(), nextColumn.getLength());
575 }
576 }
577
578 public Cell getKeyForNextRow(Cell kv) {
579 return KeyValueUtil.createLastOnRow(
580 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
581 null, 0, 0,
582 null, 0, 0);
583 }
584
585
586
587
588
589
590 public int compareKeyForNextRow(Cell nextIndexed, Cell kv) {
591 return rowComparator.compareKey(nextIndexed,
592 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
593 null, 0, 0,
594 null, 0, 0,
595 HConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
596 }
597
598
599
600
601
602
603 public int compareKeyForNextColumn(Cell nextIndexed, Cell kv) {
604 ColumnCount nextColumn = columns.getColumnHint();
605 if (nextColumn == null) {
606 return rowComparator.compareKey(nextIndexed,
607 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
608 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
609 kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength(),
610 HConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
611 } else {
612 return rowComparator.compareKey(nextIndexed,
613 kv.getRowArray(), kv.getRowOffset(), kv.getRowLength(),
614 kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
615 nextColumn.getBuffer(), nextColumn.getOffset(), nextColumn.getLength(),
616 HConstants.LATEST_TIMESTAMP, Type.Maximum.getCode());
617 }
618 }
619
620
621 static MatchCode checkColumn(ColumnTracker columnTracker, byte[] bytes, int offset,
622 int length, long ttl, byte type, boolean ignoreCount) throws IOException {
623 MatchCode matchCode = columnTracker.checkColumn(bytes, offset, length, type);
624 if (matchCode == MatchCode.INCLUDE) {
625 return columnTracker.checkVersions(bytes, offset, length, ttl, type, ignoreCount);
626 }
627 return matchCode;
628 }
629
630
631
632
633
634
635
636
637 public static enum MatchCode {
638
639
640
641 INCLUDE,
642
643
644
645
646 SKIP,
647
648
649
650
651 NEXT,
652
653
654
655
656 DONE,
657
658
659
660
661
662
663
664
665 SEEK_NEXT_ROW,
666
667
668
669 SEEK_NEXT_COL,
670
671
672
673
674 DONE_SCAN,
675
676
677
678
679 SEEK_NEXT_USING_HINT,
680
681
682
683
684 INCLUDE_AND_SEEK_NEXT_COL,
685
686
687
688
689 INCLUDE_AND_SEEK_NEXT_ROW,
690 }
691 }