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.Comparator;
24 import java.util.List;
25 import java.util.PriorityQueue;
26
27 import org.apache.hadoop.classification.InterfaceAudience;
28 import org.apache.hadoop.hbase.Cell;
29 import org.apache.hadoop.hbase.KeyValue;
30 import org.apache.hadoop.hbase.KeyValue.KVComparator;
31
32
33
34
35
36
37
38
39
40
41
42
43
44 @InterfaceAudience.Private
45 public class KeyValueHeap extends NonReversedNonLazyKeyValueScanner
46 implements KeyValueScanner, InternalScanner {
47 protected PriorityQueue<KeyValueScanner> heap = null;
48
49
50
51
52
53
54
55
56
57
58
59 protected KeyValueScanner current = null;
60
61 protected KVScannerComparator comparator;
62
63
64
65
66
67
68
69 public KeyValueHeap(List<? extends KeyValueScanner> scanners,
70 KVComparator comparator) throws IOException {
71 this(scanners, new KVScannerComparator(comparator));
72 }
73
74
75
76
77
78
79
80 KeyValueHeap(List<? extends KeyValueScanner> scanners,
81 KVScannerComparator comparator) throws IOException {
82 this.comparator = comparator;
83 if (!scanners.isEmpty()) {
84 this.heap = new PriorityQueue<KeyValueScanner>(scanners.size(),
85 this.comparator);
86 for (KeyValueScanner scanner : scanners) {
87 if (scanner.peek() != null) {
88 this.heap.add(scanner);
89 } else {
90 scanner.close();
91 }
92 }
93 this.current = pollRealKV();
94 }
95 }
96
97 public KeyValue peek() {
98 if (this.current == null) {
99 return null;
100 }
101 return this.current.peek();
102 }
103
104 public KeyValue next() throws IOException {
105 if(this.current == null) {
106 return null;
107 }
108 KeyValue kvReturn = this.current.next();
109 KeyValue kvNext = this.current.peek();
110 if (kvNext == null) {
111 this.current.close();
112 this.current = pollRealKV();
113 } else {
114 KeyValueScanner topScanner = this.heap.peek();
115
116 if (topScanner != null && this.comparator.compare(kvNext, topScanner.peek()) >= 0) {
117 this.heap.add(this.current);
118 this.current = pollRealKV();
119 }
120 }
121 return kvReturn;
122 }
123
124
125
126
127
128
129
130
131
132
133
134
135 public boolean next(List<Cell> result, int limit) throws IOException {
136 if (this.current == null) {
137 return false;
138 }
139 InternalScanner currentAsInternal = (InternalScanner)this.current;
140 boolean mayContainMoreRows = currentAsInternal.next(result, limit);
141 KeyValue pee = this.current.peek();
142
143
144
145
146
147
148
149 if (pee == null || !mayContainMoreRows) {
150 this.current.close();
151 } else {
152 this.heap.add(this.current);
153 }
154 this.current = pollRealKV();
155 return (this.current != null);
156 }
157
158
159
160
161
162
163
164
165
166
167
168 public boolean next(List<Cell> result) throws IOException {
169 return next(result, -1);
170 }
171
172 protected static class KVScannerComparator implements Comparator<KeyValueScanner> {
173 protected KVComparator kvComparator;
174
175
176
177
178 public KVScannerComparator(KVComparator kvComparator) {
179 this.kvComparator = kvComparator;
180 }
181 public int compare(KeyValueScanner left, KeyValueScanner right) {
182 int comparison = compare(left.peek(), right.peek());
183 if (comparison != 0) {
184 return comparison;
185 } else {
186
187
188 long leftSequenceID = left.getSequenceID();
189 long rightSequenceID = right.getSequenceID();
190 if (leftSequenceID > rightSequenceID) {
191 return -1;
192 } else if (leftSequenceID < rightSequenceID) {
193 return 1;
194 } else {
195 return 0;
196 }
197 }
198 }
199
200
201
202
203
204
205 public int compare(KeyValue left, KeyValue right) {
206 return this.kvComparator.compare(left, right);
207 }
208
209
210
211 public KVComparator getComparator() {
212 return this.kvComparator;
213 }
214 }
215
216 public void close() {
217 if (this.current != null) {
218 this.current.close();
219 }
220 if (this.heap != null) {
221 KeyValueScanner scanner;
222 while ((scanner = this.heap.poll()) != null) {
223 scanner.close();
224 }
225 }
226 }
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243 @Override
244 public boolean seek(KeyValue seekKey) throws IOException {
245 return generalizedSeek(false,
246 seekKey,
247 false,
248 false);
249 }
250
251
252
253
254
255 @Override
256 public boolean reseek(KeyValue seekKey) throws IOException {
257 return generalizedSeek(false,
258 seekKey,
259 true,
260 false);
261 }
262
263
264
265
266 @Override
267 public boolean requestSeek(KeyValue key, boolean forward,
268 boolean useBloom) throws IOException {
269 return generalizedSeek(true, key, forward, useBloom);
270 }
271
272
273
274
275
276
277
278
279
280 private boolean generalizedSeek(boolean isLazy, KeyValue seekKey,
281 boolean forward, boolean useBloom) throws IOException {
282 if (!isLazy && useBloom) {
283 throw new IllegalArgumentException("Multi-column Bloom filter " +
284 "optimization requires a lazy seek");
285 }
286
287 if (current == null) {
288 return false;
289 }
290 heap.add(current);
291 current = null;
292
293 KeyValueScanner scanner;
294 while ((scanner = heap.poll()) != null) {
295 KeyValue topKey = scanner.peek();
296 if (comparator.getComparator().compare(seekKey, topKey) <= 0) {
297
298
299
300
301
302
303 heap.add(scanner);
304 current = pollRealKV();
305 return current != null;
306 }
307
308 boolean seekResult;
309 if (isLazy && heap.size() > 0) {
310
311 seekResult = scanner.requestSeek(seekKey, forward, useBloom);
312 } else {
313 seekResult = NonLazyKeyValueScanner.doRealSeek(
314 scanner, seekKey, forward);
315 }
316
317 if (!seekResult) {
318 scanner.close();
319 } else {
320 heap.add(scanner);
321 }
322 }
323
324
325 return false;
326 }
327
328
329
330
331
332
333
334
335
336
337
338
339 protected KeyValueScanner pollRealKV() throws IOException {
340 KeyValueScanner kvScanner = heap.poll();
341 if (kvScanner == null) {
342 return null;
343 }
344
345 while (kvScanner != null && !kvScanner.realSeekDone()) {
346 if (kvScanner.peek() != null) {
347 kvScanner.enforceSeek();
348 KeyValue curKV = kvScanner.peek();
349 if (curKV != null) {
350 KeyValueScanner nextEarliestScanner = heap.peek();
351 if (nextEarliestScanner == null) {
352
353 return kvScanner;
354 }
355
356
357
358 KeyValue nextKV = nextEarliestScanner.peek();
359 if (nextKV == null || comparator.compare(curKV, nextKV) < 0) {
360
361 return kvScanner;
362 }
363
364
365
366
367 heap.add(kvScanner);
368 } else {
369
370
371 kvScanner.close();
372 }
373 } else {
374
375
376 kvScanner.close();
377 }
378 kvScanner = heap.poll();
379 }
380
381 return kvScanner;
382 }
383
384
385
386
387 public PriorityQueue<KeyValueScanner> getHeap() {
388 return this.heap;
389 }
390
391 @Override
392 public long getSequenceID() {
393 return 0;
394 }
395
396 KeyValueScanner getCurrentForTesting() {
397 return current;
398 }
399 }