1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.apache.hadoop.hbase.regionserver;
22
23 import org.apache.hadoop.hbase.HConstants;
24 import org.apache.hadoop.hbase.KeyValue;
25 import org.apache.hadoop.hbase.client.Scan;
26 import org.apache.hadoop.hbase.filter.Filter;
27 import org.apache.hadoop.hbase.filter.Filter.ReturnCode;
28 import org.apache.hadoop.hbase.io.TimeRange;
29 import org.apache.hadoop.hbase.util.Bytes;
30
31 import java.util.NavigableSet;
32
33
34
35
36 public class ScanQueryMatcher {
37
38
39 private boolean stickyNextRow;
40 private byte[] stopRow;
41
42 protected TimeRange tr;
43
44 protected Filter filter;
45
46
47 protected DeleteTracker deletes;
48 protected boolean retainDeletesInOutput;
49
50
51 protected ColumnTracker columns;
52
53
54 protected KeyValue startKey;
55
56
57 protected long oldestStamp;
58
59
60 KeyValue.KeyComparator rowComparator;
61
62
63 protected byte [] row;
64
65
66
67
68
69
70
71
72
73 public ScanQueryMatcher(Scan scan, byte [] family,
74 NavigableSet<byte[]> columns, long ttl,
75 KeyValue.KeyComparator rowComparator, int maxVersions,
76 boolean retainDeletesInOutput) {
77 this.tr = scan.getTimeRange();
78 this.oldestStamp = System.currentTimeMillis() - ttl;
79 this.rowComparator = rowComparator;
80 this.deletes = new ScanDeleteTracker();
81 this.stopRow = scan.getStopRow();
82 this.startKey = KeyValue.createFirstOnRow(scan.getStartRow());
83 this.filter = scan.getFilter();
84 this.retainDeletesInOutput = retainDeletesInOutput;
85
86
87 if (columns == null || columns.size() == 0) {
88
89 this.columns = new ScanWildcardColumnTracker(maxVersions);
90 } else {
91
92
93 this.columns = new ExplicitColumnTracker(columns,maxVersions);
94 }
95 }
96 public ScanQueryMatcher(Scan scan, byte [] family,
97 NavigableSet<byte[]> columns, long ttl,
98 KeyValue.KeyComparator rowComparator, int maxVersions) {
99
100
101 this(scan, family, columns, ttl, rowComparator, maxVersions, false);
102 }
103
104
105
106
107
108
109
110
111
112
113
114
115 public MatchCode match(KeyValue kv) {
116 if (filter != null && filter.filterAllRemaining()) {
117 return MatchCode.DONE_SCAN;
118 }
119
120 byte [] bytes = kv.getBuffer();
121 int offset = kv.getOffset();
122 int initialOffset = offset;
123
124 int keyLength = Bytes.toInt(bytes, offset, Bytes.SIZEOF_INT);
125 offset += KeyValue.ROW_OFFSET;
126
127 short rowLength = Bytes.toShort(bytes, offset, Bytes.SIZEOF_SHORT);
128 offset += Bytes.SIZEOF_SHORT;
129
130 int ret = this.rowComparator.compareRows(row, 0, row.length,
131 bytes, offset, rowLength);
132 if (ret <= -1) {
133 return MatchCode.DONE;
134 } else if (ret >= 1) {
135
136
137
138 return MatchCode.SEEK_NEXT_ROW;
139 }
140
141
142 if (this.stickyNextRow)
143 return MatchCode.SEEK_NEXT_ROW;
144
145 if (this.columns.done()) {
146 stickyNextRow = true;
147 return MatchCode.SEEK_NEXT_ROW;
148 }
149
150
151 offset += rowLength;
152
153
154 byte familyLength = bytes [offset];
155 offset += familyLength + 1;
156
157 int qualLength = keyLength + KeyValue.ROW_OFFSET -
158 (offset - initialOffset) - KeyValue.TIMESTAMP_TYPE_SIZE;
159
160 long timestamp = kv.getTimestamp();
161 if (isExpired(timestamp)) {
162
163 return getNextRowOrNextColumn(bytes, offset, qualLength);
164 }
165
166 byte type = kv.getType();
167 if (isDelete(type)) {
168 if (tr.withinOrAfterTimeRange(timestamp)) {
169 this.deletes.add(bytes, offset, qualLength, timestamp, type);
170
171 }
172 if (retainDeletesInOutput) {
173 return MatchCode.INCLUDE;
174 }
175 else {
176 return MatchCode.SKIP;
177 }
178 }
179
180 if (!this.deletes.isEmpty() &&
181 deletes.isDeleted(bytes, offset, qualLength, timestamp)) {
182
183
184
185
186
187
188 return MatchCode.SKIP;
189 }
190
191 int timestampComparison = tr.compare(timestamp);
192 if (timestampComparison >= 1) {
193 return MatchCode.SKIP;
194 } else if (timestampComparison <= -1) {
195 return getNextRowOrNextColumn(bytes, offset, qualLength);
196 }
197
198
199
200
201
202
203
204 if (filter != null) {
205 ReturnCode filterResponse = filter.filterKeyValue(kv);
206 if (filterResponse == ReturnCode.SKIP) {
207 return MatchCode.SKIP;
208 } else if (filterResponse == ReturnCode.NEXT_COL) {
209 return getNextRowOrNextColumn(bytes, offset, qualLength);
210 } else if (filterResponse == ReturnCode.NEXT_ROW) {
211 stickyNextRow = true;
212 return MatchCode.SEEK_NEXT_ROW;
213 } else if (filterResponse == ReturnCode.SEEK_NEXT_USING_HINT) {
214 return MatchCode.SEEK_NEXT_USING_HINT;
215 }
216 }
217
218 MatchCode colChecker = columns.checkColumn(bytes, offset, qualLength, timestamp);
219
220
221
222
223
224 if (colChecker == MatchCode.SEEK_NEXT_ROW) {
225 stickyNextRow = true;
226 }
227 return colChecker;
228
229 }
230
231 public MatchCode getNextRowOrNextColumn(byte[] bytes, int offset,
232 int qualLength) {
233 if (columns instanceof ExplicitColumnTracker) {
234
235
236 ((ExplicitColumnTracker)columns).doneWithColumn(bytes, offset,
237 qualLength);
238 if (columns.getColumnHint() == null) {
239 return MatchCode.SEEK_NEXT_ROW;
240 } else {
241 return MatchCode.SEEK_NEXT_COL;
242 }
243 } else {
244 return MatchCode.SEEK_NEXT_COL;
245 }
246 }
247
248 public boolean moreRowsMayExistAfter(KeyValue kv) {
249 if (!Bytes.equals(stopRow , HConstants.EMPTY_END_ROW) &&
250 rowComparator.compareRows(kv.getBuffer(),kv.getRowOffset(),
251 kv.getRowLength(), stopRow, 0, stopRow.length) >= 0) {
252
253
254 return false;
255 } else {
256 return true;
257 }
258 }
259
260
261
262
263
264 public void setRow(byte [] row) {
265 this.row = row;
266 reset();
267 }
268
269 public void reset() {
270 this.deletes.reset();
271 this.columns.reset();
272
273 stickyNextRow = false;
274 }
275
276
277 protected boolean isDelete(byte type) {
278 return (type != KeyValue.Type.Put.getCode());
279 }
280
281 protected boolean isExpired(long timestamp) {
282 return (timestamp < oldestStamp);
283 }
284
285
286
287
288
289 public KeyValue getStartKey() {
290 return this.startKey;
291 }
292
293 public KeyValue getNextKeyHint(KeyValue kv) {
294 if (filter == null) {
295 return null;
296 } else {
297 return filter.getNextKeyHint(kv);
298 }
299 }
300
301 public KeyValue getKeyForNextColumn(KeyValue kv) {
302 ColumnCount nextColumn = columns.getColumnHint();
303 if (nextColumn == null) {
304 return KeyValue.createLastOnRow(
305 kv.getBuffer(), kv.getRowOffset(), kv.getRowLength(),
306 kv.getBuffer(), kv.getFamilyOffset(), kv.getFamilyLength(),
307 kv.getBuffer(), kv.getQualifierOffset(), kv.getQualifierLength());
308 } else {
309 return KeyValue.createFirstOnRow(
310 kv.getBuffer(), kv.getRowOffset(), kv.getRowLength(),
311 kv.getBuffer(), kv.getFamilyOffset(), kv.getFamilyLength(),
312 nextColumn.getBuffer(), nextColumn.getOffset(), nextColumn.getLength());
313 }
314 }
315
316 public KeyValue getKeyForNextRow(KeyValue kv) {
317 return KeyValue.createLastOnRow(
318 kv.getBuffer(), kv.getRowOffset(), kv.getRowLength(),
319 null, 0, 0,
320 null, 0, 0);
321 }
322
323
324
325
326
327
328
329
330 public static enum MatchCode {
331
332
333
334 INCLUDE,
335
336
337
338
339 SKIP,
340
341
342
343
344 NEXT,
345
346
347
348
349 DONE,
350
351
352
353
354
355
356
357
358 SEEK_NEXT_ROW,
359
360
361
362 SEEK_NEXT_COL,
363
364
365
366
367 DONE_SCAN,
368
369
370
371
372 SEEK_NEXT_USING_HINT,
373 }
374 }