hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From zhang...@apache.org
Subject [3/4] hbase git commit: HBASE-16225 Refactor ScanQueryMatcher
Date Tue, 02 Aug 2016 06:08:08 GMT
http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java
index 02a4cae..975d3c7 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java
@@ -29,16 +29,17 @@ import java.util.concurrent.atomic.AtomicLong;
 
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
-import org.apache.hadoop.hbase.classification.InterfaceAudience;
 import org.apache.hadoop.hbase.Cell;
 import org.apache.hadoop.hbase.CellUtil;
 import org.apache.hadoop.hbase.HConstants;
 import org.apache.hadoop.hbase.KeyValue;
 import org.apache.hadoop.hbase.KeyValueUtil;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
 import org.apache.hadoop.hbase.client.Scan;
 import org.apache.hadoop.hbase.io.TimeRange;
 import org.apache.hadoop.hbase.io.hfile.HFileScanner;
 import org.apache.hadoop.hbase.regionserver.StoreFile.Reader;
+import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher;
 
 /**
  * KeyValueScanner adaptor over the Reader.  It also provides hooks into
@@ -58,49 +59,41 @@ public class StoreFileScanner implements KeyValueScanner {
   private boolean delayedReseek;
   private Cell delayedSeekKV;
 
-  private boolean enforceMVCC = false;
-  private boolean hasMVCCInfo = false;
+  private final boolean enforceMVCC;
+  private final boolean hasMVCCInfo;
   // A flag represents whether could stop skipping KeyValues for MVCC
   // if have encountered the next row. Only used for reversed scan
   private boolean stopSkippingKVsIfNextRow = false;
 
   private static AtomicLong seekCount;
 
-  private ScanQueryMatcher matcher;
+  private final boolean canOptimizeForNonNullColumn;
 
-  private long readPt;
+  private final long readPt;
 
   // Order of this scanner relative to other scanners when duplicate key-value is found.
   // Higher values means scanner has newer data.
-  private long scannerOrder;
+  private final long scannerOrder;
 
   /**
    * Implements a {@link KeyValueScanner} on top of the specified {@link HFileScanner}
    * @param useMVCC If true, scanner will filter out updates with MVCC larger than {@code readPt}.
    * @param readPt MVCC value to use to filter out the updates newer than this scanner.
    * @param hasMVCC Set to true if underlying store file reader has MVCC info.
+   * @param scannerOrder Order of the scanner relative to other scanners. See
+   *          {@link KeyValueScanner#getScannerOrder()}.
+   * @param canOptimizeForNonNullColumn {@code true} if we can make sure there is no null column,
+   *          otherwise {@code false}. This is a hint for optimization.
    */
   public StoreFileScanner(StoreFile.Reader reader, HFileScanner hfs, boolean useMVCC,
-      boolean hasMVCC, long readPt) {
-    this (reader, hfs, useMVCC, hasMVCC, readPt, 0);
-  }
-
-  /**
-   * Implements a {@link KeyValueScanner} on top of the specified {@link HFileScanner}
-   * @param useMVCC If true, scanner will filter out updates with MVCC larger than {@code readPt}.
-   * @param readPt MVCC value to use to filter out the updates newer than this scanner.
-   * @param hasMVCC Set to true if underlying store file reader has MVCC info.
-   * @param scannerOrder Order of the scanner relative to other scanners.
-   *   See {@link KeyValueScanner#getScannerOrder()}.
-   */
-  public StoreFileScanner(StoreFile.Reader reader, HFileScanner hfs, boolean useMVCC,
-      boolean hasMVCC, long readPt, long scannerOrder) {
+      boolean hasMVCC, long readPt, long scannerOrder, boolean canOptimizeForNonNullColumn) {
     this.readPt = readPt;
     this.reader = reader;
     this.hfs = hfs;
     this.enforceMVCC = useMVCC;
     this.hasMVCCInfo = hasMVCC;
     this.scannerOrder = scannerOrder;
+    this.canOptimizeForNonNullColumn = canOptimizeForNonNullColumn;
   }
 
   boolean isPrimaryReplica() {
@@ -130,24 +123,20 @@ public class StoreFileScanner implements KeyValueScanner {
   }
 
   /**
-   * Return an array of scanners corresponding to the given set of store files,
-   * And set the ScanQueryMatcher for each store file scanner for further
-   * optimization
+   * Return an array of scanners corresponding to the given set of store files, And set the
+   * ScanQueryMatcher for each store file scanner for further optimization
    */
-  public static List<StoreFileScanner> getScannersForStoreFiles(
-      Collection<StoreFile> files, boolean cacheBlocks, boolean usePread,
-      boolean isCompaction, boolean canUseDrop,
+  public static List<StoreFileScanner> getScannersForStoreFiles(Collection<StoreFile> files,
+      boolean cacheBlocks, boolean usePread, boolean isCompaction, boolean canUseDrop,
       ScanQueryMatcher matcher, long readPt, boolean isPrimaryReplica) throws IOException {
-    List<StoreFileScanner> scanners = new ArrayList<StoreFileScanner>(
-        files.size());
+    List<StoreFileScanner> scanners = new ArrayList<StoreFileScanner>(files.size());
     List<StoreFile> sorted_files = new ArrayList<>(files);
     Collections.sort(sorted_files, StoreFile.Comparators.SEQ_ID);
     for (int i = 0; i < sorted_files.size(); i++) {
       StoreFile.Reader r = sorted_files.get(i).createReader(canUseDrop);
       r.setReplicaStoreFile(isPrimaryReplica);
-      StoreFileScanner scanner = r.getStoreFileScanner(cacheBlocks, usePread,
-          isCompaction, readPt, i);
-      scanner.setScanQueryMatcher(matcher);
+      StoreFileScanner scanner = r.getStoreFileScanner(cacheBlocks, usePread, isCompaction, readPt,
+        i, matcher != null ? !matcher.hasNullColumnInQuery() : false);
       scanners.add(scanner);
     }
     return scanners;
@@ -367,12 +356,12 @@ public class StoreFileScanner implements KeyValueScanner {
         haveToSeek = reader.passesGeneralBloomFilter(kv.getRowArray(),
             kv.getRowOffset(), kv.getRowLength(), kv.getQualifierArray(),
             kv.getQualifierOffset(), kv.getQualifierLength());
-      } else if (this.matcher != null && !matcher.hasNullColumnInQuery() &&
-          ((CellUtil.isDeleteFamily(kv) || CellUtil.isDeleteFamilyVersion(kv)))) {
+      } else if (canOptimizeForNonNullColumn
+          && ((CellUtil.isDeleteFamily(kv) || CellUtil.isDeleteFamilyVersion(kv)))) {
         // if there is no such delete family kv in the store file,
         // then no need to seek.
-        haveToSeek = reader.passesDeleteFamilyBloomFilter(kv.getRowArray(),
-            kv.getRowOffset(), kv.getRowLength());
+        haveToSeek = reader.passesDeleteFamilyBloomFilter(kv.getRowArray(), kv.getRowOffset(),
+          kv.getRowLength());
       }
     }
 
@@ -441,10 +430,6 @@ public class StoreFileScanner implements KeyValueScanner {
     }
   }
 
-  public void setScanQueryMatcher(ScanQueryMatcher matcher) {
-    this.matcher = matcher;
-  }
-
   @Override
   public boolean isFileScanner() {
     return true;

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreScanner.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreScanner.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreScanner.java
index 4447556..c98af00 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreScanner.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreScanner.java
@@ -19,6 +19,8 @@
 
 package org.apache.hadoop.hbase.regionserver;
 
+import com.google.common.annotations.VisibleForTesting;
+
 import java.io.IOException;
 import java.io.InterruptedIOException;
 import java.util.ArrayList;
@@ -41,15 +43,17 @@ import org.apache.hadoop.hbase.client.IsolationLevel;
 import org.apache.hadoop.hbase.client.Scan;
 import org.apache.hadoop.hbase.executor.ExecutorService;
 import org.apache.hadoop.hbase.filter.Filter;
-import org.apache.hadoop.hbase.regionserver.ScanQueryMatcher.MatchCode;
 import org.apache.hadoop.hbase.regionserver.ScannerContext.LimitScope;
 import org.apache.hadoop.hbase.regionserver.ScannerContext.NextState;
 import org.apache.hadoop.hbase.regionserver.handler.ParallelSeekHandler;
 import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.regionserver.querymatcher.CompactionScanQueryMatcher;
+import org.apache.hadoop.hbase.regionserver.querymatcher.LegacyScanQueryMatcher;
+import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher;
+import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode;
+import org.apache.hadoop.hbase.regionserver.querymatcher.UserScanQueryMatcher;
 import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
 
-import com.google.common.annotations.VisibleForTesting;
-
 /**
  * Scanner scans both the memstore and the Store. Coalesce KeyValue stream
  * into List&lt;KeyValue&gt; for a single row.
@@ -176,6 +180,7 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
   protected void addCurrentScanners(List<? extends KeyValueScanner> scanners) {
     this.currentScanners.addAll(scanners);
   }
+
   /**
    * Opens a scanner across memstore, snapshot, and all StoreFiles. Assumes we
    * are not in a compaction.
@@ -192,9 +197,8 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
     if (columns != null && scan.isRaw()) {
       throw new DoNotRetryIOException("Cannot specify any column for a raw scan");
     }
-    matcher = new ScanQueryMatcher(scan, scanInfo, columns,
-        ScanType.USER_SCAN, Long.MAX_VALUE, HConstants.LATEST_TIMESTAMP,
-        oldestUnexpiredTS, now, store.getCoprocessorHost());
+    matcher = UserScanQueryMatcher.create(scan, scanInfo, columns, oldestUnexpiredTS, now,
+      store.getCoprocessorHost());
 
     this.store.addChangedReaderObserver(this);
 
@@ -263,13 +267,19 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
       List<? extends KeyValueScanner> scanners, ScanType scanType, long smallestReadPoint,
       long earliestPutTs, byte[] dropDeletesFromRow, byte[] dropDeletesToRow) throws IOException {
     this(store, scan, scanInfo, null,
-      ((HStore)store).getHRegion().getReadpoint(IsolationLevel.READ_COMMITTED), false);
-    if (dropDeletesFromRow == null) {
-      matcher = new ScanQueryMatcher(scan, scanInfo, null, scanType, smallestReadPoint,
-          earliestPutTs, oldestUnexpiredTS, now, store.getCoprocessorHost());
+        ((HStore) store).getHRegion().getReadpoint(IsolationLevel.READ_COMMITTED), false);
+    if (scan.hasFilter() || (scan.getStartRow() != null && scan.getStartRow().length > 0)
+        || (scan.getStopRow() != null && scan.getStopRow().length > 0)
+        || !scan.getTimeRange().isAllTime()) {
+      // use legacy query matcher since we do not consider the scan object in our code. Only used to
+      // keep compatibility for coprocessor.
+      matcher = LegacyScanQueryMatcher.create(scan, scanInfo, null, scanType, smallestReadPoint,
+        earliestPutTs, oldestUnexpiredTS, now, dropDeletesFromRow, dropDeletesToRow,
+        store.getCoprocessorHost());
     } else {
-      matcher = new ScanQueryMatcher(scan, scanInfo, null, smallestReadPoint, earliestPutTs,
-          oldestUnexpiredTS, now, dropDeletesFromRow, dropDeletesToRow, store.getCoprocessorHost());
+      matcher = CompactionScanQueryMatcher.create(scanInfo, scanType, smallestReadPoint,
+        earliestPutTs, oldestUnexpiredTS, now, dropDeletesFromRow, dropDeletesToRow,
+        store.getCoprocessorHost());
     }
 
     // Filter the list of scanners using Bloom filters, time range, TTL, etc.
@@ -302,18 +312,27 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
       0);
   }
 
-  private StoreScanner(final Scan scan, ScanInfo scanInfo,
-      ScanType scanType, final NavigableSet<byte[]> columns,
-      final List<KeyValueScanner> scanners, long earliestPutTs, long readPt)
-  throws IOException {
+  public StoreScanner(final Scan scan, ScanInfo scanInfo, ScanType scanType,
+      final NavigableSet<byte[]> columns, final List<KeyValueScanner> scanners, long earliestPutTs,
+      long readPt) throws IOException {
     this(null, scan, scanInfo, columns, readPt, scan.getCacheBlocks());
-    this.matcher = new ScanQueryMatcher(scan, scanInfo, columns, scanType,
-        Long.MAX_VALUE, earliestPutTs, oldestUnexpiredTS, now, null);
-
-    // In unit tests, the store could be null
-    if (this.store != null) {
-      this.store.addChangedReaderObserver(this);
+    if (scanType == ScanType.USER_SCAN) {
+      this.matcher = UserScanQueryMatcher.create(scan, scanInfo, columns, oldestUnexpiredTS, now,
+        null);
+    } else {
+      if (scan.hasFilter() || (scan.getStartRow() != null && scan.getStartRow().length > 0)
+          || (scan.getStopRow() != null && scan.getStopRow().length > 0)
+          || !scan.getTimeRange().isAllTime() || columns != null) {
+        // use legacy query matcher since we do not consider the scan object in our code. Only used
+        // to keep compatibility for coprocessor.
+        matcher = LegacyScanQueryMatcher.create(scan, scanInfo, columns, scanType, Long.MAX_VALUE,
+          earliestPutTs, oldestUnexpiredTS, now, null, null, store.getCoprocessorHost());
+      } else {
+        this.matcher = CompactionScanQueryMatcher.create(scanInfo, scanType, Long.MAX_VALUE,
+          earliestPutTs, oldestUnexpiredTS, now, null, null, null);
+      }
     }
+
     // Seek all scanners to the initial key
     seekScanners(scanners, matcher.getStartKey(), false, parallelSeekEnabled);
     addCurrentScanners(scanners);
@@ -487,16 +506,13 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
 
     // only call setRow if the row changes; avoids confusing the query matcher
     // if scanning intra-row
-    byte[] row = cell.getRowArray();
-    int offset = cell.getRowOffset();
-    short length = cell.getRowLength();
 
     // If no limits exists in the scope LimitScope.Between_Cells then we are sure we are changing
     // rows. Else it is possible we are still traversing the same row so we must perform the row
     // comparison.
-    if (!scannerContext.hasAnyLimit(LimitScope.BETWEEN_CELLS) || matcher.row == null) {
+    if (!scannerContext.hasAnyLimit(LimitScope.BETWEEN_CELLS) || matcher.currentRow() == null) {
       this.countPerRow = 0;
-      matcher.setRow(row, offset, length);
+      matcher.setToNewRow(cell);
     }
 
     // Clear progress away unless invoker has indicated it should be kept.
@@ -524,14 +540,13 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
 
       ScanQueryMatcher.MatchCode qcode = matcher.match(cell);
       qcode = optimize(qcode, cell);
-      switch(qcode) {
+      switch (qcode) {
         case INCLUDE:
         case INCLUDE_AND_SEEK_NEXT_ROW:
         case INCLUDE_AND_SEEK_NEXT_COL:
 
           Filter f = matcher.getFilter();
           if (f != null) {
-            // TODO convert Scan Query Matcher to be Cell instead of KV based ?
             cell = f.transformCell(cell);
           }
 
@@ -545,7 +560,7 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
             // Setting the matcher.row = null, will mean that after the subsequent seekToNextRow()
             // the heap.peek() will any way be in the next row. So the SQM.match(cell) need do
             // another compareRow to say the current row is DONE
-            matcher.row = null;
+            matcher.clearCurrentRow();
             seekToNextRow(cell);
             break LOOP;
           }
@@ -576,7 +591,7 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
             // Setting the matcher.row = null, will mean that after the subsequent seekToNextRow()
             // the heap.peek() will any way be in the next row. So the SQM.match(cell) need do
             // another compareRow to say the current row is DONE
-            matcher.row = null;
+            matcher.clearCurrentRow();
             seekToNextRow(cell);
           } else if (qcode == ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_COL) {
             seekAsDirection(matcher.getKeyForNextColumn(cell));
@@ -602,7 +617,7 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
           // We are sure that this row is done and we are in the next row.
           // So subsequent StoresScanner.next() call need not do another compare
           // and set the matcher.row
-          matcher.row = null;
+          matcher.clearCurrentRow();
           return scannerContext.setScannerState(NextState.MORE_VALUES).hasMoreValues();
 
         case DONE_SCAN:
@@ -618,7 +633,7 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
           // Setting the matcher.row = null, will mean that after the subsequent seekToNextRow()
           // the heap.peek() will any way be in the next row. So the SQM.match(cell) need do
           // another compareRow to say the current row is DONE
-          matcher.row = null;
+          matcher.clearCurrentRow();
           seekToNextRow(cell);
           break;
 
@@ -631,7 +646,6 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
           break;
 
         case SEEK_NEXT_USING_HINT:
-          // TODO convert resee to Cell?
           Cell nextKV = matcher.getNextKeyHint(cell);
           if (nextKV != null) {
             seekAsDirection(nextKV);
@@ -840,11 +854,12 @@ public class StoreScanner extends NonReversedNonLazyKeyValueScanner
     byte[] row = kv.getRowArray();
     int offset = kv.getRowOffset();
     short length = kv.getRowLength();
-    if ((matcher.row == null) || !Bytes.equals(row, offset, length, matcher.row,
-        matcher.rowOffset, matcher.rowLength)) {
+    Cell currentRow = matcher.currentRow();
+
+    if ((currentRow == null) || !Bytes.equals(row, offset, length, currentRow.getRowArray(),
+      currentRow.getRowOffset(), currentRow.getRowLength())) {
       this.countPerRow = 0;
-      matcher.reset();
-      matcher.setRow(row, offset, length);
+      matcher.setToNewRow(kv);
     }
   }
 

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnCount.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnCount.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnCount.java
new file mode 100644
index 0000000..10961a9
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnCount.java
@@ -0,0 +1,111 @@
+/**
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+
+/**
+ * Simple wrapper for a byte buffer and a counter.  Does not copy.
+ * <p>
+ * NOT thread-safe because it is not used in a multi-threaded context, yet.
+ */
+@InterfaceAudience.Private
+class ColumnCount {
+  private final byte [] bytes;
+  private final int offset;
+  private final int length;
+  private int count;
+
+  /**
+   * Constructor
+   * @param column the qualifier to count the versions for
+   */
+  public ColumnCount(byte [] column) {
+    this(column, 0);
+  }
+
+  /**
+   * Constructor
+   * @param column the qualifier to count the versions for
+   * @param count initial count
+   */
+  public ColumnCount(byte [] column, int count) {
+    this(column, 0, column.length, count);
+  }
+
+  /**
+   * Constuctor
+   * @param column the qualifier to count the versions for
+   * @param offset in the passed buffer where to start the qualifier from
+   * @param length of the qualifier
+   * @param count initial count
+   */
+  public ColumnCount(byte [] column, int offset, int length, int count) {
+    this.bytes = column;
+    this.offset = offset;
+    this.length = length;
+    this.count = count;
+  }
+
+  /**
+   * @return the buffer
+   */
+  public byte [] getBuffer(){
+    return this.bytes;
+  }
+
+  /**
+   * @return the offset
+   */
+  public int getOffset(){
+    return this.offset;
+  }
+
+  /**
+   * @return the length
+   */
+  public int getLength(){
+    return this.length;
+  }
+
+  /**
+   * Decrement the current version count
+   * @return current count
+   */
+  public int decrement() {
+    return --count;
+  }
+
+  /**
+   * Increment the current version count
+   * @return current count
+   */
+  public int increment() {
+    return ++count;
+  }
+
+  /**
+   * Set the current count to a new count
+   * @param count new count to set
+   */
+  public void setCount(int count) {
+    this.count = count;
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnTracker.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnTracker.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnTracker.java
new file mode 100644
index 0000000..8ac78ab
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ColumnTracker.java
@@ -0,0 +1,130 @@
+/**
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode;
+
+/**
+ * Implementing classes of this interface will be used for the tracking
+ * and enforcement of columns and numbers of versions and timeToLive during
+ * the course of a Get or Scan operation.
+ * <p>
+ * Currently there are two different types of Store/Family-level queries.
+ * <ul><li>{@link ExplicitColumnTracker} is used when the query specifies
+ * one or more column qualifiers to return in the family.</li>
+ * <li>{@link ScanWildcardColumnTracker} is used when no columns are
+ * explicitly specified.</li>
+ * </ul>
+ * <p>
+ * This class is utilized by {@link ScanQueryMatcher} mainly through two methods:
+ * <ul><li>{@link #checkColumn} is called when a Put satisfies all other
+ * conditions of the query.</li>
+ * <li>{@link #getNextRowOrNextColumn} is called whenever ScanQueryMatcher
+ * believes that the current column should be skipped (by timestamp, filter etc.)</li>
+ * </ul>
+ * <p>
+ * These two methods returns a
+ * {@link org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode}
+ * to define what action should be taken.
+ * <p>
+ * This class is NOT thread-safe as queries are never multi-threaded
+ */
+@InterfaceAudience.Private
+public interface ColumnTracker {
+
+  /**
+   * Checks if the column is present in the list of requested columns by returning the match code
+   * instance. It does not check against the number of versions for the columns asked for. To do the
+   * version check, one has to call {@link #checkVersions(byte[], int, int, long, byte, boolean)}
+   * method based on the return type (INCLUDE) of this method. The values that can be returned by
+   * this method are {@link MatchCode#INCLUDE}, {@link MatchCode#SEEK_NEXT_COL} and
+   * {@link MatchCode#SEEK_NEXT_ROW}.
+   * @param bytes
+   * @param offset
+   * @param length
+   * @param type The type of the KeyValue
+   * @return The match code instance.
+   * @throws IOException in case there is an internal consistency problem caused by a data
+   *           corruption.
+   */
+  ScanQueryMatcher.MatchCode checkColumn(byte[] bytes, int offset, int length, byte type)
+      throws IOException;
+
+  /**
+   * Keeps track of the number of versions for the columns asked for. It assumes that the user has
+   * already checked if the keyvalue needs to be included by calling the
+   * {@link #checkColumn(byte[], int, int, byte)} method. The enum values returned by this method
+   * are {@link MatchCode#SKIP}, {@link MatchCode#INCLUDE},
+   * {@link MatchCode#INCLUDE_AND_SEEK_NEXT_COL} and {@link MatchCode#INCLUDE_AND_SEEK_NEXT_ROW}.
+   * Implementations which include all the columns could just return {@link MatchCode#INCLUDE} in
+   * the {@link #checkColumn(byte[], int, int, byte)} method and perform all the operations in this
+   * checkVersions method.
+   * @param type the type of the key value (Put/Delete)
+   * @param ttl The timeToLive to enforce.
+   * @param ignoreCount indicates if the KV needs to be excluded while counting (used during
+   *          compactions. We only count KV's that are older than all the scanners' read points.)
+   * @return the scan query matcher match code instance
+   * @throws IOException in case there is an internal consistency problem caused by a data
+   *           corruption.
+   */
+  ScanQueryMatcher.MatchCode checkVersions(byte[] bytes, int offset, int length, long ttl,
+      byte type, boolean ignoreCount) throws IOException;
+  /**
+   * Resets the Matcher
+   */
+  void reset();
+
+  /**
+   *
+   * @return <code>true</code> when done.
+   */
+  boolean done();
+
+  /**
+   * Used by matcher and scan/get to get a hint of the next column
+   * to seek to after checkColumn() returns SKIP.  Returns the next interesting
+   * column we want, or NULL there is none (wildcard scanner).
+   *
+   * Implementations aren't required to return anything useful unless the most recent
+   * call was to checkColumn() and the return code was SKIP.  This is pretty implementation
+   * detail-y, but optimizations are like that.
+   *
+   * @return null, or a ColumnCount that we should seek to
+   */
+  ColumnCount getColumnHint();
+
+  /**
+   * Retrieve the MatchCode for the next row or column
+   */
+  MatchCode getNextRowOrNextColumn(
+    byte[] bytes, int offset, int qualLength
+  );
+
+  /**
+   * Give the tracker a chance to declare it's done based on only the timestamp
+   * to allow an early out.
+   *
+   * @param timestamp
+   * @return <code>true</code> to early out based on timestamp.
+   */
+  boolean isDone(long timestamp);
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/CompactionScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/CompactionScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/CompactionScanQueryMatcher.java
new file mode 100644
index 0000000..d3224dc
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/CompactionScanQueryMatcher.java
@@ -0,0 +1,119 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.HConstants;
+import org.apache.hadoop.hbase.KeepDeletedCells;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.filter.Filter;
+import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+import org.apache.hadoop.hbase.regionserver.ScanType;
+
+/**
+ * Query matcher for compaction.
+ */
+@InterfaceAudience.Private
+public abstract class CompactionScanQueryMatcher extends ScanQueryMatcher {
+
+  /** readPoint over which the KVs are unconditionally included */
+  protected final long maxReadPointToTrackVersions;
+
+  /** Keeps track of deletes */
+  protected final DeleteTracker deletes;
+
+  /** whether to return deleted rows */
+  protected final KeepDeletedCells keepDeletedCells;
+
+  protected CompactionScanQueryMatcher(ScanInfo scanInfo, DeleteTracker deletes,
+      long readPointToUse, long oldestUnexpiredTS, long now) {
+    super(HConstants.EMPTY_START_ROW, scanInfo,
+        new ScanWildcardColumnTracker(scanInfo.getMinVersions(), scanInfo.getMaxVersions(),
+            oldestUnexpiredTS),
+        oldestUnexpiredTS, now);
+    this.maxReadPointToTrackVersions = readPointToUse;
+    this.deletes = deletes;
+    this.keepDeletedCells = scanInfo.getKeepDeletedCells();
+  }
+
+  @Override
+  public boolean hasNullColumnInQuery() {
+    return true;
+  }
+
+  @Override
+  public boolean isUserScan() {
+    return false;
+  }
+
+  @Override
+  public boolean moreRowsMayExistAfter(Cell cell) {
+    return true;
+  }
+
+  @Override
+  public Filter getFilter() {
+    // no filter when compaction
+    return null;
+  }
+
+  @Override
+  public Cell getNextKeyHint(Cell cell) throws IOException {
+    // no filter, so no key hint.
+    return null;
+  }
+
+  @Override
+  protected void reset() {
+    deletes.reset();
+  }
+
+  protected final void trackDelete(Cell cell) {
+    // If keepDeletedCells is true, then we only remove cells by versions or TTL during
+    // compaction, so we do not need to track delete here.
+    // If keepDeletedCells is TTL and the delete marker is expired, then we can make sure that the
+    // minVerions is larger than 0(otherwise we will just return at preCheck). So here we still
+    // need to track the delete marker to see if it masks some cells.
+    if (keepDeletedCells == KeepDeletedCells.FALSE
+        || (keepDeletedCells == KeepDeletedCells.TTL && cell.getTimestamp() < oldestUnexpiredTS)) {
+      deletes.add(cell);
+    }
+  }
+
+  public static CompactionScanQueryMatcher create(ScanInfo scanInfo, ScanType scanType,
+      long readPointToUse, long earliestPutTs, long oldestUnexpiredTS, long now,
+      byte[] dropDeletesFromRow, byte[] dropDeletesToRow,
+      RegionCoprocessorHost regionCoprocessorHost) throws IOException {
+    DeleteTracker deleteTracker = instantiateDeleteTracker(regionCoprocessorHost);
+    if (dropDeletesFromRow == null) {
+      if (scanType == ScanType.COMPACT_RETAIN_DELETES) {
+        return new MinorCompactionScanQueryMatcher(scanInfo, deleteTracker, readPointToUse,
+            oldestUnexpiredTS, now);
+      } else {
+        return new MajorCompactionScanQueryMatcher(scanInfo, deleteTracker, readPointToUse,
+            earliestPutTs, oldestUnexpiredTS, now);
+      }
+    } else {
+      return new StripeCompactionScanQueryMatcher(scanInfo, deleteTracker, readPointToUse,
+          earliestPutTs, oldestUnexpiredTS, now, dropDeletesFromRow, dropDeletesToRow);
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DeleteTracker.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DeleteTracker.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DeleteTracker.java
new file mode 100644
index 0000000..4e1ba4e
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DeleteTracker.java
@@ -0,0 +1,101 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.Cell;
+
+/**
+ * This interface is used for the tracking and enforcement of Deletes during the course of a Get or
+ * Scan operation.
+ * <p>
+ * This class is utilized through three methods:
+ * <ul>
+ * <li>{@link #add} when encountering a Delete</li>
+ * <li>{@link #isDeleted} when checking if a Put KeyValue has been deleted</li>
+ * <li>{@link #update} when reaching the end of a StoreFile</li>
+ * </ul>
+ */
+@InterfaceAudience.Private
+public interface DeleteTracker {
+
+  /**
+   * Add the specified cell to the list of deletes to check against for this row operation.
+   * <p>
+   * This is called when a Delete is encountered in a StoreFile.
+   * @param cell - the delete cell
+   */
+  void add(Cell cell);
+
+  /**
+   * Check if the specified cell buffer has been deleted by a previously seen delete.
+   * @param cell - current cell to check if deleted by a previously seen delete
+   * @return deleteResult The result tells whether the KeyValue is deleted and why
+   */
+  DeleteResult isDeleted(Cell cell);
+
+  /**
+   * @return true if there are no current delete, false otherwise
+   */
+  boolean isEmpty();
+
+  /**
+   * Called at the end of every StoreFile.
+   * <p>
+   * Many optimized implementations of Trackers will require an update at when the end of each
+   * StoreFile is reached.
+   */
+  void update();
+
+  /**
+   * Called between rows.
+   * <p>
+   * This clears everything as if a new DeleteTracker was instantiated.
+   */
+  void reset();
+
+  /**
+   * Return codes for comparison of two Deletes.
+   * <p>
+   * The codes tell the merging function what to do.
+   * <p>
+   * INCLUDE means add the specified Delete to the merged list. NEXT means move to the next element
+   * in the specified list(s).
+   */
+  enum DeleteCompare {
+    INCLUDE_OLD_NEXT_OLD,
+    INCLUDE_OLD_NEXT_BOTH,
+    INCLUDE_NEW_NEXT_NEW,
+    INCLUDE_NEW_NEXT_BOTH,
+    NEXT_OLD,
+    NEXT_NEW
+  }
+
+  /**
+   * Returns codes for delete result. The codes tell the ScanQueryMatcher whether the kv is deleted
+   * and why. Based on the delete result, the ScanQueryMatcher will decide the next operation
+   */
+  enum DeleteResult {
+    FAMILY_DELETED, // The KeyValue is deleted by a delete family.
+    FAMILY_VERSION_DELETED, // The KeyValue is deleted by a delete family version.
+    COLUMN_DELETED, // The KeyValue is deleted by a delete column.
+    VERSION_DELETED, // The KeyValue is deleted by a version delete.
+    NOT_DELETED
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DropDeletesCompactionScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DropDeletesCompactionScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DropDeletesCompactionScanQueryMatcher.java
new file mode 100644
index 0000000..b20abee
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/DropDeletesCompactionScanQueryMatcher.java
@@ -0,0 +1,84 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.KeepDeletedCells;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+
+/**
+ * A query matcher for compaction which can drop delete markers.
+ */
+@InterfaceAudience.Private
+public abstract class DropDeletesCompactionScanQueryMatcher extends CompactionScanQueryMatcher {
+
+  /**
+   * By default, when hbase.hstore.time.to.purge.deletes is 0ms, a delete marker is always removed
+   * during a major compaction. If set to non-zero value then major compaction will try to keep a
+   * delete marker around for the given number of milliseconds. We want to keep the delete markers
+   * around a bit longer because old puts might appear out-of-order. For example, during log
+   * replication between two clusters.
+   * <p>
+   * If the delete marker has lived longer than its column-family's TTL then the delete marker will
+   * be removed even if time.to.purge.deletes has not passed. This is because all the Puts that this
+   * delete marker can influence would have also expired. (Removing of delete markers on col family
+   * TTL will not happen if min-versions is set to non-zero)
+   * <p>
+   * But, if time.to.purge.deletes has not expired then a delete marker will not be removed just
+   * because there are no Puts that it is currently influencing. This is because Puts, that this
+   * delete can influence. may appear out of order.
+   */
+  protected final long timeToPurgeDeletes;
+
+  /**
+   * Oldest put in any of the involved store files Used to decide whether it is ok to delete family
+   * delete marker of this store keeps deleted KVs.
+   */
+  protected final long earliestPutTs;
+
+  protected DropDeletesCompactionScanQueryMatcher(ScanInfo scanInfo, DeleteTracker deletes,
+      long readPointToUse, long earliestPutTs, long oldestUnexpiredTS, long now) {
+    super(scanInfo, deletes, readPointToUse, oldestUnexpiredTS, now);
+    this.timeToPurgeDeletes = scanInfo.getTimeToPurgeDeletes();
+    this.earliestPutTs = earliestPutTs;
+  }
+
+  protected final MatchCode tryDropDelete(Cell cell) {
+    long timestamp = cell.getTimestamp();
+    // If it is not the time to drop the delete marker, just return
+    if (timeToPurgeDeletes > 0 && now - timestamp <= timeToPurgeDeletes) {
+      return MatchCode.INCLUDE;
+    }
+    if (keepDeletedCells == KeepDeletedCells.TRUE
+        || (keepDeletedCells == KeepDeletedCells.TTL && timestamp >= oldestUnexpiredTS)) {
+      // If keepDeletedCell is true, or the delete marker is not expired yet, we should include it
+      // in version counting to see if we can drop it. The only exception is that, we can make
+      // sure that no put is older than this delete marker. And under this situation, all later
+      // cells of this column(must be delete markers) can be skipped.
+      if (timestamp < earliestPutTs) {
+        return columns.getNextRowOrNextColumn(cell.getQualifierArray(), cell.getQualifierOffset(),
+          cell.getQualifierLength());
+      } else {
+        return null;
+      }
+    } else {
+      return MatchCode.SKIP;
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ExplicitColumnTracker.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ExplicitColumnTracker.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ExplicitColumnTracker.java
new file mode 100644
index 0000000..b206055
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/ExplicitColumnTracker.java
@@ -0,0 +1,250 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+import java.util.NavigableSet;
+
+import org.apache.hadoop.hbase.CellUtil;
+import org.apache.hadoop.hbase.HConstants;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode;
+import org.apache.hadoop.hbase.util.Bytes;
+
+/**
+ * This class is used for the tracking and enforcement of columns and numbers of versions during the
+ * course of a Get or Scan operation, when explicit column qualifiers have been asked for in the
+ * query. With a little magic (see {@link ScanQueryMatcher}), we can use this matcher for both scans
+ * and gets. The main difference is 'next' and 'done' collapse for the scan case (since we see all
+ * columns in order), and we only reset between rows.
+ * <p>
+ * This class is utilized by {@link ScanQueryMatcher} mainly through two methods:
+ * <ul>
+ * <li>{@link #checkColumn} is called when a Put satisfies all other conditions of the query.</li>
+ * <li>{@link #getNextRowOrNextColumn} is called whenever ScanQueryMatcher believes that the current
+ * column should be skipped (by timestamp, filter etc.)</li>
+ * </ul>
+ * <p>
+ * These two methods returns a
+ * {@link org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode} to define
+ * what action should be taken.
+ * <p>
+ * This class is NOT thread-safe as queries are never multi-threaded
+ */
+@InterfaceAudience.Private
+public class ExplicitColumnTracker implements ColumnTracker {
+
+  private final int maxVersions;
+  private final int minVersions;
+
+  /**
+   * Contains the list of columns that the ExplicitColumnTracker is tracking. Each ColumnCount
+   * instance also tracks how many versions of the requested column have been returned.
+   */
+  private final ColumnCount[] columns;
+  private int index;
+  private ColumnCount column;
+  /**
+   * Keeps track of the latest timestamp included for current column. Used to eliminate duplicates.
+   */
+  private long latestTSOfCurrentColumn;
+  private long oldestStamp;
+
+  /**
+   * Default constructor.
+   * @param columns columns specified user in query
+   * @param minVersions minimum number of versions to keep
+   * @param maxVersions maximum versions to return per column
+   * @param oldestUnexpiredTS the oldest timestamp we are interested in, based on TTL
+   */
+  public ExplicitColumnTracker(NavigableSet<byte[]> columns, int minVersions, int maxVersions,
+      long oldestUnexpiredTS) {
+    this.maxVersions = maxVersions;
+    this.minVersions = minVersions;
+    this.oldestStamp = oldestUnexpiredTS;
+    this.columns = new ColumnCount[columns.size()];
+    int i = 0;
+    for (byte[] column : columns) {
+      this.columns[i++] = new ColumnCount(column);
+    }
+    reset();
+  }
+
+  /**
+   * Done when there are no more columns to match against.
+   */
+  public boolean done() {
+    return this.index >= columns.length;
+  }
+
+  public ColumnCount getColumnHint() {
+    return this.column;
+  }
+
+  /**
+   * {@inheritDoc}
+   */
+  @Override
+  public ScanQueryMatcher.MatchCode checkColumn(byte[] bytes, int offset, int length, byte type) {
+    // delete markers should never be passed to an
+    // *Explicit*ColumnTracker
+    assert !CellUtil.isDelete(type);
+    do {
+      // No more columns left, we are done with this query
+      if (done()) {
+        return ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW; // done_row
+      }
+
+      // No more columns to match against, done with storefile
+      if (this.column == null) {
+        return ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW; // done_row
+      }
+
+      // Compare specific column to current column
+      int ret = Bytes.compareTo(column.getBuffer(), column.getOffset(), column.getLength(), bytes,
+        offset, length);
+
+      // Column Matches. Return include code. The caller would call checkVersions
+      // to limit the number of versions.
+      if (ret == 0) {
+        return ScanQueryMatcher.MatchCode.INCLUDE;
+      }
+
+      resetTS();
+
+      if (ret > 0) {
+        // The current KV is smaller than the column the ExplicitColumnTracker
+        // is interested in, so seek to that column of interest.
+        return ScanQueryMatcher.MatchCode.SEEK_NEXT_COL;
+      }
+
+      // The current KV is bigger than the column the ExplicitColumnTracker
+      // is interested in. That means there is no more data for the column
+      // of interest. Advance the ExplicitColumnTracker state to next
+      // column of interest, and check again.
+      if (ret <= -1) {
+        ++this.index;
+        if (done()) {
+          // No more to match, do not include, done with this row.
+          return ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW; // done_row
+        }
+        // This is the recursive case.
+        this.column = this.columns[this.index];
+      }
+    } while (true);
+  }
+
+  @Override
+  public ScanQueryMatcher.MatchCode checkVersions(byte[] bytes, int offset, int length,
+      long timestamp, byte type, boolean ignoreCount) throws IOException {
+    assert !CellUtil.isDelete(type);
+    if (ignoreCount) {
+      return ScanQueryMatcher.MatchCode.INCLUDE;
+    }
+    // Check if it is a duplicate timestamp
+    if (sameAsPreviousTS(timestamp)) {
+      // If duplicate, skip this Key
+      return ScanQueryMatcher.MatchCode.SKIP;
+    }
+    int count = this.column.increment();
+    if (count >= maxVersions || (count >= minVersions && isExpired(timestamp))) {
+      // Done with versions for this column
+      ++this.index;
+      resetTS();
+      if (done()) {
+        // We have served all the requested columns.
+        this.column = null;
+        return ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
+      }
+      // We are done with current column; advance to next column
+      // of interest.
+      this.column = this.columns[this.index];
+      return ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_COL;
+    }
+    setTS(timestamp);
+    return ScanQueryMatcher.MatchCode.INCLUDE;
+  }
+
+  // Called between every row.
+  public void reset() {
+    this.index = 0;
+    this.column = this.columns[this.index];
+    for (ColumnCount col : this.columns) {
+      col.setCount(0);
+    }
+    resetTS();
+  }
+
+  private void resetTS() {
+    latestTSOfCurrentColumn = HConstants.LATEST_TIMESTAMP;
+  }
+
+  private void setTS(long timestamp) {
+    latestTSOfCurrentColumn = timestamp;
+  }
+
+  private boolean sameAsPreviousTS(long timestamp) {
+    return timestamp == latestTSOfCurrentColumn;
+  }
+
+  private boolean isExpired(long timestamp) {
+    return timestamp < oldestStamp;
+  }
+
+  /**
+   * This method is used to inform the column tracker that we are done with this column. We may get
+   * this information from external filters or timestamp range and we then need to indicate this
+   * information to tracker. It is required only in case of ExplicitColumnTracker.
+   * @param bytes
+   * @param offset
+   * @param length
+   */
+  public void doneWithColumn(byte[] bytes, int offset, int length) {
+    while (this.column != null) {
+      int compare = Bytes.compareTo(column.getBuffer(), column.getOffset(), column.getLength(),
+        bytes, offset, length);
+      resetTS();
+      if (compare <= 0) {
+        ++this.index;
+        if (done()) {
+          // Will not hit any more columns in this storefile
+          this.column = null;
+        } else {
+          this.column = this.columns[this.index];
+        }
+        if (compare <= -1) {
+          continue;
+        }
+      }
+      return;
+    }
+  }
+
+  public MatchCode getNextRowOrNextColumn(byte[] bytes, int offset, int qualLength) {
+    doneWithColumn(bytes, offset, qualLength);
+    if (getColumnHint() == null) {
+      return MatchCode.SEEK_NEXT_ROW;
+    } else {
+      return MatchCode.SEEK_NEXT_COL;
+    }
+  }
+
+  public boolean isDone(long timestamp) {
+    return minVersions <= 0 && isExpired(timestamp);
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/LegacyScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/LegacyScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/LegacyScanQueryMatcher.java
new file mode 100644
index 0000000..46c29c5
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/LegacyScanQueryMatcher.java
@@ -0,0 +1,399 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import com.google.common.base.Preconditions;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.NavigableSet;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellUtil;
+import org.apache.hadoop.hbase.HConstants;
+import org.apache.hadoop.hbase.KeepDeletedCells;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.client.Scan;
+import org.apache.hadoop.hbase.filter.Filter;
+import org.apache.hadoop.hbase.filter.Filter.ReturnCode;
+import org.apache.hadoop.hbase.io.TimeRange;
+import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+import org.apache.hadoop.hbase.regionserver.ScanType;
+import org.apache.hadoop.hbase.regionserver.querymatcher.DeleteTracker.DeleteResult;
+import org.apache.hadoop.hbase.util.Bytes;
+import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
+
+/**
+ * The old query matcher implementation. Used to keep compatibility for coprocessor that could
+ * overwrite the StoreScanner before compaction. Should be removed once we find a better way to do
+ * filtering during compaction.
+ */
+@Deprecated
+@InterfaceAudience.Private
+public class LegacyScanQueryMatcher extends ScanQueryMatcher {
+
+  private final TimeRange tr;
+
+  private final Filter filter;
+
+  /** Keeps track of deletes */
+  private final DeleteTracker deletes;
+
+  /**
+   * The following three booleans define how we deal with deletes. There are three different
+   * aspects:
+   * <ol>
+   * <li>Whether to keep delete markers. This is used in compactions. Minor compactions always keep
+   * delete markers.</li>
+   * <li>Whether to keep deleted rows. This is also used in compactions, if the store is set to keep
+   * deleted rows. This implies keeping the delete markers as well.</li> In this case deleted rows
+   * are subject to the normal max version and TTL/min version rules just like "normal" rows.
+   * <li>Whether a scan can do time travel queries even before deleted marker to reach deleted
+   * rows.</li>
+   * </ol>
+   */
+  /** whether to retain delete markers */
+  private boolean retainDeletesInOutput;
+
+  /** whether to return deleted rows */
+  private final KeepDeletedCells keepDeletedCells;
+
+  // By default, when hbase.hstore.time.to.purge.deletes is 0ms, a delete
+  // marker is always removed during a major compaction. If set to non-zero
+  // value then major compaction will try to keep a delete marker around for
+  // the given number of milliseconds. We want to keep the delete markers
+  // around a bit longer because old puts might appear out-of-order. For
+  // example, during log replication between two clusters.
+  //
+  // If the delete marker has lived longer than its column-family's TTL then
+  // the delete marker will be removed even if time.to.purge.deletes has not
+  // passed. This is because all the Puts that this delete marker can influence
+  // would have also expired. (Removing of delete markers on col family TTL will
+  // not happen if min-versions is set to non-zero)
+  //
+  // But, if time.to.purge.deletes has not expired then a delete
+  // marker will not be removed just because there are no Puts that it is
+  // currently influencing. This is because Puts, that this delete can
+  // influence. may appear out of order.
+  private final long timeToPurgeDeletes;
+
+  /**
+   * This variable shows whether there is an null column in the query. There always exists a null
+   * column in the wildcard column query. There maybe exists a null column in the explicit column
+   * query based on the first column.
+   */
+  private final boolean hasNullColumn;
+
+  /** readPoint over which the KVs are unconditionally included */
+  private final long maxReadPointToTrackVersions;
+
+  /**
+   * Oldest put in any of the involved store files Used to decide whether it is ok to delete family
+   * delete marker of this store keeps deleted KVs.
+   */
+  protected final long earliestPutTs;
+
+  private final byte[] stopRow;
+
+  private byte[] dropDeletesFromRow = null, dropDeletesToRow = null;
+
+  private LegacyScanQueryMatcher(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
+      boolean hasNullColumn, DeleteTracker deletes, ScanType scanType, long readPointToUse,
+      long earliestPutTs, long oldestUnexpiredTS, long now) {
+    super(scan.getStartRow(), scanInfo, columns, oldestUnexpiredTS, now);
+    TimeRange timeRange = scan.getColumnFamilyTimeRange().get(scanInfo.getFamily());
+    if (timeRange == null) {
+      this.tr = scan.getTimeRange();
+    } else {
+      this.tr = timeRange;
+    }
+    this.hasNullColumn = hasNullColumn;
+    this.deletes = deletes;
+    this.filter = scan.getFilter();
+    this.maxReadPointToTrackVersions = readPointToUse;
+    this.timeToPurgeDeletes = scanInfo.getTimeToPurgeDeletes();
+    this.earliestPutTs = earliestPutTs;
+
+    /* how to deal with deletes */
+    this.keepDeletedCells = scanInfo.getKeepDeletedCells();
+    this.retainDeletesInOutput = scanType == ScanType.COMPACT_RETAIN_DELETES;
+    this.stopRow = scan.getStopRow();
+  }
+
+  private LegacyScanQueryMatcher(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
+      boolean hasNullColumn, DeleteTracker deletes, ScanType scanType, long readPointToUse,
+      long earliestPutTs, long oldestUnexpiredTS, long now, byte[] dropDeletesFromRow,
+      byte[] dropDeletesToRow) {
+    this(scan, scanInfo, columns, hasNullColumn, deletes, scanType, readPointToUse, earliestPutTs,
+        oldestUnexpiredTS, now);
+    this.dropDeletesFromRow = Preconditions.checkNotNull(dropDeletesFromRow);
+    this.dropDeletesToRow = Preconditions.checkNotNull(dropDeletesToRow);
+  }
+
+  @Override
+  public MatchCode match(Cell cell) throws IOException {
+    if (filter != null && filter.filterAllRemaining()) {
+      return MatchCode.DONE_SCAN;
+    }
+    MatchCode returnCode = preCheck(cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    /*
+     * The delete logic is pretty complicated now.
+     * This is corroborated by the following:
+     * 1. The store might be instructed to keep deleted rows around.
+     * 2. A scan can optionally see past a delete marker now.
+     * 3. If deleted rows are kept, we have to find out when we can
+     *    remove the delete markers.
+     * 4. Family delete markers are always first (regardless of their TS)
+     * 5. Delete markers should not be counted as version
+     * 6. Delete markers affect puts of the *same* TS
+     * 7. Delete marker need to be version counted together with puts
+     *    they affect
+     */
+    long timestamp = cell.getTimestamp();
+    byte typeByte = cell.getTypeByte();
+    long mvccVersion = cell.getSequenceId();
+    int qualifierOffset = cell.getQualifierOffset();
+    int qualifierLength = cell.getQualifierLength();
+    if (CellUtil.isDelete(cell)) {
+      if (keepDeletedCells == KeepDeletedCells.FALSE
+          || (keepDeletedCells == KeepDeletedCells.TTL && timestamp < oldestUnexpiredTS)) {
+        // first ignore delete markers if the scanner can do so, and the
+        // range does not include the marker
+        //
+        // during flushes and compactions also ignore delete markers newer
+        // than the readpoint of any open scanner, this prevents deleted
+        // rows that could still be seen by a scanner from being collected
+        boolean includeDeleteMarker = tr.withinOrAfterTimeRange(timestamp);
+        if (includeDeleteMarker && mvccVersion <= maxReadPointToTrackVersions) {
+          this.deletes.add(cell);
+        }
+        // Can't early out now, because DelFam come before any other keys
+      }
+
+      if (timeToPurgeDeletes > 0
+          && (EnvironmentEdgeManager.currentTime() - timestamp) <= timeToPurgeDeletes) {
+        return MatchCode.INCLUDE;
+      } else if (retainDeletesInOutput || mvccVersion > maxReadPointToTrackVersions) {
+        // always include or it is not time yet to check whether it is OK
+        // to purge deltes or not
+        // if this is not a user scan (compaction), we can filter this deletemarker right here
+        // otherwise (i.e. a "raw" scan) we fall through to normal version and timerange checking
+        return MatchCode.INCLUDE;
+      } else if (keepDeletedCells == KeepDeletedCells.TRUE
+          || (keepDeletedCells == KeepDeletedCells.TTL && timestamp >= oldestUnexpiredTS)) {
+        if (timestamp < earliestPutTs) {
+          // keeping delete rows, but there are no puts older than
+          // this delete in the store files.
+          return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
+            qualifierLength);
+        }
+        // else: fall through and do version counting on the
+        // delete markers
+      } else {
+        return MatchCode.SKIP;
+      }
+      // note the following next else if...
+      // delete marker are not subject to other delete markers
+    } else if (!this.deletes.isEmpty()) {
+      DeleteResult deleteResult = deletes.isDeleted(cell);
+      switch (deleteResult) {
+        case FAMILY_DELETED:
+        case COLUMN_DELETED:
+          return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
+            qualifierLength);
+        case VERSION_DELETED:
+        case FAMILY_VERSION_DELETED:
+          return MatchCode.SKIP;
+        case NOT_DELETED:
+          break;
+        default:
+          throw new RuntimeException("UNEXPECTED");
+        }
+    }
+
+    int timestampComparison = tr.compare(timestamp);
+    if (timestampComparison >= 1) {
+      return MatchCode.SKIP;
+    } else if (timestampComparison <= -1) {
+      return columns.getNextRowOrNextColumn(cell.getQualifierArray(), qualifierOffset,
+        qualifierLength);
+    }
+
+    // STEP 1: Check if the column is part of the requested columns
+    MatchCode colChecker = columns.checkColumn(cell.getQualifierArray(),
+      qualifierOffset, qualifierLength, typeByte);
+    if (colChecker == MatchCode.INCLUDE) {
+      ReturnCode filterResponse = ReturnCode.SKIP;
+      // STEP 2: Yes, the column is part of the requested columns. Check if filter is present
+      if (filter != null) {
+        // STEP 3: Filter the key value and return if it filters out
+        filterResponse = filter.filterKeyValue(cell);
+        switch (filterResponse) {
+        case SKIP:
+          return MatchCode.SKIP;
+        case NEXT_COL:
+          return columns.getNextRowOrNextColumn(cell.getQualifierArray(),
+            qualifierOffset, qualifierLength);
+        case NEXT_ROW:
+          stickyNextRow = true;
+          return MatchCode.SEEK_NEXT_ROW;
+        case SEEK_NEXT_USING_HINT:
+          return MatchCode.SEEK_NEXT_USING_HINT;
+        default:
+          //It means it is either include or include and seek next
+          break;
+        }
+      }
+      /*
+       * STEP 4: Reaching this step means the column is part of the requested columns and either
+       * the filter is null or the filter has returned INCLUDE or INCLUDE_AND_NEXT_COL response.
+       * Now check the number of versions needed. This method call returns SKIP, INCLUDE,
+       * INCLUDE_AND_SEEK_NEXT_ROW, INCLUDE_AND_SEEK_NEXT_COL.
+       *
+       * FilterResponse            ColumnChecker               Desired behavior
+       * INCLUDE                   SKIP                        row has already been included, SKIP.
+       * INCLUDE                   INCLUDE                     INCLUDE
+       * INCLUDE                   INCLUDE_AND_SEEK_NEXT_COL   INCLUDE_AND_SEEK_NEXT_COL
+       * INCLUDE                   INCLUDE_AND_SEEK_NEXT_ROW   INCLUDE_AND_SEEK_NEXT_ROW
+       * INCLUDE_AND_SEEK_NEXT_COL SKIP                        row has already been included, SKIP.
+       * INCLUDE_AND_SEEK_NEXT_COL INCLUDE                     INCLUDE_AND_SEEK_NEXT_COL
+       * INCLUDE_AND_SEEK_NEXT_COL INCLUDE_AND_SEEK_NEXT_COL   INCLUDE_AND_SEEK_NEXT_COL
+       * INCLUDE_AND_SEEK_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW   INCLUDE_AND_SEEK_NEXT_ROW
+       *
+       * In all the above scenarios, we return the column checker return value except for
+       * FilterResponse (INCLUDE_AND_SEEK_NEXT_COL) and ColumnChecker(INCLUDE)
+       */
+      colChecker =
+          columns.checkVersions(cell.getQualifierArray(), qualifierOffset,
+              qualifierLength, timestamp, typeByte,
+            mvccVersion > maxReadPointToTrackVersions);
+      // Optimize with stickyNextRow
+      stickyNextRow = colChecker == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW ? true : stickyNextRow;
+      return (filterResponse == ReturnCode.INCLUDE_AND_NEXT_COL &&
+          colChecker == MatchCode.INCLUDE) ? MatchCode.INCLUDE_AND_SEEK_NEXT_COL
+          : colChecker;
+    }
+    stickyNextRow = (colChecker == MatchCode.SEEK_NEXT_ROW) ? true
+        : stickyNextRow;
+    return colChecker;
+  }
+
+  @Override
+  public boolean hasNullColumnInQuery() {
+    return hasNullColumn;
+  }
+
+  /**
+   * Handle partial-drop-deletes. As we match keys in order, when we have a range from which we can
+   * drop deletes, we can set retainDeletesInOutput to false for the duration of this range only,
+   * and maintain consistency.
+   */
+  private void checkPartialDropDeleteRange(Cell curCell) {
+    byte[] rowArray = curCell.getRowArray();
+    int rowOffset = curCell.getRowOffset();
+    short rowLength = curCell.getRowLength();
+    // If partial-drop-deletes are used, initially, dropDeletesFromRow and dropDeletesToRow
+    // are both set, and the matcher is set to retain deletes. We assume ordered keys. When
+    // dropDeletesFromRow is leq current kv, we start dropping deletes and reset
+    // dropDeletesFromRow; thus the 2nd "if" starts to apply.
+    if ((dropDeletesFromRow != null)
+        && (Arrays.equals(dropDeletesFromRow, HConstants.EMPTY_START_ROW)
+            || (Bytes.compareTo(rowArray, rowOffset, rowLength, dropDeletesFromRow, 0,
+              dropDeletesFromRow.length) >= 0))) {
+      retainDeletesInOutput = false;
+      dropDeletesFromRow = null;
+    }
+    // If dropDeletesFromRow is null and dropDeletesToRow is set, we are inside the partial-
+    // drop-deletes range. When dropDeletesToRow is leq current kv, we stop dropping deletes,
+    // and reset dropDeletesToRow so that we don't do any more compares.
+    if ((dropDeletesFromRow == null) && (dropDeletesToRow != null)
+        && !Arrays.equals(dropDeletesToRow, HConstants.EMPTY_END_ROW) && (Bytes.compareTo(rowArray,
+          rowOffset, rowLength, dropDeletesToRow, 0, dropDeletesToRow.length) >= 0)) {
+      retainDeletesInOutput = true;
+      dropDeletesToRow = null;
+    }
+  }
+
+  @Override
+  protected void reset() {
+    checkPartialDropDeleteRange(currentRow);
+  }
+
+  @Override
+  public boolean isUserScan() {
+    return false;
+  }
+
+  @Override
+  public boolean moreRowsMayExistAfter(Cell cell) {
+    if (this.stopRow == null || this.stopRow.length == 0) {
+      return true;
+    }
+    return rowComparator.compareRows(cell, stopRow, 0, stopRow.length) < 0;
+  }
+
+  @Override
+  public Filter getFilter() {
+    return filter;
+  }
+
+  @Override
+  public Cell getNextKeyHint(Cell cell) throws IOException {
+    if (filter == null) {
+      return null;
+    } else {
+      return filter.getNextCellHint(cell);
+    }
+  }
+
+  public static LegacyScanQueryMatcher create(Scan scan, ScanInfo scanInfo,
+      NavigableSet<byte[]> columns, ScanType scanType, long readPointToUse, long earliestPutTs,
+      long oldestUnexpiredTS, long now, byte[] dropDeletesFromRow, byte[] dropDeletesToRow,
+      RegionCoprocessorHost regionCoprocessorHost) throws IOException {
+    int maxVersions = Math.min(scan.getMaxVersions(), scanInfo.getMaxVersions());
+    boolean hasNullColumn;
+    ColumnTracker columnTracker;
+    if (columns == null || columns.size() == 0) {
+      // there is always a null column in the wildcard column query.
+      hasNullColumn = true;
+      // use a specialized scan for wildcard column tracker.
+      columnTracker = new ScanWildcardColumnTracker(scanInfo.getMinVersions(), maxVersions,
+          oldestUnexpiredTS);
+    } else {
+      // We can share the ExplicitColumnTracker, diff is we reset
+      // between rows, not between storefiles.
+      // whether there is null column in the explicit column query
+      hasNullColumn = columns.first().length == 0;
+      columnTracker = new ExplicitColumnTracker(columns, scanInfo.getMinVersions(), maxVersions,
+          oldestUnexpiredTS);
+    }
+    DeleteTracker deletes = instantiateDeleteTracker(regionCoprocessorHost);
+    if (dropDeletesFromRow == null) {
+      return new LegacyScanQueryMatcher(scan, scanInfo, columnTracker, hasNullColumn, deletes,
+          scanType, readPointToUse, earliestPutTs, oldestUnexpiredTS, now);
+    } else {
+      return new LegacyScanQueryMatcher(scan, scanInfo, columnTracker, hasNullColumn, deletes,
+          scanType, readPointToUse, earliestPutTs, oldestUnexpiredTS, now, dropDeletesFromRow,
+          dropDeletesToRow);
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MajorCompactionScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MajorCompactionScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MajorCompactionScanQueryMatcher.java
new file mode 100644
index 0000000..e3bc924
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MajorCompactionScanQueryMatcher.java
@@ -0,0 +1,81 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellUtil;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+
+/**
+ * Query matcher for major compaction.
+ */
+@InterfaceAudience.Private
+public class MajorCompactionScanQueryMatcher extends DropDeletesCompactionScanQueryMatcher {
+
+  public MajorCompactionScanQueryMatcher(ScanInfo scanInfo, DeleteTracker deletes,
+      long readPointToUse, long earliestPutTs, long oldestUnexpiredTS, long now) {
+    super(scanInfo, deletes, readPointToUse, earliestPutTs, oldestUnexpiredTS, now);
+  }
+
+  @Override
+  public MatchCode match(Cell cell) throws IOException {
+    MatchCode returnCode = preCheck(cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    long timestamp = cell.getTimestamp();
+    long mvccVersion = cell.getSequenceId();
+
+    // The delete logic is pretty complicated now.
+    // This is corroborated by the following:
+    // 1. The store might be instructed to keep deleted rows around.
+    // 2. A scan can optionally see past a delete marker now.
+    // 3. If deleted rows are kept, we have to find out when we can
+    // remove the delete markers.
+    // 4. Family delete markers are always first (regardless of their TS)
+    // 5. Delete markers should not be counted as version
+    // 6. Delete markers affect puts of the *same* TS
+    // 7. Delete marker need to be version counted together with puts
+    // they affect
+    //
+    if (CellUtil.isDelete(cell)) {
+      if (mvccVersion > maxReadPointToTrackVersions) {
+        // We can not drop this delete marker yet, and also we should not use this delete marker to
+        // mask any cell yet.
+        return MatchCode.INCLUDE;
+      }
+      trackDelete(cell);
+      returnCode = tryDropDelete(cell);
+      if (returnCode != null) {
+        return returnCode;
+      }
+    } else {
+      returnCode = checkDeleted(deletes, cell);
+      if (returnCode != null) {
+        return returnCode;
+      }
+    }
+    // Skip checking column since we do not remove column during compaction.
+    return columns.checkVersions(cell.getQualifierArray(), cell.getQualifierOffset(),
+      cell.getQualifierLength(), timestamp, cell.getTypeByte(),
+      mvccVersion > maxReadPointToTrackVersions);
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MinorCompactionScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MinorCompactionScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MinorCompactionScanQueryMatcher.java
new file mode 100644
index 0000000..4ba3293
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/MinorCompactionScanQueryMatcher.java
@@ -0,0 +1,62 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellUtil;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+
+/**
+ * Query matcher for minor compaction.
+ */
+@InterfaceAudience.Private
+public class MinorCompactionScanQueryMatcher extends CompactionScanQueryMatcher {
+
+  public MinorCompactionScanQueryMatcher(ScanInfo scanInfo, DeleteTracker deletes,
+      long readPointToUse, long oldestUnexpiredTS, long now) {
+    super(scanInfo, deletes, readPointToUse, oldestUnexpiredTS, now);
+  }
+
+  @Override
+  public MatchCode match(Cell cell) throws IOException {
+    MatchCode returnCode = preCheck(cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    long mvccVersion = cell.getSequenceId();
+    if (CellUtil.isDelete(cell)) {
+      if (mvccVersion > maxReadPointToTrackVersions) {
+        // we should not use this delete marker to mask any cell yet.
+        return MatchCode.INCLUDE;
+      }
+      trackDelete(cell);
+      return MatchCode.INCLUDE;
+    }
+    returnCode = checkDeleted(deletes, cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    // Skip checking column since we do not remove column during compaction.
+    return columns.checkVersions(cell.getQualifierArray(), cell.getQualifierOffset(),
+      cell.getQualifierLength(), cell.getTimestamp(), cell.getTypeByte(),
+      mvccVersion > maxReadPointToTrackVersions);
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/NormalUserScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/NormalUserScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/NormalUserScanQueryMatcher.java
new file mode 100644
index 0000000..3942f04
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/NormalUserScanQueryMatcher.java
@@ -0,0 +1,106 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellUtil;
+import org.apache.hadoop.hbase.KeepDeletedCells;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.client.Scan;
+import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+
+/**
+ * Query matcher for normal user scan.
+ */
+@InterfaceAudience.Private
+public class NormalUserScanQueryMatcher extends UserScanQueryMatcher {
+
+  /** Keeps track of deletes */
+  private final DeleteTracker deletes;
+
+  /** True if we are doing a 'Get' Scan. Every Get is actually a one-row Scan. */
+  private final boolean get;
+
+  /** whether time range queries can see rows "behind" a delete */
+  private final boolean seePastDeleteMarkers;
+
+  protected NormalUserScanQueryMatcher(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
+      boolean hasNullColumn, DeleteTracker deletes, long oldestUnexpiredTS, long now) {
+    super(scan, scanInfo, columns, hasNullColumn, oldestUnexpiredTS, now);
+    this.deletes = deletes;
+    this.get = scan.isGetScan();
+    this.seePastDeleteMarkers = scanInfo.getKeepDeletedCells() != KeepDeletedCells.FALSE;
+  }
+
+  @Override
+  public MatchCode match(Cell cell) throws IOException {
+    if (filter != null && filter.filterAllRemaining()) {
+      return MatchCode.DONE_SCAN;
+    }
+    MatchCode returnCode = preCheck(cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    long timestamp = cell.getTimestamp();
+    if (CellUtil.isDelete(cell)) {
+      boolean includeDeleteMarker = seePastDeleteMarkers ? tr.withinTimeRange(timestamp)
+          : tr.withinOrAfterTimeRange(timestamp);
+      if (includeDeleteMarker) {
+        this.deletes.add(cell);
+      }
+      return MatchCode.SKIP;
+    }
+    returnCode = checkDeleted(deletes, cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    return matchColumn(cell);
+  }
+
+  @Override
+  protected void reset() {
+    deletes.reset();
+  }
+
+  @Override
+  protected boolean isGet() {
+    return get;
+  }
+
+  public static NormalUserScanQueryMatcher create(Scan scan, ScanInfo scanInfo,
+      ColumnTracker columns, boolean hasNullColumn, long oldestUnexpiredTS, long now,
+      RegionCoprocessorHost regionCoprocessorHost) throws IOException {
+    DeleteTracker deletes = instantiateDeleteTracker(regionCoprocessorHost);
+    if (scan.isReversed()) {
+      return new NormalUserScanQueryMatcher(scan, scanInfo, columns, hasNullColumn, deletes,
+          oldestUnexpiredTS, now) {
+
+        @Override
+        protected boolean moreRowsMayExistsAfter(int cmpToStopRow) {
+          return cmpToStopRow > 0;
+        }
+      };
+    } else {
+      return new NormalUserScanQueryMatcher(scan, scanInfo, columns, hasNullColumn, deletes,
+          oldestUnexpiredTS, now);
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/hbase/blob/dc56aa2d/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/RawScanQueryMatcher.java
----------------------------------------------------------------------
diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/RawScanQueryMatcher.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/RawScanQueryMatcher.java
new file mode 100644
index 0000000..acdae90
--- /dev/null
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/querymatcher/RawScanQueryMatcher.java
@@ -0,0 +1,77 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.hadoop.hbase.regionserver.querymatcher;
+
+import java.io.IOException;
+
+import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.client.Scan;
+import org.apache.hadoop.hbase.regionserver.ScanInfo;
+
+/**
+ * Query matcher for raw scan.
+ */
+@InterfaceAudience.Private
+public class RawScanQueryMatcher extends UserScanQueryMatcher {
+
+  protected RawScanQueryMatcher(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
+      boolean hasNullColumn, long oldestUnexpiredTS, long now) {
+    super(scan, scanInfo, columns, hasNullColumn, oldestUnexpiredTS, now);
+  }
+
+  @Override
+  public MatchCode match(Cell cell) throws IOException {
+    if (filter != null && filter.filterAllRemaining()) {
+      return MatchCode.DONE_SCAN;
+    }
+    MatchCode returnCode = preCheck(cell);
+    if (returnCode != null) {
+      return returnCode;
+    }
+    // For a raw scan, we do not filter out any cells by delete marker, and delete marker is also
+    // returned, so we do not need to track delete.
+    return matchColumn(cell);
+  }
+
+  @Override
+  protected void reset() {
+  }
+
+  @Override
+  protected boolean isGet() {
+    return false;
+  }
+
+  public static RawScanQueryMatcher create(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
+      boolean hasNullColumn, long oldestUnexpiredTS, long now) {
+    if (scan.isReversed()) {
+      return new RawScanQueryMatcher(scan, scanInfo, columns, hasNullColumn, oldestUnexpiredTS,
+          now) {
+
+        @Override
+        protected boolean moreRowsMayExistsAfter(int cmpToStopRow) {
+          return cmpToStopRow > 0;
+        }
+      };
+    } else {
+      return new RawScanQueryMatcher(scan, scanInfo, columns, hasNullColumn, oldestUnexpiredTS,
+          now);
+    }
+  }
+}


Mime
View raw message