Source code

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.NavigableSet;
022import org.apache.hadoop.hbase.Cell;
023import org.apache.hadoop.hbase.CellUtil;
024import org.apache.hadoop.hbase.KeyValueUtil;
025import org.apache.hadoop.hbase.PrivateCellUtil;
026import org.apache.hadoop.hbase.client.Scan;
027import org.apache.hadoop.hbase.filter.Filter;
028import org.apache.hadoop.hbase.filter.Filter.ReturnCode;
029import org.apache.hadoop.hbase.io.TimeRange;
030import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost;
031import org.apache.hadoop.hbase.regionserver.ScanInfo;
032import org.apache.hadoop.hbase.util.Pair;
033import org.apache.yetus.audience.InterfaceAudience;
034
035/**
036 * Query matcher for user scan.
037 * <p>
038 * We do not consider mvcc here because
039 * {@link org.apache.hadoop.hbase.regionserver.StoreFileScanner} and
040 * {@link org.apache.hadoop.hbase.regionserver.SegmentScanner} will only return a cell whose mvcc is
041 * less than or equal to given read point. For
042 * {@link org.apache.hadoop.hbase.client.IsolationLevel#READ_UNCOMMITTED}, we just set the read
043 * point to {@link Long#MAX_VALUE}, i.e. still do not need to consider it.
044 */
045@InterfaceAudience.Private
046public abstract class UserScanQueryMatcher extends ScanQueryMatcher {
047
048  protected final boolean hasNullColumn;
049
050  protected final Filter filter;
051
052  protected final byte[] stopRow;
053
054  protected final TimeRange tr;
055
056  private final int versionsAfterFilter;
057
058  private int count = 0;
059
060  private Cell curColCell = null;
061
062  private static Cell createStartKey(Scan scan, ScanInfo scanInfo) {
063    if (scan.includeStartRow()) {
064      return createStartKeyFromRow(scan.getStartRow(), scanInfo);
065    } else {
066      return PrivateCellUtil.createLastOnRow(scan.getStartRow());
067    }
068  }
069
070  protected UserScanQueryMatcher(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
071    boolean hasNullColumn, long oldestUnexpiredTS, long now) {
072    super(createStartKey(scan, scanInfo), scanInfo, columns, oldestUnexpiredTS, now);
073    this.hasNullColumn = hasNullColumn;
074    this.filter = scan.getFilter();
075    if (this.filter != null) {
076      this.versionsAfterFilter = scan.isRaw()
077        ? scan.getMaxVersions()
078        : Math.min(scan.getMaxVersions(), scanInfo.getMaxVersions());
079    } else {
080      this.versionsAfterFilter = 0;
081    }
082    this.stopRow = scan.getStopRow();
083    TimeRange timeRange = scan.getColumnFamilyTimeRange().get(scanInfo.getFamily());
084    if (timeRange == null) {
085      this.tr = scan.getTimeRange();
086    } else {
087      this.tr = timeRange;
088    }
089  }
090
091  @Override
092  public boolean hasNullColumnInQuery() {
093    return hasNullColumn;
094  }
095
096  @Override
097  public boolean isUserScan() {
098    return true;
099  }
100
101  @Override
102  public Filter getFilter() {
103    return filter;
104  }
105
106  @Override
107  public Cell getNextKeyHint(Cell cell) throws IOException {
108    if (filter == null) {
109      return null;
110    } else {
111      return filter.getNextCellHint(cell);
112    }
113  }
114
115  @Override
116  public void beforeShipped() throws IOException {
117    super.beforeShipped();
118    if (curColCell != null) {
119      this.curColCell = KeyValueUtil.toNewKeyCell(this.curColCell);
120    }
121  }
122
123  protected final MatchCode matchColumn(Cell cell, long timestamp, byte typeByte)
124    throws IOException {
125    int tsCmp = tr.compare(timestamp);
126    if (tsCmp > 0) {
127      return MatchCode.SKIP;
128    }
129    if (tsCmp < 0) {
130      return columns.getNextRowOrNextColumn(cell);
131    }
132    // STEP 1: Check if the column is part of the requested columns
133    MatchCode matchCode = columns.checkColumn(cell, typeByte);
134    if (matchCode != MatchCode.INCLUDE) {
135      return matchCode;
136    }
137    /*
138     * STEP 2: check the number of versions needed. This method call returns SKIP, SEEK_NEXT_COL,
139     * INCLUDE, INCLUDE_AND_SEEK_NEXT_COL, or INCLUDE_AND_SEEK_NEXT_ROW.
140     */
141    matchCode = columns.checkVersions(cell, timestamp, typeByte, false);
142    switch (matchCode) {
143      case SKIP:
144        return MatchCode.SKIP;
145      case SEEK_NEXT_COL:
146        return MatchCode.SEEK_NEXT_COL;
147      default:
148        // It means it is INCLUDE, INCLUDE_AND_SEEK_NEXT_COL or INCLUDE_AND_SEEK_NEXT_ROW.
149        assert matchCode == MatchCode.INCLUDE || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL
150          || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
151        break;
152    }
153
154    return filter == null
155      ? matchCode
156      : mergeFilterResponse(cell, matchCode, filter.filterCell(cell));
157  }
158
159  /**
160   * Call this when scan has filter. Decide the desired behavior by checkVersions's MatchCode and
161   * filterCell's ReturnCode. Cell may be skipped by filter, so the column versions in result may be
162   * less than user need. It need to check versions again when filter and columnTracker both include
163   * the cell. <br/>
164   *
165   * <pre>
166   * ColumnChecker                FilterResponse               Desired behavior
167   * INCLUDE                      SKIP                         SKIP
168   * INCLUDE                      NEXT_COL                     SEEK_NEXT_COL or SEEK_NEXT_ROW
169   * INCLUDE                      NEXT_ROW                     SEEK_NEXT_ROW
170   * INCLUDE                      SEEK_NEXT_USING_HINT         SEEK_NEXT_USING_HINT
171   * INCLUDE                      INCLUDE                      INCLUDE
172   * INCLUDE                      INCLUDE_AND_NEXT_COL         INCLUDE_AND_SEEK_NEXT_COL
173   * INCLUDE                      INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW
174   * INCLUDE_AND_SEEK_NEXT_COL    SKIP                         SEEK_NEXT_COL
175   * INCLUDE_AND_SEEK_NEXT_COL    NEXT_COL                     SEEK_NEXT_COL or SEEK_NEXT_ROW
176   * INCLUDE_AND_SEEK_NEXT_COL    NEXT_ROW                     SEEK_NEXT_ROW
177   * INCLUDE_AND_SEEK_NEXT_COL    SEEK_NEXT_USING_HINT         SEEK_NEXT_USING_HINT
178   * INCLUDE_AND_SEEK_NEXT_COL    INCLUDE                      INCLUDE_AND_SEEK_NEXT_COL
179   * INCLUDE_AND_SEEK_NEXT_COL    INCLUDE_AND_NEXT_COL         INCLUDE_AND_SEEK_NEXT_COL
180   * INCLUDE_AND_SEEK_NEXT_COL    INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW
181   * INCLUDE_AND_SEEK_NEXT_ROW    SKIP                         SEEK_NEXT_ROW
182   * INCLUDE_AND_SEEK_NEXT_ROW    NEXT_COL                     SEEK_NEXT_ROW
183   * INCLUDE_AND_SEEK_NEXT_ROW    NEXT_ROW                     SEEK_NEXT_ROW
184   * INCLUDE_AND_SEEK_NEXT_ROW    SEEK_NEXT_USING_HINT         SEEK_NEXT_USING_HINT
185   * INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE                      INCLUDE_AND_SEEK_NEXT_ROW
186   * INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_NEXT_COL         INCLUDE_AND_SEEK_NEXT_ROW
187   * INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW
188   * </pre>
189   */
190  private final MatchCode mergeFilterResponse(Cell cell, MatchCode matchCode,
191    ReturnCode filterResponse) {
192    switch (filterResponse) {
193      case SKIP:
194        if (matchCode == MatchCode.INCLUDE) {
195          return MatchCode.SKIP;
196        } else if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL) {
197          return MatchCode.SEEK_NEXT_COL;
198        } else if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW) {
199          return MatchCode.SEEK_NEXT_ROW;
200        }
201        break;
202      case NEXT_COL:
203        if (matchCode == MatchCode.INCLUDE || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL) {
204          return columns.getNextRowOrNextColumn(cell);
205        } else if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW) {
206          return MatchCode.SEEK_NEXT_ROW;
207        }
208        break;
209      case NEXT_ROW:
210        return MatchCode.SEEK_NEXT_ROW;
211      case SEEK_NEXT_USING_HINT:
212        return MatchCode.SEEK_NEXT_USING_HINT;
213      case INCLUDE:
214        break;
215      case INCLUDE_AND_NEXT_COL:
216        if (matchCode == MatchCode.INCLUDE) {
217          matchCode = MatchCode.INCLUDE_AND_SEEK_NEXT_COL;
218        }
219        break;
220      case INCLUDE_AND_SEEK_NEXT_ROW:
221        matchCode = MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
222        break;
223      default:
224        throw new RuntimeException("UNEXPECTED");
225    }
226
227    // It means it is INCLUDE, INCLUDE_AND_SEEK_NEXT_COL or INCLUDE_AND_SEEK_NEXT_ROW.
228    assert matchCode == MatchCode.INCLUDE || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL
229      || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
230
231    // We need to make sure that the number of cells returned will not exceed max version in scan
232    // when the match code is INCLUDE* case.
233    if (curColCell == null || !CellUtil.matchingRowColumn(cell, curColCell)) {
234      count = 0;
235      curColCell = cell;
236    }
237    count += 1;
238
239    if (count > versionsAfterFilter) {
240      // when the number of cells exceed max version in scan, we should return SEEK_NEXT_COL match
241      // code, but if current code is INCLUDE_AND_SEEK_NEXT_ROW, we can optimize to choose the max
242      // step between SEEK_NEXT_COL and INCLUDE_AND_SEEK_NEXT_ROW, which is SEEK_NEXT_ROW.
243      if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW) {
244        matchCode = MatchCode.SEEK_NEXT_ROW;
245      } else {
246        matchCode = MatchCode.SEEK_NEXT_COL;
247      }
248    }
249    if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL || matchCode == MatchCode.SEEK_NEXT_COL) {
250      // Update column tracker to next column, As we use the column hint from the tracker to seek
251      // to next cell (HBASE-19749)
252      columns.doneWithColumn(cell);
253    }
254    return matchCode;
255  }
256
257  protected abstract boolean isGet();
258
259  protected abstract boolean moreRowsMayExistsAfter(int cmpToStopRow);
260
261  @Override
262  public boolean moreRowsMayExistAfter(Cell cell) {
263    // If a 'get' Scan -- we are doing a Get (every Get is a single-row Scan in implementation) --
264    // then we are looking at one row only, the one specified in the Get coordinate..so we know
265    // for sure that there are no more rows on this Scan
266    if (isGet()) {
267      return false;
268    }
269    // If no stopRow, return that there may be more rows. The tests that follow depend on a
270    // non-empty, non-default stopRow so this little test below short-circuits out doing the
271    // following compares.
272    if (this.stopRow == null || this.stopRow.length == 0) {
273      return true;
274    }
275    return moreRowsMayExistsAfter(rowComparator.compareRows(cell, stopRow, 0, stopRow.length));
276  }
277
278  public static UserScanQueryMatcher create(Scan scan, ScanInfo scanInfo,
279    NavigableSet<byte[]> columns, long oldestUnexpiredTS, long now,
280    RegionCoprocessorHost regionCoprocessorHost) throws IOException {
281    boolean hasNullColumn =
282      !(columns != null && columns.size() != 0 && columns.first().length != 0);
283    Pair<DeleteTracker, ColumnTracker> trackers =
284      getTrackers(regionCoprocessorHost, columns, scanInfo, oldestUnexpiredTS, scan);
285    DeleteTracker deleteTracker = trackers.getFirst();
286    ColumnTracker columnTracker = trackers.getSecond();
287    if (scan.isRaw()) {
288      return RawScanQueryMatcher.create(scan, scanInfo, columnTracker, hasNullColumn,
289        oldestUnexpiredTS, now);
290    } else {
291      return NormalUserScanQueryMatcher.create(scan, scanInfo, columnTracker, deleteTracker,
292        hasNullColumn, oldestUnexpiredTS, now);
293    }
294  }
295}