001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.regionserver.querymatcher;
019
020import java.io.IOException;
021import java.util.Iterator;
022import java.util.NavigableSet;
023import org.apache.hadoop.hbase.Cell;
024import org.apache.hadoop.hbase.CellComparator;
025import org.apache.hadoop.hbase.CellUtil;
026import org.apache.hadoop.hbase.HConstants;
027import org.apache.hadoop.hbase.KeyValue;
028import org.apache.hadoop.hbase.KeyValue.Type;
029import org.apache.hadoop.hbase.KeyValueUtil;
030import org.apache.hadoop.hbase.PrivateCellUtil;
031import org.apache.hadoop.hbase.PrivateConstants;
032import org.apache.hadoop.hbase.Tag;
033import org.apache.hadoop.hbase.TagType;
034import org.apache.hadoop.hbase.client.Scan;
035import org.apache.hadoop.hbase.filter.Filter;
036import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost;
037import org.apache.hadoop.hbase.regionserver.ScanInfo;
038import org.apache.hadoop.hbase.regionserver.ShipperListener;
039import org.apache.hadoop.hbase.regionserver.querymatcher.DeleteTracker.DeleteResult;
040import org.apache.hadoop.hbase.security.visibility.VisibilityNewVersionBehaivorTracker;
041import org.apache.hadoop.hbase.security.visibility.VisibilityScanDeleteTracker;
042import org.apache.hadoop.hbase.util.Bytes;
043import org.apache.hadoop.hbase.util.Pair;
044import org.apache.yetus.audience.InterfaceAudience;
045
046/**
047 * A query matcher that is specifically designed for the scan case.
048 */
049@InterfaceAudience.Private
050public abstract class ScanQueryMatcher implements ShipperListener {
051
052  /**
053   * {@link #match} return codes. These instruct the scanner moving through memstores and StoreFiles
054   * what to do with the current KeyValue.
055   * <p>
056   * Additionally, this contains "early-out" language to tell the scanner to move on to the next
057   * File (memstore or Storefile), or to return immediately.
058   */
059  public static enum MatchCode {
060    /**
061     * Include KeyValue in the returned result
062     */
063    INCLUDE,
064
065    /**
066     * Do not include KeyValue in the returned result
067     */
068    SKIP,
069
070    /**
071     * Do not include, jump to next StoreFile or memstore (in time order)
072     */
073    NEXT,
074
075    /**
076     * Do not include, return current result
077     */
078    DONE,
079
080    /**
081     * These codes are used by the ScanQueryMatcher
082     */
083
084    /**
085     * Done with the row, seek there.
086     */
087    SEEK_NEXT_ROW,
088
089    /**
090     * Done with column, seek to next.
091     */
092    SEEK_NEXT_COL,
093
094    /**
095     * Done with scan, thanks to the row filter.
096     */
097    DONE_SCAN,
098
099    /**
100     * Seek to next key which is given as hint.
101     */
102    SEEK_NEXT_USING_HINT,
103
104    /**
105     * Include KeyValue and done with column, seek to next.
106     */
107    INCLUDE_AND_SEEK_NEXT_COL,
108
109    /**
110     * Include KeyValue and done with row, seek to next.
111     */
112    INCLUDE_AND_SEEK_NEXT_ROW,
113  }
114
115  /** Row comparator for the region this query is for */
116  protected final CellComparator rowComparator;
117
118  /** Key to seek to in memstore and StoreFiles */
119  protected final Cell startKey;
120
121  /** Keeps track of columns and versions */
122  protected final ColumnTracker columns;
123
124  /** The oldest timestamp we are interested in, based on TTL */
125  protected final long oldestUnexpiredTS;
126
127  protected final long now;
128
129  /** Row the query is on */
130  protected Cell currentRow;
131
132  protected ScanQueryMatcher(Cell startKey, ScanInfo scanInfo, ColumnTracker columns,
133    long oldestUnexpiredTS, long now) {
134    this.rowComparator = scanInfo.getComparator();
135    this.startKey = startKey;
136    this.oldestUnexpiredTS = oldestUnexpiredTS;
137    this.now = now;
138    this.columns = columns;
139  }
140
141  /**
142   * nn * @return true if the cell is expired
143   */
144  private static boolean isCellTTLExpired(final Cell cell, final long oldestTimestamp,
145    final long now) {
146    // Look for a TTL tag first. Use it instead of the family setting if
147    // found. If a cell has multiple TTLs, resolve the conflict by using the
148    // first tag encountered.
149    Iterator<Tag> i = PrivateCellUtil.tagsIterator(cell);
150    while (i.hasNext()) {
151      Tag t = i.next();
152      if (TagType.TTL_TAG_TYPE == t.getType()) {
153        // Unlike in schema cell TTLs are stored in milliseconds, no need
154        // to convert
155        long ts = cell.getTimestamp();
156        assert t.getValueLength() == Bytes.SIZEOF_LONG;
157        long ttl = Tag.getValueAsLong(t);
158        if (ts + ttl < now) {
159          return true;
160        }
161        // Per cell TTLs cannot extend lifetime beyond family settings, so
162        // fall through to check that
163        break;
164      }
165    }
166    return false;
167  }
168
169  /**
170   * Check before the delete logic.
171   * @return null means continue.
172   */
173  protected final MatchCode preCheck(Cell cell) {
174    if (currentRow == null) {
175      // Since the curCell is null it means we are already sure that we have moved over to the next
176      // row
177      return MatchCode.DONE;
178    }
179    // if row key is changed, then we know that we have moved over to the next row
180    if (rowComparator.compareRows(currentRow, cell) != 0) {
181      return MatchCode.DONE;
182    }
183
184    if (this.columns.done()) {
185      return MatchCode.SEEK_NEXT_ROW;
186    }
187
188    long timestamp = cell.getTimestamp();
189    // check if this is a fake cell. The fake cell is an optimization, we should make the scanner
190    // seek to next column or next row. See StoreFileScanner.requestSeek for more details.
191    // check for early out based on timestamp alone
192    if (timestamp == PrivateConstants.OLDEST_TIMESTAMP || columns.isDone(timestamp)) {
193      return columns.getNextRowOrNextColumn(cell);
194    }
195    // check if the cell is expired by cell TTL
196    if (isCellTTLExpired(cell, this.oldestUnexpiredTS, this.now)) {
197      return MatchCode.SKIP;
198    }
199    return null;
200  }
201
202  protected final MatchCode checkDeleted(DeleteTracker deletes, Cell cell) {
203    if (deletes.isEmpty() && !(deletes instanceof NewVersionBehaviorTracker)) {
204      return null;
205    }
206    // MvccSensitiveTracker always need check all cells to save some infos.
207    DeleteResult deleteResult = deletes.isDeleted(cell);
208    switch (deleteResult) {
209      case FAMILY_DELETED:
210      case COLUMN_DELETED:
211        if (!(deletes instanceof NewVersionBehaviorTracker)) {
212          // MvccSensitive can not seek to next because the Put with lower ts may have higher mvcc
213          return columns.getNextRowOrNextColumn(cell);
214        }
215      case VERSION_DELETED:
216      case FAMILY_VERSION_DELETED:
217      case VERSION_MASKED:
218        return MatchCode.SKIP;
219      case NOT_DELETED:
220        return null;
221      default:
222        throw new RuntimeException("Unexpected delete result: " + deleteResult);
223    }
224  }
225
226  /**
227   * Determines if the caller should do one of several things:
228   * <ul>
229   * <li>seek/skip to the next row (MatchCode.SEEK_NEXT_ROW)</li>
230   * <li>seek/skip to the next column (MatchCode.SEEK_NEXT_COL)</li>
231   * <li>include the current KeyValue (MatchCode.INCLUDE)</li>
232   * <li>ignore the current KeyValue (MatchCode.SKIP)</li>
233   * <li>got to the next row (MatchCode.DONE)</li>
234   * </ul>
235   * @param cell KeyValue to check
236   * @return The match code instance.
237   * @throws IOException in case there is an internal consistency problem caused by a data
238   *                     corruption.
239   */
240  public abstract MatchCode match(Cell cell) throws IOException;
241
242  /** Returns the start key */
243  public Cell getStartKey() {
244    return startKey;
245  }
246
247  /** Returns whether there is an null column in the query */
248  public abstract boolean hasNullColumnInQuery();
249
250  /** Returns a cell represent the current row */
251  public Cell currentRow() {
252    return currentRow;
253  }
254
255  /**
256   * Make {@link #currentRow()} return null.
257   */
258  public void clearCurrentRow() {
259    currentRow = null;
260  }
261
262  protected abstract void reset();
263
264  /**
265   * Set the row when there is change in row n
266   */
267  public void setToNewRow(Cell currentRow) {
268    this.currentRow = currentRow;
269    columns.reset();
270    reset();
271  }
272
273  public abstract boolean isUserScan();
274
275  /**
276   * @return Returns false if we know there are no more rows to be scanned (We've reached the
277   *         <code>stopRow</code> or we are scanning on row only because this Scan is for a Get,
278   *         etc.
279   */
280  public abstract boolean moreRowsMayExistAfter(Cell cell);
281
282  public Cell getKeyForNextColumn(Cell cell) {
283    // We aren't sure whether any DeleteFamily cells exist, so we can't skip to next column.
284    // TODO: Current way disable us to seek to next column quickly. Is there any better solution?
285    // see HBASE-18471 for more details
286    // see TestFromClientSide3#testScanAfterDeletingSpecifiedRow
287    // see TestFromClientSide3#testScanAfterDeletingSpecifiedRowV2
288    if (cell.getQualifierLength() == 0) {
289      Cell nextKey = PrivateCellUtil.createNextOnRowCol(cell);
290      if (nextKey != cell) {
291        return nextKey;
292      }
293      // The cell is at the end of row/family/qualifier, so it is impossible to find any
294      // DeleteFamily cells.
295      // Let us seek to next column.
296    }
297    ColumnCount nextColumn = columns.getColumnHint();
298    if (nextColumn == null) {
299      return PrivateCellUtil.createLastOnRowCol(cell);
300    } else {
301      return PrivateCellUtil.createFirstOnRowCol(cell, nextColumn.getBuffer(),
302        nextColumn.getOffset(), nextColumn.getLength());
303    }
304  }
305
306  /**
307   * @param nextIndexed the key of the next entry in the block index (if any)
308   * @param currentCell The Cell we're using to calculate the seek key
309   * @return result of the compare between the indexed key and the key portion of the passed cell
310   */
311  public int compareKeyForNextRow(Cell nextIndexed, Cell currentCell) {
312    return PrivateCellUtil.compareKeyBasedOnColHint(rowComparator, nextIndexed, currentCell, 0, 0,
313      null, 0, 0, PrivateConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
314  }
315
316  /**
317   * @param nextIndexed the key of the next entry in the block index (if any)
318   * @param currentCell The Cell we're using to calculate the seek key
319   * @return result of the compare between the indexed key and the key portion of the passed cell
320   */
321  public int compareKeyForNextColumn(Cell nextIndexed, Cell currentCell) {
322    ColumnCount nextColumn = columns.getColumnHint();
323    if (nextColumn == null) {
324      return PrivateCellUtil.compareKeyBasedOnColHint(rowComparator, nextIndexed, currentCell, 0, 0,
325        null, 0, 0, PrivateConstants.OLDEST_TIMESTAMP, Type.Minimum.getCode());
326    } else {
327      return PrivateCellUtil.compareKeyBasedOnColHint(rowComparator, nextIndexed, currentCell,
328        currentCell.getFamilyOffset(), currentCell.getFamilyLength(), nextColumn.getBuffer(),
329        nextColumn.getOffset(), nextColumn.getLength(), HConstants.LATEST_TIMESTAMP,
330        Type.Maximum.getCode());
331    }
332  }
333
334  /** Returns the Filter */
335  public abstract Filter getFilter();
336
337  /**
338   * Delegate to {@link Filter#getNextCellHint(Cell)}. If no filter, return {@code null}.
339   */
340  public abstract Cell getNextKeyHint(Cell cell) throws IOException;
341
342  @Override
343  public void beforeShipped() throws IOException {
344    if (this.currentRow != null) {
345      this.currentRow = PrivateCellUtil.createFirstOnRow(CellUtil.copyRow(this.currentRow));
346    }
347    if (columns != null) {
348      columns.beforeShipped();
349    }
350  }
351
352  protected static Cell createStartKeyFromRow(byte[] startRow, ScanInfo scanInfo) {
353    return PrivateCellUtil.createFirstDeleteFamilyCellOnRow(startRow, scanInfo.getFamily());
354  }
355
356  protected static Pair<DeleteTracker, ColumnTracker> getTrackers(RegionCoprocessorHost host,
357    NavigableSet<byte[]> columns, ScanInfo scanInfo, long oldestUnexpiredTS, Scan userScan)
358    throws IOException {
359    int resultMaxVersion = scanInfo.getMaxVersions();
360    int maxVersionToCheck = resultMaxVersion;
361    if (userScan != null) {
362      if (userScan.isRaw()) {
363        resultMaxVersion = userScan.getMaxVersions();
364        maxVersionToCheck = userScan.hasFilter() ? Integer.MAX_VALUE : resultMaxVersion;
365      } else {
366        resultMaxVersion = Math.min(userScan.getMaxVersions(), scanInfo.getMaxVersions());
367        maxVersionToCheck = userScan.hasFilter() ? scanInfo.getMaxVersions() : resultMaxVersion;
368      }
369    }
370
371    DeleteTracker deleteTracker;
372    if (scanInfo.isNewVersionBehavior() && (userScan == null || !userScan.isRaw())) {
373      deleteTracker = new NewVersionBehaviorTracker(columns, scanInfo.getComparator(),
374        scanInfo.getMinVersions(), scanInfo.getMaxVersions(), resultMaxVersion, oldestUnexpiredTS);
375    } else {
376      deleteTracker = new ScanDeleteTracker(scanInfo.getComparator());
377    }
378    if (host != null) {
379      deleteTracker = host.postInstantiateDeleteTracker(deleteTracker);
380      if (deleteTracker instanceof VisibilityScanDeleteTracker && scanInfo.isNewVersionBehavior()) {
381        deleteTracker = new VisibilityNewVersionBehaivorTracker(columns, scanInfo.getComparator(),
382          scanInfo.getMinVersions(), scanInfo.getMaxVersions(), resultMaxVersion,
383          oldestUnexpiredTS);
384      }
385    }
386
387    ColumnTracker columnTracker;
388
389    if (deleteTracker instanceof NewVersionBehaviorTracker) {
390      columnTracker = (NewVersionBehaviorTracker) deleteTracker;
391    } else if (columns == null || columns.size() == 0) {
392      columnTracker = new ScanWildcardColumnTracker(scanInfo.getMinVersions(), maxVersionToCheck,
393        oldestUnexpiredTS, scanInfo.getComparator());
394    } else {
395      columnTracker = new ExplicitColumnTracker(columns, scanInfo.getMinVersions(),
396        maxVersionToCheck, oldestUnexpiredTS);
397    }
398    return new Pair<>(deleteTracker, columnTracker);
399  }
400
401  // Used only for testing purposes
402  static MatchCode checkColumn(ColumnTracker columnTracker, byte[] bytes, int offset, int length,
403    long ttl, byte type, boolean ignoreCount) throws IOException {
404    KeyValue kv = KeyValueUtil.createFirstOnRow(HConstants.EMPTY_BYTE_ARRAY, 0, 0,
405      HConstants.EMPTY_BYTE_ARRAY, 0, 0, bytes, offset, length);
406    MatchCode matchCode = columnTracker.checkColumn(kv, type);
407    if (matchCode == MatchCode.INCLUDE) {
408      return columnTracker.checkVersions(kv, ttl, type, ignoreCount);
409    }
410    return matchCode;
411  }
412}