View Javadoc

1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
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   * A query matcher that is specifically designed for the scan case.
45   */
46  @InterfaceAudience.Private
47  public class ScanQueryMatcher {
48    // Optimization so we can skip lots of compares when we decide to skip
49    // to the next row.
50    private boolean stickyNextRow;
51    private final byte[] stopRow;
52  
53    private final TimeRange tr;
54  
55    private final Filter filter;
56  
57    /** Keeps track of deletes */
58    private final DeleteTracker deletes;
59  
60    /*
61     * The following three booleans define how we deal with deletes.
62     * There are three different aspects:
63     * 1. Whether to keep delete markers. This is used in compactions.
64     *    Minor compactions always keep delete markers.
65     * 2. Whether to keep deleted rows. This is also used in compactions,
66     *    if the store is set to keep deleted rows. This implies keeping
67     *    the delete markers as well.
68     *    In this case deleted rows are subject to the normal max version
69     *    and TTL/min version rules just like "normal" rows.
70     * 3. Whether a scan can do time travel queries even before deleted
71     *    marker to reach deleted rows.
72     */
73    /** whether to retain delete markers */
74    private boolean retainDeletesInOutput;
75  
76    /** whether to return deleted rows */
77    private final KeepDeletedCells keepDeletedCells;
78    /** whether time range queries can see rows "behind" a delete */
79    private final boolean seePastDeleteMarkers;
80  
81  
82    /** Keeps track of columns and versions */
83    private final ColumnTracker columns;
84  
85    /** Key to seek to in memstore and StoreFiles */
86    private final Cell startKey;
87  
88    /** Row comparator for the region this query is for */
89    private final KeyValue.KVComparator rowComparator;
90  
91    /* row is not private for tests */
92    /** Row the query is on */
93    byte [] row;
94    int rowOffset;
95    short rowLength;
96    
97    /**
98     * Oldest put in any of the involved store files
99     * Used to decide whether it is ok to delete
100    * family delete marker of this store keeps
101    * deleted KVs.
102    */
103   private final long earliestPutTs;
104   private final long ttl;
105 
106   /** The oldest timestamp we are interested in, based on TTL */
107   private final long oldestUnexpiredTS;
108   private final long now;
109 
110   /** readPoint over which the KVs are unconditionally included */
111   protected long maxReadPointToTrackVersions;
112 
113   private byte[] dropDeletesFromRow = null, dropDeletesToRow = null;
114 
115   /**
116    * This variable shows whether there is an null column in the query. There
117    * always exists a null column in the wildcard column query.
118    * There maybe exists a null column in the explicit column query based on the
119    * first column.
120    * */
121   private boolean hasNullColumn = true;
122   
123   private RegionCoprocessorHost regionCoprocessorHost= null;
124 
125   // By default, when hbase.hstore.time.to.purge.deletes is 0ms, a delete
126   // marker is always removed during a major compaction. If set to non-zero
127   // value then major compaction will try to keep a delete marker around for
128   // the given number of milliseconds. We want to keep the delete markers
129   // around a bit longer because old puts might appear out-of-order. For
130   // example, during log replication between two clusters.
131   //
132   // If the delete marker has lived longer than its column-family's TTL then
133   // the delete marker will be removed even if time.to.purge.deletes has not
134   // passed. This is because all the Puts that this delete marker can influence
135   // would have also expired. (Removing of delete markers on col family TTL will
136   // not happen if min-versions is set to non-zero)
137   //
138   // But, if time.to.purge.deletes has not expired then a delete
139   // marker will not be removed just because there are no Puts that it is
140   // currently influencing. This is because Puts, that this delete can
141   // influence.  may appear out of order.
142   private final long timeToPurgeDeletes;
143   
144   private final boolean isUserScan;
145 
146   private final boolean isReversed;
147 
148   /**
149    * Construct a QueryMatcher for a scan
150    * @param scan
151    * @param scanInfo The store's immutable scan info
152    * @param columns
153    * @param scanType Type of the scan
154    * @param earliestPutTs Earliest put seen in any of the store files.
155    * @param oldestUnexpiredTS the oldest timestamp we are interested in,
156    *  based on TTL
157    * @param regionCoprocessorHost 
158    * @throws IOException 
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     /* how to deal with deletes */
180     this.isUserScan = scanType == ScanType.USER_SCAN;
181     // keep deleted cells: if compaction or raw scan
182     this.keepDeletedCells = scan.isRaw() ? KeepDeletedCells.TRUE :
183       isUserScan ? KeepDeletedCells.FALSE : scanInfo.getKeepDeletedCells();
184     // retain deletes: if minor compaction or raw scanisDone
185     this.retainDeletesInOutput = scanType == ScanType.COMPACT_RETAIN_DELETES || scan.isRaw();
186     // seePastDeleteMarker: user initiated scans
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     // Single branch to deal with two types of reads (columns vs all in family)
195     if (columns == null || columns.size() == 0) {
196       // there is always a null column in the wildcard column query.
197       hasNullColumn = true;
198 
199       // use a specialized scan for wildcard column tracker.
200       this.columns = new ScanWildcardColumnTracker(
201           scanInfo.getMinVersions(), maxVersions, oldestUnexpiredTS);
202     } else {
203       // whether there is null column in the explicit column query
204       hasNullColumn = (columns.first().length == 0);
205 
206       // We can share the ExplicitColumnTracker, diff is we reset
207       // between rows, not between storefiles.
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    * Construct a QueryMatcher for a scan that drop deletes from a limited range of rows.
224    * @param scan
225    * @param scanInfo The store's immutable scan info
226    * @param columns
227    * @param earliestPutTs Earliest put seen in any of the store files.
228    * @param oldestUnexpiredTS the oldest timestamp we are interested in, based on TTL
229    * @param now the current server time
230    * @param dropDeletesFromRow The inclusive left bound of the range; can be EMPTY_START_ROW.
231    * @param dropDeletesToRow The exclusive right bound of the range; can be EMPTY_END_ROW.
232    * @param regionCoprocessorHost 
233    * @throws IOException 
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    * Constructor for tests
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, /* max Readpoint to track versions */
253         HConstants.LATEST_TIMESTAMP, oldestUnexpiredTS, now, null);
254   }
255 
256   /**
257    *
258    * @return  whether there is an null column in the query
259    */
260   public boolean hasNullColumnInQuery() {
261     return hasNullColumn;
262   }
263 
264   /**
265    * Determines if the caller should do one of several things:
266    * - seek/skip to the next row (MatchCode.SEEK_NEXT_ROW)
267    * - seek/skip to the next column (MatchCode.SEEK_NEXT_COL)
268    * - include the current KeyValue (MatchCode.INCLUDE)
269    * - ignore the current KeyValue (MatchCode.SKIP)
270    * - got to the next row (MatchCode.DONE)
271    *
272    * @param cell KeyValue to check
273    * @return The match code instance.
274    * @throws IOException in case there is an internal consistency problem
275    *      caused by a data corruption.
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           // could optimize this, if necessary?
289           // Could also be called SEEK_TO_CURRENT_ROW, but this
290           // should be rare/never happens.
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     // optimize case.
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     // check for early out based on timestamp alone
318     if (columns.isDone(timestamp)) {
319       return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
320           qualifierLength);
321     }
322     // check if the cell is expired by cell TTL
323     if (HStore.isCellTTLExpired(cell, this.oldestUnexpiredTS, this.now)) {
324       return MatchCode.SKIP;
325     }    
326 
327     /*
328      * The delete logic is pretty complicated now.
329      * This is corroborated by the following:
330      * 1. The store might be instructed to keep deleted rows around.
331      * 2. A scan can optionally see past a delete marker now.
332      * 3. If deleted rows are kept, we have to find out when we can
333      *    remove the delete markers.
334      * 4. Family delete markers are always first (regardless of their TS)
335      * 5. Delete markers should not be counted as version
336      * 6. Delete markers affect puts of the *same* TS
337      * 7. Delete marker need to be version counted together with puts
338      *    they affect
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         // first ignore delete markers if the scanner can do so, and the
346         // range does not include the marker
347         //
348         // during flushes and compactions also ignore delete markers newer
349         // than the readpoint of any open scanner, this prevents deleted
350         // rows that could still be seen by a scanner from being collected
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         // Can't early out now, because DelFam come before any other keys
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         // always include or it is not time yet to check whether it is OK
368         // to purge deltes or not
369         if (!isUserScan) {
370           // if this is not a user scan (compaction), we can filter this deletemarker right here
371           // otherwise (i.e. a "raw" scan) we fall through to normal version and timerange checking
372           return MatchCode.INCLUDE;
373         }
374       } else if (keepDeletedCells == KeepDeletedCells.TRUE
375           || (keepDeletedCells == KeepDeletedCells.TTL && timestamp >= ttl)) {
376         if (timestamp < earliestPutTs) {
377           // keeping delete rows, but there are no puts older than
378           // this delete in the store files.
379           return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
380               qualifierOffset, qualifierLength);
381         }
382         // else: fall through and do version counting on the
383         // delete markers
384       } else {
385         return MatchCode.SKIP;
386       }
387       // note the following next else if...
388       // delete marker are not subject to other delete markers
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     // STEP 1: Check if the column is part of the requested columns
415     MatchCode colChecker = columns.checkColumn(cell.getQualifierArray(), 
416         qualifierOffset, qualifierLength, typeByte);
417     if (colChecker == MatchCode.INCLUDE) {
418       ReturnCode filterResponse = ReturnCode.SKIP;
419       // STEP 2: Yes, the column is part of the requested columns. Check if filter is present
420       if (filter != null) {
421         // STEP 3: Filter the key value and return if it filters out
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           //It means it is either include or include and seek next
436           break;
437         }
438       }
439       /*
440        * STEP 4: Reaching this step means the column is part of the requested columns and either
441        * the filter is null or the filter has returned INCLUDE or INCLUDE_AND_NEXT_COL response.
442        * Now check the number of versions needed. This method call returns SKIP, INCLUDE,
443        * INCLUDE_AND_SEEK_NEXT_ROW, INCLUDE_AND_SEEK_NEXT_COL.
444        *
445        * FilterResponse            ColumnChecker               Desired behavior
446        * INCLUDE                   SKIP                        row has already been included, SKIP.
447        * INCLUDE                   INCLUDE                     INCLUDE
448        * INCLUDE                   INCLUDE_AND_SEEK_NEXT_COL   INCLUDE_AND_SEEK_NEXT_COL
449        * INCLUDE                   INCLUDE_AND_SEEK_NEXT_ROW   INCLUDE_AND_SEEK_NEXT_ROW
450        * INCLUDE_AND_SEEK_NEXT_COL SKIP                        row has already been included, SKIP.
451        * INCLUDE_AND_SEEK_NEXT_COL INCLUDE                     INCLUDE_AND_SEEK_NEXT_COL
452        * INCLUDE_AND_SEEK_NEXT_COL INCLUDE_AND_SEEK_NEXT_COL   INCLUDE_AND_SEEK_NEXT_COL
453        * INCLUDE_AND_SEEK_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW   INCLUDE_AND_SEEK_NEXT_ROW
454        *
455        * In all the above scenarios, we return the column checker return value except for
456        * FilterResponse (INCLUDE_AND_SEEK_NEXT_COL) and ColumnChecker(INCLUDE)
457        */
458       colChecker =
459           columns.checkVersions(cell.getQualifierArray(), qualifierOffset,
460               qualifierLength, timestamp, typeByte,
461             mvccVersion > maxReadPointToTrackVersions);
462       //Optimize with stickyNextRow
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   /** Handle partial-drop-deletes. As we match keys in order, when we have a range from which
474    * we can drop deletes, we can set retainDeletesInOutput to false for the duration of this
475    * range only, and maintain consistency. */
476   private void checkPartialDropDeleteRange(byte [] row, int offset, short length) {
477     // If partial-drop-deletes are used, initially, dropDeletesFromRow and dropDeletesToRow
478     // are both set, and the matcher is set to retain deletes. We assume ordered keys. When
479     // dropDeletesFromRow is leq current kv, we start dropping deletes and reset
480     // dropDeletesFromRow; thus the 2nd "if" starts to apply.
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     // If dropDeletesFromRow is null and dropDeletesToRow is set, we are inside the partial-
489     // drop-deletes range. When dropDeletesToRow is leq current kv, we stop dropping deletes,
490     // and reset dropDeletesToRow so that we don't do any more compares.
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       // KV >= STOPROW
513       // then NO there is nothing left.
514       return false;
515     } else {
516       return true;
517     }
518   }
519 
520   /**
521    * Set current row
522    * @param row
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    * @return the start key
542    */
543   public Cell getStartKey() {
544     return this.startKey;
545   }
546 
547   /**
548    *
549    * @return the Filter
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    * @param nextIndexed the key of the next entry in the block index (if any)
587    * @param kv The Cell we're using to calculate the seek key
588    * @return result of the compare between the indexed key and the key portion of the passed cell
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    * @param nextIndexed the key of the next entry in the block index (if any)
600    * @param kv The Cell we're using to calculate the seek key
601    * @return result of the compare between the indexed key and the key portion of the passed cell
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   //Used only for testing purposes
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    * {@link #match} return codes.  These instruct the scanner moving through
632    * memstores and StoreFiles what to do with the current KeyValue.
633    * <p>
634    * Additionally, this contains "early-out" language to tell the scanner to
635    * move on to the next File (memstore or Storefile), or to return immediately.
636    */
637   public static enum MatchCode {
638     /**
639      * Include KeyValue in the returned result
640      */
641     INCLUDE,
642 
643     /**
644      * Do not include KeyValue in the returned result
645      */
646     SKIP,
647 
648     /**
649      * Do not include, jump to next StoreFile or memstore (in time order)
650      */
651     NEXT,
652 
653     /**
654      * Do not include, return current result
655      */
656     DONE,
657 
658     /**
659      * These codes are used by the ScanQueryMatcher
660      */
661 
662     /**
663      * Done with the row, seek there.
664      */
665     SEEK_NEXT_ROW,
666     /**
667      * Done with column, seek to next.
668      */
669     SEEK_NEXT_COL,
670 
671     /**
672      * Done with scan, thanks to the row filter.
673      */
674     DONE_SCAN,
675 
676     /*
677      * Seek to next key which is given as hint.
678      */
679     SEEK_NEXT_USING_HINT,
680 
681     /**
682      * Include KeyValue and done with column, seek to next.
683      */
684     INCLUDE_AND_SEEK_NEXT_COL,
685 
686     /**
687      * Include KeyValue and done with row, seek to next.
688      */
689     INCLUDE_AND_SEEK_NEXT_ROW,
690   }
691 }